本文是我在上UCSD的 CSE 120: Principles of Operating Systems (Winter 2020) 整理的笔记,这一课主要介绍了操作系统里面进程同步的算法,主要是信号量 (Semaphores) 的使用。
Problem introduction
-
Introduction
- synchronization: events happen at the same time
- Process synchronization
- Events in process that occur “at the same time”
- one process have to wait for another
- Usage
- prevent race conditions
- wait for resources to become available
-
race condition
- race condition: two process which should run sequently accidentally run at the same time (which cause a bug)
- To avoid race conditions:
- identify related critical sections
- Section of code excuted by different processes
- critical sections must run atomically w.r.t each other
- Enforce mutual exclusion
- only one process is allowed to be active in critical section
- identify related critical sections
- Atomic
- atomic means “indivisible”
- effective atomicity
- interrupt may occur, but it shouldn’t has effect on that section caused by other processes
- How to determine wether a critical section is atomic
- Consider effect of critical section in isolation
- Consider interruptions: if the result is same, then it is OK.
- Mutual exclusion
- Surrond critical section with entry/exit code
- entry code act as a barrier
- if another process is critical section, block current process till it exit
- Otherwise, allow process to proceed
- Exit code should release other entry barriers
-
Requirements for good solution
- Given
- multiple cooperating process
- each with related critical sections
- At most one process in a critical section
- Can’t prevent entry if no others in critical section
- Should eventually be able to enter critical section
- No assumptions about CPU speed or number.
- Given
Different approaches for mutual exclusion (workable)
-
Peterson’s solution
-
implementation
shared int turn; shared bool intent[2] = {false, false}; // P0 intent[0] = TRUE; turn = 1; turn = 0; while (intent[1] && turn==1); /* < critical section > */ intent[0] = FALSE; // P1 intent[1] = TRUE; while (intent[0] && turn==0); /* < critical section > */ intent[1] = FALSE;
-
if competition occur, take turns, otherwise enter
-
for competing process number larger than 2, the solution will become more complex
-
-
Test-and-Set Lock Instruction: TSL
-
requirement: TSL mem
do atomically (i.e., locking the memory bus) [test if mem == 0 AND set mem = 1]
-
a possible C function implementation for TSL (it should be guaranteed atomic)
TSL(int *lockptr) { int oldval; oldval = *lockptr *lockptr = 1; return ((oldval == 0) ? 1 : 0); }
-
mutual exclusion using TSL
shared int lock = 0; // P0 while (! TSL(&lock)); /* < critical section > */ lock = 0; // P1 while (! TSL(&lock)); /* < critical section > */ lock = 0;
-
shared variable solution using TSL(int *)
- test if lock == 0 (if so, will return 1; else 0)
- before returning, sets lock to 1
-
simple, works for any number of threads
-
still suffering from busy waiting
-
-
Semaphores
-
Synchronization varaible
- takes on integer values (non-negative)
- can cause a process to block/unblock
-
wait and signal operations (must be atomic, use a lower-level mechanism)
- wait(s) block if zero, else decrement
- signal(s) unblock a process if any, else increment
-
no other operations allowed (cannot change/test value of semaphore)
-
simple, works for n processes
-
busy-waiting still exist, but it lies inside semephore, which last shorter
-
Implementation
wait(sem s) { s.n = s.n – 1; if (s.n < 0) { addProc (me, s.L); // add process to waiting list block (me); } } signal(sem s) { s.n = s.n + 1; if (!empty (s.L)) { p = removeProc (s.L); // select a process from waiting list to release unblock (p); } }
-
Only synchronization, no information transfer
- no way for a process to tell it blocked
-
-
Usage of semaphore
-
basic usage example
sem mutex = 1; //P0 wait(mutex); /* < critical section > */ signal(mutex); //P1 wait(mutex); /* < critical section > */ signal(mutex)
-
order how processes execute
sem cond = 0; // P0 /* < to be done before P1 > */ signal(cond); // P1 wait(cond); /* < to be done after P0 > */
-