- 一、作業系統
- 二、Linux 程式設計
一、作業系統
(一) Semaphore
- Synchronization tool that does not require busy waiting.
- Semaphore S – integer variable
- Two standard operations modify S:
wait()andsignal() - Less complicated
- Can only be accessed via two indivisible (atomic) operations
wait(S)
while (S <= 0)
; //busy wait
S--;
}
signal(S) {
S++;
}
1. Usage
- Counting semaphore – integer value can range over an unrestricted domain
- Binary semaphore – integer value can range only between 0 and 1
- Then a
mutex lock
- Then a
- Can implement a counting semaphore S as a binary semaphore
- Can solve various synchronization problems
- Consider P1 and P2 that require S1 to happen before S2
P1:
S1;
signal(synch);
P2:
wait(synch);
S2;
2. Implementation
(1) Busy waiting
-
Must guarantee that no two processes can execute
wait()andsignal()on the same semaphore at the same time - Thus, implementation becomes the critical section problem where the wait and signal code are placed in the critical section
- Could now have busy waiting in critical section implementation
- But implementation code is short
- Little busy waiting if critical section rarely occupied
- Note that applications may spend lots of time in critical sections and therefore this is not a good solution
(2) with no Busy waiting
- With each semaphore there is an associated waiting queue
- Each entry in a waiting queue has two data items:
- value (of type integer)
- pointer to next record in the list
- Two operations:
block– place the process invoking the operation on the appropriate waiting queuewakeup– remove one of processes in the waiting queue and place it in the ready queue
typedef struct{
int value;
struct process *list;
} semaphore;
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
// add this process to S->list;
block();
}
}
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
// remove a process P from S->list;
wakeup(P);
}
}
(二) Deadlock and Starvation
- Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes
-
Let S and Q be two semaphores initialized to 1
- Starvation – indefinite blocking
- A process may never be removed from the semaphore queue in which it is suspended
- Priority Inversion
- Scheduling problem when lower-priority process holds a lock needed by higher-priority process
- Solved via priority-inheritance protocol
(三) Classical Problems of Synchronization
1. Bounded-Buffer Problem
- n buffers, each can hold one item
- Semaphore
mutexinitialized to the value 1 - Semaphore
fullinitialized to the value 0 - Semaphore
emptyinitialized to the value n
- Semaphore
(1) The structure of the producer process
do {
...
/* produce an item in next_produced */
...
wait(empty);
wait(mutex);
...
/* add next produced to the buffer */
...
signal(mutex);
signal(full);
} while (true);
(2) The structure of the consumer process
do {
wait(full);
wait(mutex);
...
/* remove an item from buffer to next_consumed */
...
signal(mutex);
signal(empty);
...
/* consume the item in next consumed */
...
} while (true);
2. Readers-Writers Problem
- A data set is shared among a number of concurrent processes
- Readers - only read the data set; they do not perform any updates
- Writers - can both read and write
- Problem - allow multiple readers to read at the same time
- Several variations of how readers and writers are treated – all involve priorities
- Shared Data
- Data set
- Semaphore
rw_mutexinitialized to 1 - Semaphore
mutexinitialized to 1 - Integer
read_countinitialized to 0
(1) The structure of a writer process
do {
wait(rw_mutex);
...
/* writing is performed */
...
signal(rw_mutex);
} while (true);
(2) The structure of a reader process
do {
wait(mutex);
read_count++;
if (read_count == 1) // only for the first reader entering
wait(rw_mutex);
signal(mutex); // if the first reader wait for rw_mutex, other readers will be blocked on wait(mutex)
...
/* reading is performed */
...
wait(mutex);
read_count--;
if (read_count == 0) // only for the last reader leaving
signal(rw_mutex);
signal(mutex);
} while (true)
(3) Problem
- First variation – no reader kept waiting unless writer has permission to use shared object
- Second variation – once writer is ready, it performs write asap
- Both may have starvation leading to even more variations
- Problem is solved on some systems by kernel providing
reader-writer locks
3. Dining-Philosophers Problem
- Philosophers spend their lives thinking and eating
- Don’t interact with their neighbors, occasionally try to pick up 2 chopsticks (one at a time) to eat from bowl
- Need both to eat, then release both when done
- Need both to eat, then release both when done
(1) In the case of 5 philosophers
- Shared data
- Bowl of rice (data set)
- Semaphore chopstick [5] initialized to 1
- The structure of Philosopher i:
do {
wait ( chopstick[i] );
wait ( chopStick[ (i+1) % 5] );
// eat
signal ( chopstick[i] );
signal (chopstick[ (i+1) % 5] );
// think
} while (TRUE);
- Incorrect use of semaphore operations:
- signal (mutex) …. wait (mutex)
- wait (mutex) … wait (mutex)
- Omitting of wait (mutex) or signal (mutex) (or both)
- Deadlock and starvation
(2) Monitors
- A high-level abstraction that provides a convenient and effective mechanism for process synchronization
- Abstract data type, internal variables only accessible by code within the procedure
- Only one process may be active within the monitor at a time
- But not powerful enough to model some synchronization schemes
Monitors Implementation
1. Using Semaphores
- Variables
semaphore mutex; // (initially = 1)
semaphore next; // (initially = 0)
int next_count = 0;
- Each procedure F will be replaced by
wait(mutex);
...
body of F;
...
if (next_count > 0)
signal(next)
else
signal(mutex);
- Mutual exclusion within a monitor is ensured
2. Condition Variables
- For each condition variable x, we have:
semaphore x_sem; // (initially = 0)
int x_count = 0;
- The operation
x.waitcan be implemented as:
x-count++;
if (next_count > 0)
signal(next);
else
signal(mutex);
wait(x_sem);
x-count--;
Resuming Processes
- If several processes queued on condition x, and x.signal() executed, which should be resumed?
- FCFS frequently not adequate
- conditional-wait construct of the form x.wait(c)
- Where c is priority number
- Process with lowest number (highest priority) is scheduled next
Allocate Single Resource
monitor ResourceAllocator
{
boolean busy;
condition x;
void acquire(int time) {
if (busy)
x.wait(time);
busy = TRUE;
}
void release() {
busy = FALSE;
x.signal();
}
initialization code() {
busy = FALSE;
}
}
(3) Solution
- Each philosopher i invokes the operations
pickup()andputdown()in the following sequence:- No deadlock, but starvation is possible.
DiningPhilosophers.pickup(i);
EAT
DiningPhilosophers.putdown(i);
monitor DiningPhilosophers
{
enum { THINKING; HUNGRY, EATING) state [5] ;
condition self [5];
void pickup (int i) {
state[i] = HUNGRY;
test(i);
if (state[i] != EATING) self [i].wait;
}
void putdown (int i) {
state[i] = THINKING;
/* test left and right neighbors */
test((i + 4) % 5);
test((i + 1) % 5);
}
void test (int i) {
if ((state[(i + 4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING)) {
state[i] = EATING;
self[i].signal();
}
}
initialization_code() {
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
}
二、Linux 程式設計
- 課程簡報
(一) mmap
void *mmap(void *addr, size_t len, int port, int flags, int fildes, off_t off);- PORT_READ
- PORT_WRITE
- PORT_EXEC
- PORT_NONE
- MAP_PRIVATE
- MAP_SHARED
- MAP_FIXED
(二) msync
int msync(void* addr, size_t len, int flags);- MS_AYSNC (非同步寫入)
- MS_SYNC (同步寫入)
- MS_INVALIDATE (再從檔案讀)
(三) munmap
-
int munmap(void * addr, size_t len); fprintf.c#include <stdio.h> #include <stdlib.h> #include <time.h> #define SIZE 100 int main() { FILE *fptr, *fptr2; int i, j; float a, b; srand(time(NULL)); fptr = fopen("ans.txt", "w"); if (!fptr){ printf("open error \n"); exit(1); } else { printf("open success, start writing into file\n"); } for (i = 1; i <= SIZE; i++) { a = ((float)rand() / (float)(RAND_MAX)) * 100; printf("[%3d] = %3.3f\n", i, a); fprintf(fptr, "%3.3f\n", a); } fclose(fptr); /*---------------------------------------------------------- */ fptr2 = fopen("ans.txt", "r"); if(!fptr2) { printf("open error\n"); exit(1); } else { printf("open success, start reading from file\n"); } i = 1; while (fscanf(fptr2, "%6f" ,&b) == 1) printf("[%3d] = %3.3f\n", i++, b); fclose(fptr2); return 0; }- 執行結果
課堂作業
- 給予一個資料檔，計算其平均值與標準差。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define SIZE 100
int main() {
FILE *fptr1, *fptr2;
int i;
float a = .0, total = .0, avg = .0;
float sigma = .0, sd = .0;
/* Use fptr1 to calculate total and average */
fptr1 = fopen("ans.txt", "r");
if (!fptr1) {
printf("open error\n");
exit(1);
}
else {
printf("\nopen success, fptr1 starts reading from file\n");
}
i = 1;
while (fscanf(fptr1, "%6f" ,&a) == 1) {
printf("[%3d] = %3.3f\n", i++, a);
total += a;
}
avg = (total / i);
fclose(fptr1);
/* Use fptr2 to calculate standard deviation */
fptr2 = fopen("ans.txt", "r");
if (!fptr2) {
printf("open error\n");
exit(1);
}
else {
printf("\nopen success, fptr2 starts reading from file\n");
}
i = 1;
while (fscanf(fptr2, "%6f" ,&a) == 1) {
sigma += (a - avg) * (a - avg);
i++;
}
sd = sqrt(sigma / i);
fclose(fptr2);
/* Output */
printf("\n\nThe average = %f\n", avg);
printf("The standard deviation = %f\n", sd);
return 0;
}
- 執行結果
