• What is a Process?
• 3 Issues with Sharing
• Carl’s Jr. Restaurant
• Algorithmic approach
• Software Primitives
• Semaphores
• Locks
• Concurrent Programming Construct
• Condition Variables
• Producer-Consumer Problem
• Recommended reading

What is a Process?

Operating system(OS) objective is to keep as many as of the computer resources as busy as possible. It is used to keep track of all the things an OS must remember about the state of user program.

Process is like a box, a complete entity in itself which does a step by step task written in program. More formally it is called program in execution.

Lets consider a very basic operating system with very least complexity. This operating system can run only one process at a time. Since, only one process is working at a time, it may happen that all the resources occupied by process will not be used at the same time. To maximize the resource utilization, we need to have entities running at the same time. For multiple entities, it is logical that either we need to have multiple process running at the same time or light weight multiple entities running inside process as a part of process. Process = Code + Allocated Resources + Book keeping information

Lets explore the second option, now consider process is like a box and it has resources inside the box. We create multiple child of process which is called thread.

Thread is a child of process and hence it will use resources of process. Theoretically, there is no limit on number of child threads a process can have but it seems logical that process should have enough resource for administrative purpose for these threads.

Once there are multiple threads they are going to ask for same resource at the same time. For example, if two children are in one room then they will always fight for same toy. Same applies to threads.

3 Issues with Sharing

1. How to Share data?
2. How to ensure threads in a process, executes one at a time?
3. How to ensure proper sequencing of events?

To understand it better, lets take a real world example

Carl’s Jr. Restaurant

Process

1. Customer arrives
2. Employee takes order
3. Employee cooks food
4. Employee bag food
5. Employee takes money
6. Customer gets food and leaves

If a single employee is doing steps from 1-6 then all other customers have to wait in line and its going to be long wait. Instead, lets have multiple employees for taking order, cook food, bag food, take money. Each of these ‘employees’ are multiple threads on Process ‘Restaurant’. Each thread is responsible for doing specialized task.

Lets associate 3 issues in current situation

1. What is shared data? - In step 2-3, Quantity of food. In step 3-4, how much food to bag
2. Does sequence matters? - Cook can’t cook food until order arrives. Employee can’t bag food until it is cooked. So, sequencing matters.

Shared data can be passed for sharing either using message passing or storing that data in global memory of process and each thread read from that memory location.

The next logical question is how to ensure threads in a process executes one at a time i.e. in exclusion? More formally there are three types of solution categories

1. Algorithmic approach
2. Software Primitives
3. Concurrent programming construct

Algorithmic approach

The algorithmic approach to process synchronization does not use any assistance from the computer architecture or the OS kernel. Instead it uses an arrangement of logical conditions to satisfy the desired synchronization requirements. [Dhamdhere]

• Two process algorithms
• Dekker’s Algorithm
• Peterson’s Algorithm
• n process algorithm
• Bakery’s Algorithm

Software Primitives

A set of software primitives for mutual exclusion e.g Semaphore, Locks etc. were developed to overcome the logical complexity of algorithmic implementations. This is implemented using some special architectural features of computer systems. But, ease of use and correctness still remained the major obstacle in a development of large concurrent systems.

Semaphores

It is a shared integer variable with non-negative values that have initialization, wait and signal as a indivisible operation.

 
 class Semaphore {
     public:
     //Constructor
     Semaphore(char *debugName, int initialValue);
 
     //Destructor
     ~Semaphore();
 
    private:
    int value;
    List *waitQueue;
    char *name;
};

Semaphore(char * debugName, int initialValue) {
    name      = debugName;
    value     = initialValue;
    waitQueue = new List;
}

~Semaphore() {
    delete waitQueue;
}

 
 //P() - Semaphore Wait
 Semaphore::P() {
     //Disable interrupts
     IntStatus oldLevel = interrupt->SetLevel(IntOff);
 
     //Semaphore not available
     while (value == 0) {
     waitQueue->Append((void *)currentThread);
    currentThread->Sleep();
    }

    //Semaphore now availble
    value--;
    (void)interrupt->SetLevel(oldLevel);
}

 
 //Semaphore Signal
 Semaphore::V() {
     Thread *thread;  
 
     IntStatus oldLevel = interrupt->SetLevel(IntOff);
 
     //Remove first thread from wait queue
     thread->(Thread *)waitQueue->Remove();

    if (thread != NULL) {
    scheduler->ReadyToRun(thread);  
    }

    value++;

    (void)interrupt->SetLevel(oldLevel);
}

Locks

The basic idea is to close/acquire a lock at the start of critical section or an indivisible operation and open/release it at the end of the critical section or the indivisible operation.

Locks solves how to ensure threads in a process executes one at a time but not the sequencing problem.

Lock Class

 
 class Lock {
     public:
     Lock (char *debugName);
     ~Lock();
 
     char* getName() { return name; }
 
     void acquire();
    void release();
    bool isHeldByCurrentThread;

    private:
    char*   name;
    List*   lockWaitQueue;
    bool    lockFree;
    Thread* currentLockThread;
};

//Lock Constructor
Lock::Lock(char * debugName) {
    name              = debugName;
    currentLockThread = NULL;
    lockFree          = TRUE;
    lockWaitQueue     = new List;
}

//Lock Destructor
~Lock() {
    delete lockWaitQueue;  
}

 
 Lock::acquire() {
     //Disable interrupts
     IntStatus oldLevel = interrupt->SetLevel(IntOff);
 
     //Check if current thread is an owner
     if (currentThread == currentLockThread) {
     //Already owner  
     (void)interrupt->SetLevel(oldLevel);
    return;
    }

    if(lockFree == TRUE) {
    lockFree = FALSE;
    currentLockThread = currentThread;      
    } else {
    lockWaitQueue->Append((void*) currentThread);
    currentThread->Sleep();
    }

    (void)interrupt->SetLevel(oldLevel);
}

 
 Lock::release() {
     Thread* waitingThread;
     IntStatus oldLevel = interrupt->SetLevel(IntOff);
 
     if (!isHeldByCurrentThread()) {
     //Thread is not valid owner of lock its
     //trying to release
     DEBUG("Not a lock owner");

    (void)interrupt->SetLevel(oldLevel);
    return;      
    }

    waitingThread = (Thread*)lockWaitQueue->Remove();

    if (waitingThread != NULL) {
    scheduler->ReadyToRun(waitingThread);
    currentLockThread = waitingThread;      
    } else {
    lockFree = TRUE;
    currentLockThread = NULL;
    }

    (void)interrupt->SetLevel(oldLevel);
}

bool Lock::isHeldByCurrentThread() {
    return ((currentThread != currentLockThread) ?  FALSE : TRUE);
}

Concurrent Programming Construct

Locks can only solve mutual exclusion problem, they can not solve sequencing problem. We need another mechanism Monitors

Monitors is a programming language construct that supports both data access synchronization and control synchronization.

Monitors have 3 parts

1. Lock for mutual exclusion
2. 1 or more condition variables for sequencing
3. Monitor variables for make sequencing decisions -> Shared data

Condition Variables

Each condition variable is only associated with one lock.

 
 class Condition {
     public:
     Condition(char *debugName);
     ~Conditon();
 
     char* getName() { return name; }
 
     void wait(Lock* conditionLock);
    void signal(Lock* conditionLock);
    void broadcast(Lock* conditionLock);

    private:
    char* name;
    List* cvQueue;
    Lock* cvLock;  
};

Condition::Condition(char * debugName) {
    name    = debugName;
    cvQueue = new List;
    cvLock  = NULL;  
}

Condition::~Condition() {
    delete cvQueue;    
}

 
 void Condition::wait(Lock* conditionLock) {
     IntStatus oldLevel = interrupt->SetLevel(IntOff);
 
     if (cvQueue->isEmpty()) {
     //This lock is now associated with CV and
     //only removed when last entry is removed
     //from cvQueue.
     cvLock = conditionLock;
    }

    if (conditionLock == NULL) {
    interrupt->SetLevel(oldLevel);  
    return;
    }

    conditionLock->release();
    cvQueue->Append((void*) currentThread);
    currentThread->Sleep();

    //Acquire lock when get up
    conditionLock->acquire();
    interrupt->SetLevel(oldLevel);    
}

 
 void Conditon::signal(Lock * conditionLock) {
     IntStatus oldLevel = interrupt->SetLevel(IntOff);
 
     //If nobody to signal, return
     if (cvQueue->Empty()) {
     interrupt->SetLevel(oldLevel);
     return;
     }

    //Verify right lock is signalled
    if (cvLock != conditionLock) {
    interrupt->SetLevel(oldLevel);
    return;
    }

    thread = cvQueue->Remove();
    if (thread != NULL) {
    scheduler->ReadyToRun(thread);
    }

    if (cvQueue->isEmpty()) {
    cvLock = NULL;
    }

    interrupt->SetLevel(oldLevel);
}

Producer-Consumer Problem

Lets consider we have infinite buffer

monitor variable => int itemCount = 0;
monitor lock => monitorLock;
monitor condition => needItem;

 
 while (true) {
     monitorLock.acquire();
 
     //Produce item
     //Put in a buffer
     itemCount++;
 
     needItem.signal(&monitorLock);

    monitorLock.Release();    
}

 
 while (true) {
     monitorLock.acquire();
 
     while(intemCount == 0) {
     needItem.wait(&monitorLock);      
     }
 
     //Buffer has atleast one item
    itemCount--;

    monitorLock.Relase();
}

Recommended reading

• Implementing CV using semaphore
• Monitors by C.A.R Hoare
• Process synchronization in Linux Kernel