Kinesia Online Course
Advanced Operating Systems
Kinesia LLC, 2003

    1. Review and Overview
    2. Deadlocks
    3. Distributed Systems Architecture
    4. Theoretical Foundations
    5. Distributed Mutual Exclusions    		    6. Agreement Protocols
    7. Distributed Resource Management
    8. Distributed Scheduling
    9. Secutiry and Protection
    10. Recovery and Fault Tolerance
         		 

    
The top software developers are more productive than
average software developers not by a factor of 10X or
100X or even 1000X but by 10,000X.

                                        Nathan Myhrvold
    Review and Overview
    1. Process and Threads
    2. Process -- programs in execution, including stacks, memory, resources consumed
      has states : New, Ready, Running, Blocked, Terminated
    3. Concurrent processes -- execution overlaps in time, i.e. second process starts before first completes
      interact with each other through
      1. shared variables
      2. message passing -- two concurrent processes exchange information with each other by sending and receiving messages
    4. Serial processes -- execution of one must be complete before the other can start
    5. Threads -- light weight process ( LWP ), includes PC and stack, shares with peer threads resources

    6. Critical Section resource shared by several processes;
      only one process can enter at a time => mutual exclusion
    7. Mutual Exclusion Mechanisms
    8. Busy waiting -- wasting CPU cycles
    9. Disabling interrupt -- has trouble with multiprocessor systems
    10. Test-and-set lock ( TSL ) -- atomic instruction
    11. Semaphores
    12. integer variables
    13. atomic operations : UP ( V ), DOWN ( P )
      wait:   down ( mutex );
        access_CS();
      signal:   up ( mutex );

      Example

      Let us look at an example of semaphores. 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.

      Weakness
      1. difficult to verify program correctness
      2. difficult to implement, omission of an operation may lead to deadlock
      3. need to know which other processes are using semaphore
    14. Monitors high-level synchronization,
      consists of procedures, shared resources, and administrative data
    15. only one process can be active inside a monitor
    16. procedures of monitor can only access data inside monitor
    17. local data of monitor cannot be accessed from outside
    18. When a task attempts to access a monitor method, it is put in the monitor's entry queue.
    19. 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.
    20. A task that holds the monitor lock may give it up and enter a condition variable queue by executing the corresponding wait method.
    21. A task that holds the monitor lock may revive a task waiting in a condition variable queue with the notify method of that queue.
    22. The notify method removes one task from the condition variable queue if the queue is not empty.
    23. Processes in the monitor queues are waiting to acquire the monitor lock.
    24. When a task is removed from one of the condition variable queues, it is put in the waiting queue.
    25. In the figure below, the arrows show how tasks can move from one queue to another.

      Weakness:

      1. one process active inside monitor => defeats concurrency purpose
      2. nested monitor calls --> deadlock
      Java Synchronization ~ monitor
      An Example : Producer-Consumer Problem

    26. Serializers

      Procedures



      Hollow Region


      ( multiple processes can be active here )
       


      Hollow Region


      ( multiple processes can be active here )
       

    27. Processes can be concurrently active in a hollow region
    28. when a process enters a hollow region, it releases the possession of the serializer to let other processes gain possession join-crowd ( <crowd> ) then <body> ) end
    29. Regain possession of serializer enqueue ( <priority>, <queue-name> ) until ( <condition> )
    30. Weakness
      1. more complex
      2. less efficient
    31. Path Expression indicates the operations order on a shared resource

      path S end
      S : execution history

      ; sequencing -- statement executions are in sequence

      e.g. path open; read; close; end

      + selection -- only one statement can be executed at a time

      e.g. path read + write end
      either read or write, but order doesn't matter       {} concurrency -- concurrent execution e.g. path { read } end
      several read can be executed at the same time
      e.g. path write + { read } end
      either write or several read
      e.g. path { write ; read } end
      at any time, there can be any number of intantiations of path write; read.       Example: readers-writers problem with weak reader's priority ( several readers can read file at the same time but only one writer can write to the file at a time; an arriving reader has higher priority than a waiting writer if reading has occurred, but when reading or writing is done, reader and writer have same priority, i.e. chosen randomly ) path { read } + write end
    32. Communicating Sequential Processes ( CSP ) Use I/O commands for synchronization Input command = <source process id> ? <target variable>

      Output command = <destination process id> ! <expression>

      Concurrent processes :
      [process P1's code||process P2's code|| ..... ||process Pn's code||

      Guarded Command G --> CL
      G -- guard, a boolean expression
      CL -- list of commands

      basically :
      if ( G )
          CL
      evaluate G, if false, ( i.e. guard fails ), CL won't be evaluated

      Alternative command

      G1 -->CL1 G2 -->CL2 ..... Gn -->CLn if all guarded commands fail, then the alternative command fails
      otherwise, one successfully guarded command is selected randomly and executed

      Repetitive command

      *[G1 -->CL1 G2 -->CL2 ..... Gn -->CLn ] repeatedly execute the alternate command until all guarded commands fail --> terminate

      Example

      i := 0; *[ i < size; content(i) &ne n → i := i + 1]

      start with i = 0, then repetitively scan until either i ≥ size or some content( i ) equals n

      Example

      *[c: character; P1 ? c → P2 ! c ]

      ? -- output,   ! -- input

      reads all characters output by process P1 to c which becomes input of process P2

      Weakness of CSP

    33. requires explicit naming of processes in I/O commands
    34. no message buffering; performs I/O blocking => inefficient

    35. The Ada Rendezvous The rendezvous effectively combines mutual exclusion, task, synchronization, and interprocess communication

      Two tasks may rendezvous at once in Ada -- a caller and a server

    36. caller calls an entry in the server, caller waits for accept from server
    37. server when its ready, issues an accept statement to receive the call
    38. when a call has been accepted, rendezvous occurs ( passing parameters )

      server accepts calls from any caller but only one caller may rendezvous with the server, others wait
      First-come-first-served

      Ada Task:

    39. Task specification -- lists interactions of this task with others
    40. Task body -- the set of actions the task performs 

      	task ResourceController is		--task specification
		entry GetControl;
		entry RelinquishControl;
	end  ResourceController

	task body ResourceController is		--body
	begin
	  	loop	
		  accept GetControl;
		  accept RelinquishControl;
		end loop;
	end ResourceController;
	 .
	 .
	 .

      41. similar to CSP
    41. condition ~ guard
    42. several accepts, one of these is selected randomly

      Example: producer-consumer with single buffer 

      	task SingleBuffer is
	  	entry Store ( x:buffer );
		entry Remove ( y:buffer );
	end;

	task body SingleBuffer is
	temp:buffer;				--shared variable
	begin
	loop
		accept Store ( x:buffer );	--Store and remove
			temp = x;		--are executed alternately
		end Store;

		accept Remove ( y:buffer );
			y = temp;
		end Remove;

	end loop
	end SingleBuffer;
      call the accept statement : producer process p calls SingleBuffer.Store( a );
      consumer process c calls SingleBuffer.Remove( b );

      select -- make tasks to accept calls in a more flexible way 

      	select
		when Condition 1 => accept Entry 1
			statements;
		or when Condition 2 => accept Entry 2
			statements;
		or
		 .
		 .
		 .
		else
			statements;	
	end select

      Example: producer-consumer with bounded buffer 

      	task bounded-buffer is
	  entry store( x:buffer );
	  entry remove( y:buffer );
	end;

	task body bounded-buffer is
	  ring:[0..9] of buffer;
	  head, tail: integer;
	  head = 0;
	  tail = 0;
	  begin
	  loop
	    select
		when tail < head + 10 = >	--queue not full yet
		accept store( x:buffer );
		  ring[tail mod 10] = x;	--put item in buffer
		  tail = tail + 1;		--next slot
		end store;
	    or
		when head < tail = >		--queue not empty
		accept remove( y:buffer );
		  y = ring[head mod 10];	--get item from ring
		  head = head + 1;		--next slot
		end remove;
	    end select;
	  end loop
	end bounded-buffer;

      Simulating path expressions in Ada 

      	entries A, B
	  B must follow A:
		accept A;
		accept B;

	  specifying either A or B ( not both ) can be executed:
		select
		  when ( x > 0 ) = >
		    accept A;
		or
		  when ( x <= 0 ) = >
		    accept B;
		end select;

	  specifying any number ( including 0 ) of calls to A:
		loop
		  select
		    when ( x > 0 ) = >
			accept A;
		    else
			exit;
		  end select;
		end loop