Introduction Processes Inter Process Communication Deadlocks Memory Management

File Systems Protection and Security I/O Systems

We are what we repeatedly do.
Excellence, then, is not an act, but a habit.

					Aristotle

1. Race Conditions and Critical Sections

   Too much milk problem ( Adopted from Barton P. Miller's Lecture notes )

   	Person A	Person B
   3:00 3:05 3:10 3:15 3:20 3:25 3:30	Look in fridge. Out of milk. Leave for store. Arrive at store. Leave store. Arrive home, put milk away.	Look in fridge. Out of milk. Leave for store. Arrive at store. Leave store. Arrive home. OH NO!

   What does correct mean?

   Synchronization: the use of atomic operations to ensure the correct operation of cooperating processes

   race conditions

   shared resource -- critical resource

   Mutual exclusion: Mechanisms that ensure that only one person or process is doing certain things at one time (others are excluded). E.g. only one person goes shopping at a time.

   Critical section: A section of code, or collection of operations, in which only one process may be executing at a given time. E.g. shopping. It is a large operation that we want to make "sort of" atomic.

   There are many ways to achieve mutual exclusion. Most involve some sort of locking mechanism: prevent someone from doing something. For example, before shopping, leave a note on the refrigerator.

   Three elements of locking:

   1.	Must lock before using.	leave note
   2.	Must unlock when done.	remove note
   3.	Must wait if locked.	do not shop if note

   1st attempt at computerized milk buying:

   Processes A & B
   1 2 3 4 5 6 7	if (NoMilk) { if (NoNote) { Leave Note; Buy Milk; Remove Note; } }

   Does this work?

   What happens if we leave the note at the very beginning: does this make everything work?

   2nd attempt: Change meaning of note.

   A buys if there is no note, B buys if there is a note. This gets rid of confusion.

   	Process A	Process B
   1 2 3 4 5 6	if (NoNote) { if (NoMilk) { Buy Milk; } Leave Note; }	if (Note) { if (NoMilk) { Buy Milk; } Remove Note; }

   • Does this work?
   • How can we tell?
   • When dealing with complex parallel programs, we cannot rely on our intuitions or informal reasoning. We need to prove that the programs behave correctly. What can we say about the above solution?

   Suppose B goes on vacation. A will buy milk once and will not buy any more until B returns. Thus this really does not really do what we want; it is unfair, and leads to starvation.

   3rd attempt: Use 2 notes:

   	Process A
   1 2 3 4 5 6 7	Leave NoteA; if (NoNoteB) { if (NoMilk) { Buy Milk; } } Remove NoteA;

   Process B is the same except interchange NoteA and NoteB.

   What can we say about this solution?

   Solution is almost correct. We just need a way to decide who will buy milk when both leave notes (somebody has to hang around to make sure that the job gets done).

   4th attempt: In case of tie, A will buy milk:

   Process B stays the same as before.

   	Process A
   1 2 3 4 5 6 7 8 9 10 11 12 13 14	Leave NoteA; if (NoNoteB) { if (NoMilk) { Buy Milk; } } else { while (NoteB) { DoNothing; } if (NoMilk) { Buy Milk; } } Remove NoteA;

   How do we know this is correct?

   This solution works. But it still has two disadvantages:

   • A may have to wait while B is at the store.
   • While A is waiting it is consuming resources (busy-waiting).

   Good solution requirements of mutual exclusion

   No two processes may be simultaneously inside their critical section
   Independent of CPU speed and # of CPU
   No process running outside its critical section should block any process
   Bounded waiting

2. Mutual Exclusions
   Disabling interrupts

   
   when a process enters a critical section, it disables all interrupts

   problem: if a process forgot to turn on interrupts, other processes can't be executed

   mulitprocessing -- time-consuming and difficult to disable all interrupts

   Two-process solutions

   only 2 processes: P0, P1

   strict alternation

   turn = 1 => P1
   turn = 0 => P0

   P0		P1
   while ( 1 ) { while ( turn != 0 ) ; //wait critical_section(); turn = 1; //P1's turn now non_critical_section(); }		while ( 1 ) { while ( turn != 1 ) ; //wait critical_section(); turn = 0; //P0's turn now non_critical_section(); }

   The non_critical_section() of say P1 could be very long. This may lead to P0 blocking itself.

   Peterson's Solution

   P0		P1
   //global variables int wait; //0 or 1 int interested[2]; //interested to enter C.S.
   void enter_region0() { interested[0] = 1; //P0 interested in C.S. wait = 0; //P0, please wait first while ( wait == 0 && interested[1] ) ; //wait, if the other is interested } void leave_region0() { //P0 leaving C.S. interested[0] = 0; }		void enter_region0() { interested[1] = 1; //P1 interested in C.S. wait = 1; //P1,please wait first while ( wait == 1 && interested[0] ) ; //wait, if the other is interested } void leave_region1() { //P1 leaving C.S. interested[1] = 0; }

   Before entering its critical seciton, each process calls enter_regionid() with its own process id. This call will cause it to wait, if need be, until it is safe to enter.

   Multiple-process solutions

   Lamport's Bakery Algorithm

   • get a ticket number to purchase baked goods
   • if two processes pick the number at the same time, it does not gaurantee two processes have different #
   • if number( Pi ) < number ( Pj ) serve Pi first
   • if number ( Pi ) = number ( Pj ), then check i, j ( unique process ids ); if i < j, then serve Pi first
   • The notation (a,b) < (c,d) is defined as (a < c) or (a = c and b < d)

     Process i
     

     boolean choosing[n]; int number[n]; while (true) { choosing[i] = true; //picking a number //max ( number[0], ..., number[n-1] ) + 1 number[i] = 1 + getmax( number[], n ); choosing[i] = false; //finished picking a number for (int j=0; j < n; j++ ) //check with others { while ( choosing[j] ) //don't do anything while someone ; //is choosing a # while (( number[j]!=0 ) && ( number[j],j) < ( number[i],i )) ; //check if process j has higher priority //( lower # ) } critical_section(); number[i] = 0; //reset non_critical_section(); }

   Use TSL Instruction

   • help from hardware
   • Test-and-Set Lock ( atomic action, i.e. indivisible )
   • Use flag ( lock ) to coordinate access to shared memory, set to 1 by TSL

     while ( 1 ) { test_and_set(); //lock ← 1; wait if necessary critical_section(); reset(); //lock ← 0 } test_and_set: TSL register, lock //register ← lock, lock ← 1 CMP register, #1 //is lock = 1 ? JE test_and_set //yes, C.S. forbiden, wait RET reset: MOV lock, #0 //lock ← 0 RET

3. Semaphores

   o A semaphore S is an integer variable, apart from initialization is accessed through standard atomic operations:

   wait ( S ): waits for semaphore S to become positive, then decrements it by 1. ( or down( S ) )
   signal ( S ): increments semaphore S by 1.( or up ( S ) )

   void wait ( int S ) { //atomic while ( S <= 0 ) ; //wait S = S - 1; } void signal ( int S ) { //atomic S = S + 1; }

   o invented by Dijkstra in 1965

   o Semaphores are simple and elegant and allow the solution of many interesting problems. They do a lot more than just mutual exclusion.

   o Binary semaphores are those that have only two values, 0 and 1. They are implemented in the same way as regular semaphores except multiple signal()s will not increase the semaphore to anything greater than one.

   o Semaphores are not provided by hardware. But they have several attractive properties:

   Machine independent.
   Simple.
   Powerful. Embody both exclusion and waiting but do NOT need to be busy waiting
   Correctness is easy to determine.
   Work with many processes.
   Can have many different critical sections with different semaphores.
   Can acquire many resources simultaneously (multiple P's).
   Can permit multiple processes into the critical section at once, if that is desirable.

   o Here is an example of how semaphores are used to enforce mutual exclusion:

   //n processes share semaphore mutex ( mutual exclusion ) Semaphore mutex; //initialized to 1 while ( 1 ) { wait ( mutex ); critical_section(); signal ( mutex ); non_critical_section(); }

   o When a process executes the wait() operation and finds that the semaphore value is not positive, it must wait.

   However, rather than busy wiating, the process can block itself ( sleep ); places itself into a waiting queue associated with the semaphore, and the state of the process is switched to the sleeping state ( blocked state ). The transfer is controlled to the CPU scheduler, which selects another process to run. The sleeping process is restarted by a signal ( wakeup ).

   Example

   In figure A, there are three semaphores: S1 has a value of zero and process P1 is blocked on S1; S2 has a value of three, meaning three more processes may execute a down operation on S2 without being put to sleep; S3 has a value of zero, and has two sleeping processes, P4 and P5, blocked on it.

   

   Now let us look at what happens when a process executes an UP on S1. In figure B, process P1 is activated by an UP operation. It executes a DOWN on S1 and enters its critical section. The state of the semaphores after these actions has now changed.

   

   o C implementation

   typedef int process; typedef struct { int count; process Q[MAX_P]; //a queue of processes } Semaphore S; Semaphore S; void wait ( Semaphore S ) //atomic { if ( S.count > 0 ) //no need to wait --S.count; else { add_process ( S.Q ); //add this process to S.Q sleep(); //block reschedule(); } } void signal ( Semaphore S ) //atomic { if ( isEmpty( S.Q ) ) { //no waiters to wake up ++S.count; } else { P = delete_process ( S.Q ); //delete a process P from S.Q wakeup ( P ); //e.g. put P in a ready list ++S.count; reschedule(); //depends on priority of P and //currently running process } }

   o A Java implementation

   Click here to see.

4. Monitors high-level synchronization,
   consists of procedures, shared resources, and administrative data
   only one process can be active inside a monitor
   procedures of monitor can only access data inside monitor
   local data of monitor cannot be accessed from outside
   
   When a task attempts to access a monitor method, it is put in the monitor's entry queue.
   A condition variable is not a variable at all. In fact it is just a queue that is part of the monitor. Sometimes these are called event queues or variable queues. A condition variable queue can only be accessed with two monitor methods associated with this queue. These methods are typically called wait and signal. The signal method is called notify in Java.
   A task that holds the monitor lock may give it up and enter a condition variable queue by executing the corresponding wait method.
   A task that holds the monitor lock may revive a task waiting in a condition variable queue with the notify method of that queue.
   The notify method removes one task from the condition variable queue if the queue is not empty.
   Processes in the monitor queues are waiting to acquire the monitor lock.
   When a task is removed from one of the condition variable queues, it is put in the waiting queue.

   Weakness:

   1. one process active inside monitor => defeats concurrency purpose
   2. nested monitor calls --> deadlock

   Java Synchronization ~ monitor
   An Example : Producer-Consumer Problem

   

5. Message Passing

   send ( P, &message ); //send a message to process P receive ( Q, &message );//receive a message from Q

   

   A communication link has to satisfy the following properties:

   • Processes only need to know each other's identity to communicate.
   • Exactly one link between 2 processes.
   • Link may be unidirectional but usually bidirectional.
     Point-to-Point
     Broadcast

     Example: Producer-consumer problem

     #define N 100 //# of slots in buffer void producer() { int item; message m; //message buffer ( ~plate ) while ( true ) { produce_item ( &item ); //generate something to put in buffer receive ( consumer, &m ); //wait for an empty buffer to arrive build_message ( &m, item ); //construct a message to send send ( consumer, &m ); //send item to consumer } } void consumer() { int item, i; message m; //buffer to hold a message for ( i = 0; i < N; i++ ) //send N empty buffers ( slots ) send ( producer, &m ); while ( 1 ) { receive ( producer, &m ); //get message containing item extract_item ( &m, &item ); //take item out of message send ( producer, &m ); //send empty buffer reply consume_item ( item ); //consume item } }

   indirect communication

   mailbox ( in UNXI, this is called pipes )

   send ( A, &message )     //send a message to mailbox A

   receive ( A, &message )     //receive a message from mailbox A

   • zero buffering
     no buffer
     sender must wait ( block ) until receiver receives a message ( and vice versa )
     i.e. rendezvous
     if exchanged information is crucial for the computation, sender must be sure message received
     acknowledgement

     e.g. process P → process Q

     send ( Q, &message );
     receive ( Q, &message );

     receive ( P, &message );
     send ( P, "acknowledgement" );

     Remote Procedure Call ( RPC )

     

     ---

     stub procedures

     

6. A Classical IPC problem

   The dining philosophers problem ( Dijkstra, 1965 )

   

   Analysis

   
   • chopsticks -- shared resources
   • neighbours may compete for chopsticks -- race conditions; so use a binary semaphore mutex to protect the usage of chopstics

   //philosopher i while ( true ) { think(); wait ( mutex ); //first check if someone is eating take_chops( i ); //take left chopstick take_chops((i+1)%5); //take right chopstick eat(); put_chops( i ); //put down left chops put_chops( (i+1)%5); //put down right chops signal( mutex ); //wake up anyone who's waiting }

   O.K. It works! But what's the drawback of the above algorithm?

   Improvement:

   • Use mutex lock to protect each chopstick rather than eating

     deadlock

     

     starvation

     
   • Use an array, state to keep track of whether a philosopher is eating, thinking, or hungry.

     //philosopher i #define LEFT ( i - 1 ) % 5 #define RIGHT ( i + 1 ) % 5 typedef int semaphore; semaphore s[5] = {0, 0, 0, 0, 0}; semaphore mutex = 1; void philosopher ( int i ) { while ( 1 ) { think(); pickup ( i ); //pick up chops eat(); putdown( i ); //put down chops } } void pickup( int i ) { wait ( mutex ); state[i] = HUNGRY; test ( i ); //try to get yourself into EATING state signal ( mutex ); wait ( s[i] ); //block if chops were not acquired } void putdown ( int i ) { wait ( mutex ); state[i] = THINKING; test ( LEFT ); //test left, signal her if she's waiting test ( RIGHT ); //test right, signal her if she's waiting signal ( mutex ); } void test ( int i ) { if ( state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING ) { state[i] = EATING; //O.K., you can eat if your neigbour's aren't signal ( s[i] ); //now your state is eating, so others cannot eat //you can wake up those waiting on s[i] } }