- What is a Process?
- 3 Issues with Sharing
- Carl’s Jr. Restaurant
- Algorithmic approach
- Software Primitives
- Concurrent Programming Construct
- Condition Variables
- Producer-Consumer Problem
- Recommended reading
What is a Process?
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
- How to
- How to ensure threads in a process,
executes oneat a time?
- How to ensure proper
To understand it better, lets take a real world example
Carl’s Jr. Restaurant
- Customer arrives
- Employee takes order
- Employee cooks food
- Employee bag food
- Employee takes money
- 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
3 issues in current situation
- What is shared data? - In step 2-3, Quantity of food. In step 3-4, how much food to bag
- 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
More formally there are three types of solution categories
- Algorithmic approach
- Software Primitives
- Concurrent programming construct
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
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.
It is a shared integer variable with
non-negative values that have
initialization, wait and signal as a indivisible operation.
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
Concurrent Programming Construct
Locks can only solve
mutual exclusion problem, they can not solve
sequencing problem. We need another mechanism
Monitors is a programming language construct that supports both data access synchronization and control synchronization.
Monitors have 3 parts
Lockfor mutual exclusion
- 1 or more
condition variablesfor sequencing
- Monitor variables for make sequencing decisions -> Shared data
Each condition variable is only associated with one lock.
Lets consider we have
monitor variable => int itemCount = 0;
monitor lock => monitorLock;
monitor condition => needItem;