Smartphone Operating System (779883), страница 25
Текст из файла (страница 25)
This could occur, for example, ifone process is producing timing data and the other process is reading thatdata and displaying it. Consider, for example, the code below:while (true){while (timing_count == 0) ; // do nothingtiming_data = time_buffer[time_out];time_out = (time_out + 1) % buffer_size;timing_count --;display(timing_data);}The consumer is waiting – doing nothing – until a variable namedtiming_count is greater than zero, which indicates how much timingdata there is in the buffer to be read. This timing data is produced by adata producer that executes code similar to that below:while (true){CONCEPTS AND MODELS FOR CONCURRENCY111while (timing_count == buffer_size) ; // do nothingtiming_data = timer();time_buffer[time_in] = timing_data;time_in = (time_in + 1) % buffer_size;timing_count ++;}These two code fragments run in parallel.
Note that each processshares the time_buffer, which is filled and emptied of time data. Eachprocess keeps its own idea of how much is in each buffer. Finally, notethat the count timing_count is also shared between processes. Thevariables time_out and time_in are private variables and are meantto keep track on a circular basis.
The shared timing_count variable ismeant to indicate how much data is in the buffer that should be displayed.It is easy to demonstrate how these code sections would work togetherwell. For example, if a producer section is run before a consumer section,all objects are shared correctly, as in the sequence of code below (thetime-data producer is in italics and indented):timing_data = timer();time_buffer[time_in] = timing_data;time_in = (time_in + 1) % buffer_size;timing_count ++;timing_data = time_buffer[time_out];time_out = (time_out + 1) % buffer_size;timing_count --;display(timing_data);Even certain interleavings of the code work correctly:timing_data = time_buffer[time_out];time_out = (time_out + 1) % buffer_size;timing_data = timer();time_buffer[time_in] = timing_data;time_in = (time_in + 1) % buffer_size;timing_count --;timing_count ++;display(timing_data);These are ‘macro-style’ interleavings.
That is, they interleave entirestatements, which themselves are comprised of instructions. Interleavingprocess execution ultimately happens at the instruction level. Considerwhat happens if we interleave the instructions that these statements112PROCESS CONCURRENCY AND SYNCHRONIZATIONcomprise a bit differently. Let’s assume that the execution of timing_count ++ and timing_count -- are implemented like this:load register from timing_count locationadd (or subtract) 1 to (or from) registerstore register into timing_count locationNow consider the following interleaving of instructions:load register from timing_count locationadd 1 to registerload register from timing_count locationsubtract 1 from registerstore register into timing_count locationstore register into timing_count locationIf the value of timing_count is 10 at the beginning of this sequence,then the producer sets timing_count to 11 and the consumer sets it to9.
In this case, both values are wrong; the correct result of this interleavingshould leave timing_count at 10.We can see, therefore, that certain interleavings of statements arecorrect and others leave corrupted data. Our goal is to derive ideas aboutparallel execution that allow us to ensure correct manipulation of dataall the time.The Goal: SerializabilityIt is clear that, without proper precautions, data manipulation can onlybe guaranteed to be correct when processes are not concurrent. Thatis, resource corruption cannot occur when only one process at a timeis using the resource. This is a dilemma, however, because, as we sawin Chapter 5, running processes one at a time does not make sense forthe performance of a system.
The goal, then, is to make shared accessto resources look as if it is done sequentially. This property is calledserializability.We must invent ways for processes to cooperate and be coordinatedthat allows concurrency, yet makes access to shared resources look likeserial access. We start to do this by identifying the code sections thataccess shared resources. We call these code sections critical sections.We must coordinate the access these critical sections have to sharedresources so as to adhere to these criteria:CONCEPTS AND MODELS FOR CONCURRENCY113• mutual exclusion : this is a guarantee that, when a process is executinginside a critical section, it is the only one in the critical sectionaccessing the shared resource• no starvation : if a process wants to enter its critical section and noother processes are in their critical sections, then it is eventuallyallowed to do so• bounded waiting : there must be a limit to the number of times otherprocesses can enter their critical sections between the time a processrequests to enter its critical section and the time that request is granted.In other words, we must ensure that our serialization mechanism iseffective, with no starvation and no indefinite postponement.While we consider ways to guarantee these criteria, we must continueto remind ourselves that statements in a program that make up a process’scritical section are actually instructions.
At some point, as we drill downto the machine language making up a program, we have to assumethat something executes without interruption. (If any process can beinterrupted at any time, we can say very little about guaranteeing thecriteria above.) We assume that machine language instructions executewithout interruption – atomically. This means that the execution of oneinstruction completes before the execution of another instruction fromanother process begins.Synchronization of Two ProcessesLet us start our consideration of process synchronization by consideringthe case of only two processes executing concurrently. We branch outfrom this view in the next section, but restricting ourselves to twoprocesses allows us to examine the issues more closely.If we are only looking at two processes, a first solution to sharing aresource might be to take turns by using a turn variable that indicateswhose turn it is.
When the turn variable has a process’s ID, then it isthat process’s turn. The following code shows how this might work:while (true){while (turn != myID) ;// critical section114PROCESS CONCURRENCY AND SYNCHRONIZATIONturn = nextID;// whatever else needs to be done}The process IDs of the two processes involved are stored in myID andnextID. This method ensures some of our criteria but not all of them. Foronly two processes, this method does indeed ensure mutual exclusion:the turn variable can only have one value at a time and changes onlywhen the critical section is complete.
There is also a bound on waiting:when a process is ready to enter its critical section, the other process canenter only once. However, the rule against no starvation is violated: if aprocess is ready to enter its critical section, and the other process is not,the current process can only enter if it is its turn.
A process can starveanother process simply by not taking its turn.The method failed because we did not know enough information aboutprocesses. If we knew whether a process was ready to enter its criticalsection, we might be able to fix this. The following code shows a wayaround this:while (true){ready[myID] = true;while (ready[nextID]) ;// critical sectionready[myID] = false;// whatever else needs to be done}In this method, we establish two flags – an array of Booleans – thatindicate whether a process is ready to enter its critical section. By settinga flag and checking the other process’s flag, a process can implement theidea of taking turns while avoiding starvation.This still does not satisfy all our criteria.
It does indeed satisfy mutualexclusion and goes some way towards meeting the starvation requirement. However, it does not completely work: since the ready flags areset in separate statements, a second process could set its ready flagbetween the two statements before entering the critical section. That is,we could have:CONCEPTS AND MODELS FOR CONCURRENCY115ready[myID] = true;ready[nextID] = true;while (ready[nextID]) ;while (ready[myID]) ;Now both processes are stuck in their waiting loops and each processstarves.The correct solution lies in combining the ideas of both of the previousmethods: take turns, but only if the other process is not ready.
For thissolution, we need both turn variables and ready arrays:while (true){ready[myID] = true;turn = nextID;while (ready[nextID] && turn == nextID) ;// critical sectionready[myID] = false;// whatever else needs to be done}Synchronization of Multiple ProcessesWe have seen a two-process solution; now we need to generalize to amethod that works in a multiple-process environment. There are manymethods of multiple-process synchronization; this topic remains fodderfor many research projects and doctoral dissertations.
Examples includethe colored ticket algorithm, clock algorithms, and many unnamed mutualexclusion algorithms. For further reading, [Lamport 1987] is an excellentpaper that surveys synchronization methods.We outline the bakery method – sometimes called the grocery storeor shop method. The bakery method is based on an algorithm used inbakeries and shops. In these situations, customers organize themselves bytaking a number and waiting their turn until their number is called. Thecustomer with the lowest number is the next to be served. We simulatethis type of behavior:do{116PROCESS CONCURRENCY AND SYNCHRONIZATIONchoosing[pid] = true;number[pid] = max(number[0], ..., number[n-1]) + 1;choosing[pid] = false;for (i=0; i<num_processes; i++){while (choosing[i]) ;// do nothingwhile ( (number[i] != 0) &&( (number[pid], pid) < (number[i], i) ) ) ;}// critical sectionnumber[pid] = 0;// whatever} while (true);We start by picking a number – which we assume is more than allthe other numbers chosen.
However, we cannot guarantee that multipleprocesses do not choose the same number. Then we check all processes,waiting for each to finish choosing and for each to return their number ifit is less. The notation (number[i],i) is meant to convey that eitherthe number chosen is less or the process ID is less (if the number is thesame). To understand that this works, consider that if a process Pi is inits critical section and Pj (where i is not the same as j ) is waiting withan already-selected number then it must be true that (number[i],i) <(number[j],j).In this algorithm, we can see that mutual exclusion is adhered toby observing that when Pi is in its critical section, number[i] !=0. When a second process Pj wants to enter its critical section, then(number[i],i) < (number[j],j). So the algorithm makes Pj waituntil Pi is done and the statement number[pid] = 0 is executed.Notice that processes enter critical sections when they need to, on afirst-come-first-served basis.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
