Operating system chapter 5

صفحه 1:
Concurrency: Mutual Exclusion and Synchronization Chapter 5 

صفحه 2:
Concurrency ° Multiple applications ° Structured applications ° Operating system structure 

صفحه 3:
Concurrency ‘Table 5.1 Some Key Terms Related to Concurrency ‘A section of code within aprocess that requires access to stared resources and which may not be executed while another process isin a comesponding section of code. A situation in which two or mote processes a unable to proceed because cach is waiting for one ofthe others to do something. A situation in which two or more processes contiamously change their state in ‘response to changes in the other process(es) without doing any useful wot ‘The requirement that when one process is ina critical section that aceesses, shared resources, no other proces: may he in a critical section that accesses ny of those shared resources. A situation in which multiple threads or processes read and write a shared ‘dna item and the final result depend om the relative timing oftheir ‘execution A situation in which a runaable process is overlooked indefinitely by the Scheduler: although it is able to proceed itis never chosen, critical section deadlock livelock ‘mutual exclusion starvation 

صفحه 4:
Difficulties of Concurrency ° Sharing of global resources ° Operating system managing the allocation of resources optimally ° Difficult to locate programming errors 

صفحه 5:
Currency ° Communication among processes ° Sharing resources ° Synchronization of multiple processes ° Allocation of processor time 

صفحه 6:
Concurrency ° Multiple applications ~ Multiprogramming ° Structured application ~ Application can be a set of concurrent processes ° Operating-system structure ~ Operating system is a set of processes or threads 

صفحه 7:
A Simple Example void echo() { chin = getchar(); chout = chin; putchar(chout) ; } 

صفحه 8:
A Simple Example Process Pl Process P2 chin = getchar(); 5 chin = getchar(); chout = chin; chout = chin; putchar(chout) ; putchar(chout) ; 

صفحه 9:
Operating System Concerns Keep track of various processes Allocate and deallocate resources Processor time ~ Memory ~ Files ~ I/O devices Protect data and resources Output of process must be independent of the speed of execution of other concurrent processes 

صفحه 10:
Process Interaction ° Processes unaware of each other ° Processes indirectly aware of each other ° Process directly aware of each other 

صفحه 11:
11 ۳ سس Mia exclusion ‘Deadlock (renewable resource) 3030 Mutual excision ‘Deadlock (euewable source) و Dua cobeence Deadloels (cosuzble ‏مس‎ ‘Starvation Process Interaction taftence that one موه مه ‎proves independent‏ ‎ieee‏ ‎sect‏ -Tiniag of process aay be affected ‎of oe‏ له ‎proces may depend‏ و ‎tine fom others ‎stinine of process say be affected ‎Rests of one process me dopend ‏مه و‎ bane fom others ‏مه متس ‏هه ‎ ‎Table 5.2 ‎Relationship ‎[Competition ‎Cooperation by sharing ‎Cooperation by ‎ ‎Degree of Avareness ‎Processes ooawa of ‏لمعم‎ ‎| ‎rear of each other (ee. shared object) ‎Process dreeiy ‏هه اه مس‎ ther ‎Gave communication riitives avaiable 5 Sem) ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 12:
Competition AMOong Processes for ‎Benen Ce‏ تمه ‎~ Critical sections ‎* Only one program at a time is allowed in its critical section ‎° Example only one process at a time is allowed to send command to the printer ‎° Deadlock ° Starvation 

صفحه 13:
Requirements for Mutual Exclusion ° Only one process at a time is allowed in the critical section for a resource ° A process that halts in its noncritical section must do so without interfering with other processes ° No deadlock or starvation 

صفحه 14:
Requirements for Mutual Exclusion * A process must not be delayed access to a critical section when there is no other process using it ¢ No assumptions are made about relative process speeds or number of processes ۰ A process remains inside its critical section for a finite time only 

صفحه 15:
Mutual Exclusion: Hardware Support ° Interrupt Disabling ~ A process runs until it invokes an operating system service or until it is interrupted ~ Disabling interrupts guarantees mutual exclusion ~ Processor is limited in its ability to interleave programs ~ Multiprocessing ° disabling interrupts on one processor will not guarantee mutual exclusion 

صفحه 16:
Mutual Exclusion: Hardware Support ° Special Machine Instructions ~ Performed in a single instruction cycle ~ Access to the memory location is blocked for any other instructions 

صفحه 17:
Mutual Exclusion: Hardware Support * Test and Set Instruction boolean testset (int i) { if (i == 0) { i=1; return true; } else { return false; } 1 

صفحه 18:
Mutual Exclusion: Hardware Support ° Exchange Instruction void exchange(int register, int memory) { int temp; temp = memory; memory = register; register = temp; } 

صفحه 19:
Mutual Exclusion 7# program mutualexclusion #7 int const n = /* number of processes*+/; int bolt: void P(int i) 1 int keyi? while (true) 1 keyi = 1) while (keyi != 0) exchange (keyi, bolt): J+ critical section ۶ exchange (eyi, bolt); ۳ remainder */ 1 1 void main () bolt = 0; parbogin (P(1), PQ), ~~. «4 Pin))s 0 () Exchange instruction ‘* number of processes */; spin): 7# progran mitualexclusion *7 const int 2 int bolt: void P(int i) 0 while (true) 0 while (!testeet (bolt) 7 de nothing ۶ /* critical section ۶ bolt = 0; 7* senainde: +/ 1 1 void main() 1 bolt = 07 parbogin (P(1), 2@), (@) Test and sot instruction Figure 52. Hardware Support for Mutual Exclusion 19 

صفحه 20:
Mutual Exclusion Machine Instructions ° Advantages ~ Applicable to any number of processes on either a single processor or multiple processors sharing main memory ~ It is simple and therefore easy to verify ~ It can be used to support multiple critical sections 

صفحه 21:
Mutual Exclusion Machine Instructions * Disadvantages ~ Busy-waiting consumes processor time ~ Starvation is possible when a process leaves a critical section and more than one process is waiting. ~ Deadlock ۰ If a low priority process has the critical region and a higher priority process needs, the higher priority process will obtain the processor to wait for the critical region 21 

صفحه 22:
Semaphores ° Special variable called a semaphore is used for signaling ° If a process is waiting for a signal, it is suspended until that signal is sent 

صفحه 23:
Semaphores ° Semaphore is a variable that has an integer value ~ May be initialized toa nonnegative number ~ Wait operation decrements the semaphore value ~ Signal operation increments semaphore value 

صفحه 24:
24 Semaphore Primitives Figure 5.3 A Definition of Semaphore Primitives 

صفحه 25:
Binary Semaphore Primitives Figure 5.4 A Definition of Binary Semaphore Primitives 

صفحه 26:
Mutual Exclusion Using Semaphores Figure 5.6 Mutual Exclusion Using Semaphores 

صفحه 27:
27 Cepia ‎Sa Te aoe‏ تست ‎= CoE ‏منت‎ phe Kel ete ‎Cong ‎a ge ‏]1 ‏ع ‎GE ‎ey gone ‎ ‎ ‎ ‏متا ‏تست ‎ ‎Figure 5.5 Example of Semaphore Mechanism ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 28:
Ti mia] Figure 5.7 Processes Accessing Shared Data Protected by a Semaphore 28 

صفحه 29:
Producer/Consumer Problem * One or more producers are generating data and placing these in a buffer ° A single consumer is taking items out of the buffer one at time ° Only one producer or consumer may access the buffer at any one time 

صفحه 30:
Producer producer: while (true) { /* produce item v */ b[in] = v; int++; } 

صفحه 31:
Consumer consumer: while (true) { while (in <= out) /*do nothing */; w = b[out]; out++; /* consume item w */ } 

صفحه 32:
Producer/Consumer Problem o 1 23 4 اكاط | لخاط | أقاط | لغاط | لتاط ۳۹ 

صفحه 33:
Producer with Circular Buffer producer: while (true) { /* produce item v */ while ((in + 1) % n == out) /* do nothing */; b[in] = v; in = (in+1)%n 

صفحه 34:
Consumer with Circular Buffer consumer: while (true) { while (in == out) /* do nothing */; w = b[out]; out = (out + 1) % n; /* consume item w */ } 

صفحه 35:
35 3 0 Figure £12 Finite Circular Buffer fo the Producer'Consumer Problem 

صفحه 36:
12 */ ant a; binary semaphore s binary semaphore delay void producer () while (crue) 0 produce () + enbiaitS (3) append()? ‏لتحم عد‎ ‘semsiquats (delay) ; semsignals (s) + while (rue) 1 semmeirs(s); ‏مت‎ (۶ ‘senSignalB (2); consune () if ‏روحسم‎ ‘senlaita (delay) ۶ 0 void main() pazbegin (producer, consumer); Figure ‏فک‎ An Incorrect Solution to the Infinite-Buffer Producer/Consumer 3g Problem Using Binary Semaphores 

صفحه 37:
37 7* program producercansuner */ int a: nary semaphore = = 1; | ‏لإقاقة وعم‎ produce () ‏)نداد‎ append()7 Af (n=1)_semsignals (delay) + sensignaln(s)+ Void consumer () int mj /* a local sonfiaita (delay) + while (ere) Sersignale (5); Consume (7 sonltaice (delay): Parbegin (producer, consumer) ۶ Figure 5.10 A Correct Solution to the Infinite Buffer Producer/Consumer Problem Using Binary Semaphores 

صفحه 38:
38 semaphore 5 void producer () ‘ while (crue) 1 produce (+ Seniiait (3) 5 sensignal (۶ } void consumez() while (crue) 1 sonmait (a): ‏ده‎ 7 take (); sonSignal (s) 7 consume 0 > void main () parbegin (producer, consumer) ; Figure 5.11 A Solution to the Infinite Buffer Producer/Consumer Problem Using Semaphores 

صفحه 39:
39 7* program boundedsutfer */ const int ‏عم عت مده ذه‎ = /* bu Semapho Semaphore o= sizeofbuffer; void producer () 1 while (crus) 1 produce () Semiait (2) : seniait (3)? append() semSignal (3) + sencignal (n) > 7 void consumer () 4 while (true) 0 senmtait (a); semmait (5); take; , Figure 5.13 A Solution to the Bounded-Buffer Producer/Consumer Problem Using Semaphores 

صفحه 40:
Monitors ° Monitor is a software module ° Chief characteristics ~ Local data variables are accessible only by the monitor ~ Process enters monitor by invoking one of its procedures - Only one process may be executing in the monitor at a time 40 

صفحه 41:
queue of ‏سس‎ ‏تسس‎ monitor wing fea Entrance ماه زو a initization ede Figure 5.15 Structure of a Monitor 

صفحه 42:
42 3 فعس 0 (resume any esting consumer J batter is enpty? avoid underflow Jr one teyer inem on rote: (+ Steume aS) waitins pesaue fs monitor nosy eee 0 tf (count ‏ور‎ ‎| ‎the ‏هد هید عمف‎ putser +/ oid take (cher 2) بدح عسوم عه و و ‎Same‏ ‏سيت 

صفحه 43:
43 قم عمد رص مسد void maint) parbegin ‏ل‎ consumer) + 0 Figure $.16 A Solution to the Bounded Buffer Producer/Consumer Problem Using a Monitor 

صفحه 44:
44 avead overflow */ ‎potter a2‏ -ز ‎ ‎2 ‎Figure $.17 Bounded Buffer Monitor Code for Mesa Monitor ‎ ‎ ‎ 

صفحه 45:
Message Passing ° Enforce mutual exclusion ° Exchange information send (destination, message) receive (source, message) 

صفحه 46:
Synchronization ° Sender and receiver may or may not be blocking (waiting for message) ° Blocking send, blocking receive ~ Both sender and receiver are blocked until message is delivered ~ Called a rendezvous 

صفحه 47:
Synchronization ° Nonblocking send, blocking receive ~ Sender continues on ~ Receiver is blocked until the requested message arrives ° Nonblocking send, nonblocking receive ~ Neither party is required to wait 

صفحه 48:
Addressing ° Direct addressing ~ Send primitive includes a specific identifier of the destination process ~ Receive primitive could know ahead of time which process a message is expected ~ Receive primitive could use source parameter to return a value when the receive operation has been performed 48 

صفحه 49:
Addressing ° Indirect addressing ~ Messages are sent to a shared data structure consisting of queues ~ Queues are called mailboxes ~ One process sends a message to the mailbox and the other process picks up the message from the mailbox 

صفحه 50:
(2) Ome toe many one (90st many (a) san to any Figure 5.18 Indireet Process Communication. 50 

صفحه 51:
Message Format 

صفحه 52:
uaion */ /۰ program mutual const int a = /* munber of void P(i 1 mossago msg: while (true) 1 Send (mutex, msg); /* remainder ۶ 1 0 vold main() 1 exeate mailbox (mutex)? send (mutex, null); parbegin (PQ), F(2), +. +» Pinl)s Figure §.20 Mutual Exclusion Using Messages 

صفحه 53:
{message emsg? while (crue) 1 seceive (mayproduce, pmsg); pmsg = produce ()+ Send (mayconsume, pmsg); 0 void consumer() {message cmsg; while (true) receive (mayconsume, cmsg); consume (cmag) 2 | ull) void main() eate mailbox (mayproduce) ; eraate mailbox (mayecnsuma| for (int i= 1 i <= capacitys i+) send (mayproduce, null); pazbegin (producer, conswzez) ; Figure 5.21 A Solution to the Bounded-Buffer Producer/Consumer Problem Using Messages 

صفحه 54:
(3 Problem ° Any number of readers may simultaneously read the file ° Only one writer at a time may write to the file ° If a writer is writing to the file, no reader may read it 

صفحه 55:
55 /۰ program readersandwriters */ int readzount semaphore x = 1, wsem = 1; void reader () 1 if (readcount == 1) semvait (wsem) 7 semsignal (x); READUNIT() ; if (readcount ‘semSignal (sem); semSignal (x)+ void writer() 1 while (true) 1 : semvait (sem): WRITEUNIT (); semsignal (wsem); 1 void main () ١ = parbegin (reach > Figure $22 A Solution to the Readers/Writers Problem Using ‘Semaphores: Readers Have Priority 

صفحه 56:
56 nile (rue) ‘readeountt+s ‏ل‎ 5 777 207 لقتو هيوق 1 ‎Vota weiter 0‏ Figure §.23 A Solution to the Readers/Writers Problem Using ‘Semaphores: Writers Have Priority