●●● ●●●● 6.2 The Critical-Section Problem::: ●●●● ● Preemptive kernels ●●●● Be carefully designed to ensure that shared kernel data are free from race conditions Be especially difficult to design for SMP Solaris、IRX、 Linux(26 or later) The advantage of preemptive kernels Be more suitable for real-time programming May be more responsive, since there is less risk that a kernel-mode process will run for an arbitrarily long period
17 6.2 The Critical-Section Problem ⚫ Preemptive kernels ▪ Be carefully designed to ensure that shared kernel data are free from race conditions ▪ Be especially difficult to design for SMP ▪ Solaris、IRIX、Linux (2.6 or later) ▪ The advantage of preemptive kernels ▪ Be more suitable for real-time programming ▪ May be more responsive, since there is less risk that a kernel-mode process will run for an arbitrarily long period
●●● ●●●● 6. Process synchronization 9988 ●●●● e 6.1 Background ●●●● o 6.2 The Critical-Section Problem °6.3 Peterson’sSo|uton 6.4 Synchronization Hardware 6.5 Semaphores o 6.6 Classic Problems of synchronization ●67 Monitors e 6.8 Synchronization Examples o 6.9 Atomic transactions
18 6. Process synchronization ⚫ 6.1 Background ⚫ 6.2 The Critical-Section Problem ⚫ 6.3 Peterson’s Solution ⚫ 6.4 Synchronization Hardware ⚫ 6.5 Semaphores ⚫ 6.6 Classic Problems of Synchronization ⚫ 6.7 Monitors ⚫ 6.8 Synchronization Examples ⚫ 6.9 Atomic Transactions
●●● ●●●● 6.3 Peterson's solution ●●●●● ●●●● ●●0●● ●●●● . Software-based solution to the critical ●●●● section problem ● conditions o Only 2 processes, Po and P o Assume that the load and store instructions are atomic, that is, cannot be interrupted o The two processes share two variables: o int turn;∥=0or1 indicates whose turn it is to enter the critical section ●Boo| ean flag[2] is used to indicate if a process is ready to enter the critical section flag[i]= true implies that process Pi is ready
19 6.3 Peterson’s Solution ⚫ Software-based solution to the critical section problem ⚫ conditions ⚫ Only 2 processes, P0 and P1 ⚫ Assume that the LOAD and STORE instructions are atomic; that is, cannot be interrupted ⚫ The two processes share two variables: ⚫ int turn; // =0 or 1 ▪ indicates whose turn it is to enter the critical section ⚫ Boolean flag[2]; ▪ is used to indicate if a process is ready to enter the critical section ▪ flag[i] = true implies that process Pi is ready!
●●● ●●●● 6.3 Peterson's solution ●●●●● ●●●● ●●0●● ●●●0 ●A| gorithm1 ●●●● Process P Process P do i while(turn =i) do i while (turn = j; critical section critical section urn turn i: reminder section reminder section 3 while(true); 3 while(true); Satisfies mutual exclusion, but not progress requirement Turn=0, and Pl is ready to enter again( after entering) P1 will wait(until PO exits) Requires that Po and p1 must run in turn
20 6.3 Peterson’s Solution ⚫ Algorithm 1 ⚫ Process Pi Process Pj do { while (turn != i) ; do { while (turn != j) ; critical section critical section turn = j; turn = i; reminder section reminder section } while (true); } while (true); ⚫ Satisfies mutual exclusion, but not progress requirement ⚫ Turn=0, and P1 is ready to enter again（after entering） ▪ P1 will wait (until P0 exits) ▪ Requires that P0 and P1 must run in turn
●●● ●●●● 6.3 Peterson's solution ●●●●● ●●●● ●●0●● ●●●● · Algorithm2 ●●●● Process P do t flag []=true; while (flag []strue); critical section flag []=false; remainder section 3 while(true) Satisfies mutual exclusion, but not progress requirement ●flag[=flag=true; PO, P1 will all wait for ever
21 6.3 Peterson’s Solution ⚫ Algorithm 2 ⚫ Process Pi do { flag [i] = true; while (flag [j]==true) ; critical section flag [i] = false; remainder section } while (true); ⚫ Satisfies mutual exclusion, but not progress requirement ⚫ flag [i]= flag [j]=true； ▪ P0, P1 will all wait for ever