This post is all about very simplistic approach towards process and process synchronization.
Process is like a box, a complete entity in itself which does a step by step task written in progam. More formally it is called program in execution.
To understand it better, lets take a real world example
Process
The next logical question is, How to ensure threads in a process, executes on at a time?
Semaphore Constructor
Semaphore Destructor
Semaphore Wait
Semaphore Signal
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
CV Constructor
CV Destructor
CV Wait
CV Signal
monitor variable => int itemCount = 0;
monitor lock => monitorLock;
monitor condition => needItem;
Producer
Consumer
Table of Contents
What is a Process?
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 = Code + Allocated Resources + Book keeping information
Process is like a box, a complete entity in itself which does a step by step task written in progam. 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. When its said 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.
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 resource Process have. 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 Share data?
- How to ensure threads in a process, executes on at a time?
- How to ensure proper sequencing of events?
To understand it better, lets take a real world example
Carl’s Jr. Restaurant
Process
- 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 specialized task.
Lets associate 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 distributed 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 on at a time?
More formally there are three types of solution categories
- Algorithmic approach
- Software Primitives
- 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.
Semaphore Constructor
Semaphore Destructor
Semaphore Wait
Semaphore Signal
Locks
The basic idea is to close a lock at the start of critical section or an indivisible operation and open it at the end of the critical section or the indivisible operation.
Locks solves, How to ensure threads in a process, executes on at a time? but not the sequencing problem.
Lock Constructor
Lock Destructor
Lock Acquire
Lock Release
Lock Owner
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
- Lock for mutual exclusion
- 1 or more condition variables for sequencing
- Monitor variables for make sequencing decisions -> Shared data
Condition Variables
Each condition variable is only associated with one lock.CV Constructor
CV Destructor
CV Wait
CV Signal
Producer-Consumer Problem
Lets consider we have infinite buffermonitor variable => int itemCount = 0;
monitor lock => monitorLock;
monitor condition => needItem;
Producer
Consumer
No comments:
Post a Comment