Software-based Approach
Only 2 processes, P0 and P1
General structure of process Pi (other process Pj)
Processes may share some common variables to synchronize their actions.
프로세스는 작업을 동기화하기 위해 몇 가지 공통 변수를 공유할 수 있습니다.
Software-based Approach (Algorithm 1)
Shared variables:
- int turn = 0;
if turn == i, then Pi can enter its critical section.
Satisfies mutual exclusion, but not progress requirement.
- Requires strict alternation
if turn == 0 and P1 is ready to enter its critical section, P1 cannot do so, even though P0 may be in its remainder section (not in the critical section).
Software-based Approach (Algorithm 2)
Shared variables
- boolean flag [2];
initially flag [0] = flag [1] = false
- if flag [i] == true,
then Pi is ready to enter its critical section
Satisfies mutual exclusion, but not progress requirement. - Consider the case where,
T0 : P0 sets flag [0] = true
T1 : P1 sets flag [1] = true
Software-based Approach (Peterson’s Algorithm)
Combination of algorithms 1/2;
Meets all requirements => Prove !
No guarantee to work on modern computers (i.e., processors or compilers may reorder instructions with no dependencies).
Synchronization Instruction (1)
Many systems provide hardware support for critical section code.
많은 시스템이 중요한 섹션 코드에 대한 하드웨어 지원을 제공합니다.
In uni-processors, we could disable interrupts.
Currently running code would execute without preemption.
유니 프로세서에서는 인터럽트를 비활성화할 수 있습니다.
현재 실행 중인 코드는 선점 없이 실행됩니다.
This is generally too inefficient on multiprocessor systems.
Operating systems using this are not broadly scalable.
멀티프로세서 시스템에서는 일반적으로 너무 비효율적입니다.
이를 사용하는 운영 체제는 광범위하게 확장되지 않습니다.
Modern machines provide special atomic hardware instructions.
(atomic = non-interruptable)
- Either test memory word and set value (TestAndSet)
- Or swap contents of two memory words (Swap)
Synchronization Instruction (2)
Test and modify the content of a word atomically.
Shared data: boolean lock = false;
Mutual exclusion implementation with TestAndSet (does not meet bounded waiting requirement).
Synchronization Instruction (3)
Atomically swap two variables.
Shared data: boolean lock = false;
Mutual exclusion implementation with Swap (does not meet bounded waiting requirement).
Mutual Exclusion with TestAndSet()
