Operating System Process Management - 4 Monday, August 11, 2008

Roadmap Process Concepts Process Scheduling Interprocess Communication Mutex and Synchronization Classical IPC Problems Threads 8/11/2008 6:14 PM bettynj@gmail.com

Classical Problems of IPC Bounded-Buffer Problem Readers and Writers Problem Dining-Philosophers Problem 8/11/2008 6:14 PM bettynj@gmail.com

Readers-Writers Problem This is the same as the Producer / Consumer problem except - we now can have many concurrent readers and one exclusive writer. Locks: shared (for the readers) exclusive (for the writer). Two possible ( contradictory ) guidelines can be used No reader is kept waiting unless a writer holds the lock (the readers have precedence). If a writer is waiting for access, no new reader gains access (writer has precedence). 一个数据对象（如文件或记录）可以为多个并发进程所共享。其中有的进程只需要读共享对象的内容，而其他进程可能要更新（即读和写）共享对象。为了区分这两种类型的进程，将只对读感兴趣的进程称为读者；而其他得则称为写者。 显然，如果两个读者同时访问共享数据对象，那么不会产生什么不利的结果。然而，如果一个作者和其他一些进程（读者或作者）同时访问共享对象，很可能产生混乱。 8/11/2008 6:14 PM bettynj@gmail.com

Readers-Writers Problem do { wait( wrt ); /*writing is performed*/ signal( wrt ); } while(TRUE); BINARY_SEMAPHORE wrt = 1; BINARY_SEMAPHORE mutex = 1; int readcount = 0; Reader: do { wait( mutex ); /* Allow 1 reader in entry*/ readcount = readcount + 1; if(readcount == 1) then wait(wrt ); /* 1st reader locks writer */ signal( mutex );   /* reading is performed */   wait( mutex ); readcount = readcount - 1; if(readcount == 0) then signal(wrt ); /*last reader frees writer */ } while(TRUE); 为了确保不会产生混乱，要求作者对共享对象有完全的访问。 信号量wrt为读者和写者进程所共用，供写者作为互斥信号量使用。 信号量mutex用于确保在更新变量readcount时的互斥。 变量readcount用来跟踪有多少进程正在读对象。 8/11/2008 6:14 PM bettynj@gmail.com

Dining-Philosophers Problem Description: 5 philosophers with 5 chopsticks sit around a circular table. They each want to eat at random times and must pick up the chopsticks on their right and on their left.  Clearly deadlock is rampant ( and starvation possible.) 假设有5个哲学家，他们花费一生中的时光思考和吃饭。这些哲学家共用一个圆桌，每个哲学家都有一把椅子。在桌子中间是一碗面，在桌子上放着5只筷子。当一个哲学家思考时，他与其他同事不交互。时而，哲学家会感到饥饿，并试图拿起与他相近的两只筷子（他与邻近左、右两人之间的筷子）。一个哲学家一次只能拿起一支筷子。显然，他不能从其他哲学家手里拿走筷子。当一个饥饿的哲学家同时有量只筷子时，他就能不用释放他的筷子而自己吃了。当吃完后，他会放下两只筷子，并再次开始思考。 解决方法：每只筷子都用一个信号量来表示。一个哲学家对信号量执行wait操作试图夺取相应的筷子；他会通过对适当信号量执行signal操作以释放相应的筷子。 8/11/2008 6:14 PM bettynj@gmail.com

A nonsolution to the dining philosophers problem 8/11/2008 6:14 PM bettynj@gmail.com

Dining-Philosophers Problem Several solutions are possible: Allow only 4 philosophers to be hungry at a time. Allow pickup only if both chopsticks are available. ( Done in critical section ) Odd # philosopher always picks up left chopstick 1st, even # philosopher always picks up right chopstick 1st. 8/11/2008 6:14 PM bettynj@gmail.com

Solution - 2 monitor dp { enum {thinking, hungry, eating} state[5]; condition self[5]; } Solution - 2 void putdown(int i) { state[i] = thinking;// test left & right neighbors test((i+4) % 5); test((i+1) % 5); } void philosopher(int i) { while(true){ thinking(); pickup(i); eating(); putdown(i); } void pickup(int i) { state[i] = hungry; test[i]; if (state[i] != eating) self[i].wait(); } void test(int i) { if ( (state[(i + 4) % 5] != eating) && (state[i] == hungry) &&(state[(i + 1) % 5] != eating)) { state[i] = eating; self[i].signal(); } initializationCode() { for ( int i = 0; i < 5; i++ )state[i] = thinking; } 8/11/2008 6:14 PM bettynj@gmail.com

Windows 2000 Synchronization Kernel threads synchronization Uses interrupt masks to protect access to global resources on uniprocessor systems. Uses spinlocks on multiprocessor systems. Other threads synchronization Also provides dispatcher objects used as sychronization mechanisms. Dispatcher objects include timer objects, event objects, semaphore objects, mutex objects, and thread objects. 8/11/2008 6:14 PM bettynj@gmail.com

Keystone Different kinds of tools for sychronization , including semaphores, critical regions and monitors The bounded-buffer problem and solution The readers-writers problem and solution The dining-philosophers problem and solution 8/11/2008 6:14 PM bettynj@gmail.com

Homework The Sleeping-Barber Problem: A barbershop consists of a waiting room with n chairs and the barber room containing the barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write a program to coordinate the barber and the customers. 8/11/2008 6:14 PM bettynj@gmail.com

Classical IPC Problems Operating System Classical IPC Problems Monday, August 11, 2008