Smartphone Operating System (779883), страница 27
Текст из файла (страница 27)
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. The semaphores make the entiresolution work.6.6 Concurrency in Symbian OSAs we have stated in previous chapters, Symbian OS supports concurrencybetween processes.
We have also seen how the Symbian OS kernel issupported by the Symbian OS nanokernel. In addition, the Symbian OSarchitecture is essentially that of a microkernel. Therefore, we can expectsynchronization primitives to be implemented in the kernel.For Symbian OS, however, this is not as simple as it may seem.Because of nanokernel support, there are multiple kinds of semaphores,implemented at both levels in the kernel.The most primitive objects are in the nanokernel. The nanokernel’ssupport for synchronization takes the form of two types of objects:mutexes and semaphores. A mutex is essentially a binary semaphore:it has only two states and is designed to implement mutual exclusion between two processes.
A semaphore is a more general form ofa mutex; it can hold values greater than 1, allowing mutual exclusionCONCURRENCY IN SYMBIAN OS127between multiple processes. Both blocking and nonblocking mutexes andsemaphores are supported. The recommended way of using nanothreadsynchronization is through the NKern class, which allows blocking calls.The FMWait() and FMSignal() methods implement blocking synchronization for mutexes; FSWait() and FSSignal() implement suchfunctionality for semaphores. Nonblocking use of these synchronizationobjects is provided through other classes; nanokernel mutexes are implemented in the NFastMutex class and semaphores are implemented inthe NFastSemaphore class. When access is nonblocking, only oneprocess may acquire access through a mutex and all others requestingaccess (say, through a wait() call) are rejected, but not forced to wait.Waiting is expensive to implement and the nanokernel is designedto be as fast as possible.
However, using nonblocking synchronizationmeans that the kernel needs to be locked as the synchronization object ischecked. It also means that if a process wants to implement waiting withnanokernel primitives, it must implement its own wait cycle. This meansthat nonblocking calls are expensive as well. The safest route is to let thekernel handle waiting.Kernel objects in Symbian OS are built on top of nanokernel objects.Thus, the kernel has analogous synchronization primitives: mutexes andsemaphores.
Kernel mutexes are binary semaphores and implement someof the semaphore properties that nanokernel mutexes do not. For example,the versions of wait() and signal() that are implemented for kernelmutexes allow for blocking and queuing: multiple processes may callwait() on a mutex and they block while they wait their turn. It is possibleto hold several kernel mutexes simultaneously. Counting semaphores arealso implemented by the Symbian OS kernel.
As with mutexes, thesesemaphores are blocking and processes may hold multiple semaphoresat once. Mutexes in the kernel are implemented by the RMutex class andsemaphores by the RSemaphore class.There is an interesting issue that applies to synchronization primitivesin Symbian OS: process priority. Process priority and mutexes providean interesting dilemma.
Symbian OS has the property that if processeswith different priorities are waiting for a mutex, then the process withthe highest priority should be next to acquire the mutex when it isreleased. However, if a lower-priority process holds the mutex, then itcan delay a higher-priority process. This is quite undesirable and thedesigners of Symbian OS have installed some mechanisms to keep itfrom happening.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
