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 allotted 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
   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.  Dijkstra invented "semaphore" (1965) 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 Dijkstra 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
   value = value - 1
   if value < 0
      block this process, set it to WAIT
      put this process to the waiting list

Signal sem
   value = value + 1
   if value <= 0  
      remove a waiting process from the waiting list      
      wakeup that process

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.   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 enters the critical section will "close the door".  After it exits 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

When two processes want to "synchronise" at some point,  two semaphores can be used to achieve it.  Let two processes be A, B.  Assume A arrives to the synchronise 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, a special call  is made, "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.  "wait" and "signal" are the OS functions callable from a user program.  

In Rz 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.

sem
sem = new(2)    // an array[2]

sem[0] = 1      // set value of sem 1
sem[1] ...      // set waiting list

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

last update  26 Jan 2013