Concepts with Symbian OS (779878), страница 26
Текст из файла (страница 26)
The intent of this kind of syntax is to guardagainst programmer errors associated with manipulating semaphores.This abstraction takes away the semaphore manipulation and focuses onsyntax.Another form of abstraction that hides semaphores is a monitor. Amonitor is a programming language construct similar to a class or otherobject-oriented abstraction. In object-oriented languages, classes are an1This and other examples of code are written in a fictitious enhancement to C++. Thereis no ‘shared’ keyword, for example, but I explain the syntax and it should be clear whatthe code is used for.120PROCESS CONCURRENCY AND SYNCHRONIZATIONencapsulation of data definitions and the procedures that operate onthose definitions.
A monitor is an extended definition of a class whereany use of a monitor’s operation guarantees atomicity with respect to thedata items defined in the monitor. Consider the following specification ofa monitor:public monitor concurrentQueue{int queue[];int head, tail;concurrentQueue() { // constructor code }void enqueue(int aQueueItem) { ... }int dequeue() { ... }int length() { ... }}This example is certainly not that mysterious; you could replace thekeyword ‘monitor’ with the keyword ‘class’ and have a class specificationwritten in Java.A monitor is implemented with semaphores and critical sections.
Useof a monitor’s methods implies locking the data items defined in themonitor’s declaration first, then making the method call. The data itemsneed to be unlocked just before the method returns. And locking, as westated previously, can be implemented with semaphores. So again wehave semaphores as the basis for higher-level abstractions.The concepts we have just discussed – such as critical regions andmonitors – were developed as experimental concepts by researchers trying to understand how best to program with concurrent processes inan operating system.
Some of the first researchers in this field were PerBrinch Hansen and C.A.R. Hoare. These scientists invented new languages or augmented existing ones so that they could experiment withhow these new constructs worked. Languages such as Concurrent Pascalrepresented existing languages (Pascal) that were augmented and Mesaand CSP (and later, Occam) were new languages influenced by theirwork.6.4 The Dining Philosophers: A Classic ProblemA classic problem in concurrency has to do with five philosophers sittingaround a table. These five philosophers have nothing to do except eatTHE DINING PHILOSOPHERS: A CLASSIC PROBLEM121RICEFigure 6.1The philosophers’ dining tableand think.
They can think on their own, but to eat, they need a sharedbowl of rice and two chopsticks. The table is built so that each of the fivephilosophers has a single chopstick to her left and right, shared by thephilosophers to the left and right (see Figure 6.1).The problem is that a philosopher cannot eat unless she has twochopsticks. This has several implications. If a philosopher is eating, thenher neighbors cannot eat. If a philosopher picks up one chopstick, buther neighbor has also picked up one, then she cannot eat. The goal inthis problem is to allow every philosopher to go through eat–think cycleswithout starvation.The obvious solution is shown in the following code:while (true){think();take_chopstick(i);take_chopstick(i+1 % 5);eat();drop_chopstick(i);drop_chopstick(i+1 % 5);}The call to take_chopstick(i) waits until the specified chopstick isavailable and then takes it.
This is obvious … but wrong. There are severalreasons why this obvious solution does not solve the problem. First, consider the example we just mentioned. If the first several statements wereinterleaved with each other, it is possible that take_chopstick(i) isinterleaved with all the others before the next statement is executed. The122PROCESS CONCURRENCY AND SYNCHRONIZATIONresult is deadlock, as all the philosophers wait for each other to give upa chopstick.
Secondly, consider a scenario where philosophers are ableto eat and take chopsticks during the time their neighbors are thinking.Then, while their neighbors wait, they put down the chopsticks, thinkand try to eat again. The result is that several philosophers starve. This isdefinitively not a desirable situation.We can see starvation in another solution. Let’s say that each philosopher, after thinking and taking her left chopstick, checks to see if the rightchopstick is available. If it is, she takes the chopstick and eats. If it is not,she puts down the left chopstick, waits for a time and repeats the process.This repeats until a chopstick is available. Unfortunately, starvation iseven more probable in this scenario.
If the neighbors can eat and thinkfaster than the philosopher’s checking time, then the philosopher nevergets to eat and starves.The proper solution to this problem uses semaphores to define a criticalsection. To start with, we can define a semaphore – call it ‘utensils’ – thatis used to enter a critical section. Before a philosopher can start acquiringchopsticks, she performs wait(utensils) and when she is done withthe chopsticks, she performs signal(utensils).
This protects thecritical section comprised of taking chopsticks, eating and replacing thechopsticks and ensures that no philosopher starves and that everyoneeats. The act of eating is now serializable.Unfortunately, this is a bad solution with regard to performance.With this solution, only one philosopher eats at a time, even thoughothers are ready and could eat without bothering each other.
The propersolution adds a semaphore for each chopstick. The chopsticks must stillbe checked and taken in a critical section, however. This ensures thatstarvation does not occur. A proper specification for this last version isgiven in Section 6.5.There are several classic problems that have developed around processconcurrency. The Dining Philosophers’ problem is one of the mostfamous. However, there are others worth thinking about.The reader–writer problem is a problem where a data object is sharedamong several processes. Some processes read from the data object andsome write to the data object. The object of the system is to allow arbitraryreads and writes without corrupting the data.The producer–consumer problem (otherwise known as the boundedbuffer problem) is a problem where a process fills a buffer with data andanother process empties that same buffer.
The buffer is bounded, thatis, it can only contain a specific number of data items. We must guardAN EXAMPLE IN UNIX123the buffer so that consumers cannot read an empty buffer and producerscannot write to a full buffer.6.5 An Example in UnixStandard Unix supports semaphores among other concurrency constructs.Let’s consider what a solution to the Dining Philosophers might look likeon a Unix platform, Solaris. We start with the following main program:#include#include#include#include#include#include#define#define#define#define#define#define<stdio.h><synch.h><signal.h><errno.h><unistd.h><sys/time.h>NLEFTRIGHTTHINKINGHUNGRYEATING5(i-1)%N(i+1)%N012/* NOTE the redefinitions of wait and signal -- with the same semantics.* And "sema_t" will serve as a semaphore.*/#define wait(S)#define signal(S)#define semaphoresema_wait(S)sema_post(S)sema_tsemaphore mutex, s[N];int state[N];main (){int phil[N], status;int i;struct timeval tp;// Set things up by seeding the random number generatorgettimeofday(&tp,&tp);srand(tp.tv_sec);// Next we initialize the semaphore.status = sema_init(&mutex, 1, USYNC_PROCESS, NULL);for (i=0; i<5; i++) sema_init(&s[i], 1, USYNC_PROCESS, NULL);124PROCESS CONCURRENCY AND SYNCHRONIZATION// Now, we create N forks by using a for loop.for (i=0; i<=N-1; i++){if ( (phil[i] = fork()) == 0 ){philosopher(i);break;}}// Finally, we pause to wait for termination of all forks.if (i == 5){for (i=0; i<5; i++) wait(&status);}}Semaphores are defined by the data type of sema_t.
The wait andsignal functions are implemented by sema_wait() and sema_post().We use two types of semaphores (as outlined in Section 6.4): one to guarda critical section and a set to govern the taking of the chopsticks. Thefunction sema_init() is used to give each semaphore an initial value.Each one is a binary semaphore.Unix implements the creation of processes through the fork() systemcall. The fork() call clones the current process’s PCB into two PCBsthat are virtually identical. The only difference between them is that thecall to fork() in the parent returns the process ID for the child process;in the child, it returns 0.
So the code above creates five processes withthe following fragment.The call to the philosopher() function occurs only if the processis a child, when the fork() call returns 0. The following code definesphilosopher(). The definition follows what we outlined in the previous section: a philosopher thinks, picks up chopsticks, eats, and putsthe chopsticks back down.
Eating and thinking amount to sleeping forrandom periods of time./* THINK and EAT -- and sleep random amounts of time (thinking and* eating is hard business).*/AN EXAMPLE IN UNIX125void think(int i){printf("Philosopher #%d is thinking...\n", i);sleep(rand() / 6553);}void eat(int i){printf("Philosopher #%d is eating...\n", i);sleep(rand() / 6553);}// The REAL philosophy business.Think and eat forever.void philosopher (int i){int times=0;while (1){think(i);take_chopsticks(i);eat(i);put_chopsticks(i);}}The real meat of the solution is the implementation of take_chopsticks() and put_chopsticks():// Test to see if neighbors are NOT eating.void test (int i){if ( (state[i] == HUNGRY) &&(state[i-1%N] != EATING) &&(state[i+1%N] != EATING) ){state[i] = EATING;signal(&s[i]);}}/* Take the forks correctly -- if neighbors are NOT eating.
Note the* "down" call as the last line.*/void take_forks (int i){wait(&mutex);126PROCESS CONCURRENCY AND SYNCHRONIZATIONstate[i] = HUNGRY;test(i);signal(&mutex);wait(&s[i]);}/* Put forks down correctly. Change the state to thinking. And enable* the neighbors if, by replacing forks, they can now eat.*/void put_forks (int i){wait(&mutex);state[i] = THINKING;test(i-1%N);test(i+1%N);signal(&mutex);}We implement a ‘state’ of a philosopher as a way to indicate a philosopher’s desire. A philosopher can be EATING, HUNGRY or THINKING.HUNGRY is a desire to be EATING (naturally). The procedure test() isvery important. If the philosopher to the right is not EATING, the currentphilosopher is HUNGRY, and if the philosopher to the left is not EATING,then the current philosopher may eat.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
