lecture note 

NOS  (nut operating system)


basic OS concepts

process

A process is a basic unit of abstraction to build concurrent execution of multiple programs.  A process is a sequential program in execution.  A program is a "static" part whereas a process is a dynamic part.  One program can be executed by many processes.  A process consists of :  code segment, data segment, stack segment.  They can be shared or separated.  When they are shared, only a single address space is needed hence the implementation is simple.  

Threads and Objects are alternatives to Process in many OS.

To achieve concurrency using one processor, each process will be allocated a slice of time for its execution.  All processes will be scheduled to be executed by time multiplexing.  For example two processes A, B.  They will be executed like this:

A B A B A B A B

A simple programming abstraction to achieve this is "co-routine" where A call B, B call A by not starting A at the beginning but resume the execution at the point where A has stopped.

To manage multiple programs, a scheduler keeps a list of all processes.  When starting an execution of a time slice, a process will be selected to be run according to some policy.   A process is run until it is:
1 time-out   using up its alloted time
2 blocked    the process requests a resource and has to wait for it.
3 terminated   the process runs to its completion.

We can model the behaviour of the process as follows:

state                   event                     next state

READY        task-switch    RUNNING
RUNNING      time-out       READY
RUNNING      terminate      DEAD
RUNNING      block          WAIT
WAIT        wakeup          READY

To execute a process on a processor, computation state, i.e.  all variables pertain to that process must be save/restore properly upon task switching.  These are pc, fp, sp, including separate stack segment for each process.  Code segment is naturally shared. Data segment can be shared using single address space.  These information is stored in a process descriptor (or called process control block etc.).  Task-switch is defined as:

task-switch
   if only one process do nothing  // do not switch
   save current state, set it to READY
   select next process
   make it runnable, set it to RUNNING

To understand how a process requests a resource we first study how a resource is shared.

Semaphore

In sharing a resource, it is necessary to ensure "mutual exclusion".  That is, during a period of one process using that resource, other process that also want that resource must wait.  Diskjstra invented "semaphore" (1972?) to achieve this "mutex" behaviour.   A semaphore is a variable (can be binary, 0/1 or an integer) associated with a resource, indicates availability of the resource to the process that requested it.  Two operations are defined on a semaphore: wait, signal  (originally Diskjstra called it P, V).  Associated with each semaphore is a waiting list of the process that wait on this semaphore.  They are defined as follows:

Wait sem
   if value of sem <= 0
      block this process, set it to WAIT
      put this process to waiting list of this sem
  else
      sem - 1

Signal sem
   if there is process waiting for this sem   
      move that process out of waiting list      
      wakeup that process
   else
      sem + 1

These two operations must be atomic, that is, they must run to completion without interruption.  (can not task switch in between)

How to use a semaphore

For resource sharing, we can let only one process to acquire it, all other processes that request that resource will be waiting in the waiting list.  This is called "monitor".  The code where this mutual exclusion is required is said to be "critical section".  A semaphore is used to protect this section.  Start with sem = 1

....
// critical section
wait sem
... code to access shared resource
signal sem

The first process that acquires this section will "close the door".  After it finishes with this section, it "open the door" to let other process in.  

A semaphore is the basis that other mechanism can be built such as process synchronisation or process communication.  

Process synchronisation

Two processes need to be "synchronise" at some point in the program.  Two semaphores are used to achieve it.  Let two processes A, B.  Assume A arrives to the sync point before B.  Then A must wait for B and vice versa if B arrives before A.

A                         B

signal sem1        wait sem1
wait sem2          signal sem2

The sequence can be rearranged and the behaviour is still correct:

A                         B

signal sem1        signal sem2
wait sem2          wait sem1

OS support functions call from a user program

To start a process, the interface is "(run (func p1 ... ))".  The "run" command is an OS function to create a process and put it on the READY state waiting to be scheduled to be run.  Of course, "wait" and "signal" are also the OS functions callable from a user program.  

In nut language

 A semaphore is implemented as an array of 2 words.  The first word is the value of semaphore, the second word is a pointer to the waiting list.

(let sem)

(set sem (new 2))  ;; an array[2]

(setv sem 0 1)       ;; set value of sem 1
(setv sem 1 ...)      ;; set waiting list
(vec sem 0)           ;; get value
(vec sem 1)           ;; get waiting list


Homework

Think how to do a synchronisation of more than two processes, n-processes.  How many semaphores are needed?

16 Jan 2005