Concurrent Process

In single processor systems or in multiple processor systems processes may execute concurrently. We here first discuss with concurrent processing in uni processor systems. Two process are said to be concurrent if their execution overlaps in time.Consider statements
S1: a= x+y
S2: b= z
S3: c=a+b
S4: d=c-1

Here statements S1&S2 are independent they can be executed concurrently, whereas statement S3 is depends on S2, S1. S4 is depends on S3. If you look at the precedence graph it is looks like

If we define two sets Read operation R(s), write operation W(s) then the conditions for concurrency are
R(s) ∩ W(s) = fi

W(s) ∩ R(s) = fi

W(s) ∩ W(s) = fi

R(s) ∩ R(s) ≠ fi

Process

Process is a program in execution. Generally programs resides in secondary memory. when cpu is ready to execute then they are placed in main memory. If we compare process with program, process is a active entity where as program is a passive entity. A program can have more number of processes. e.g. you can have a calculator program open twice, this is two processes but only one program.

Every process has different states.
1. New: Process is created.
2. Ready state: Process is ready for the execution
3. Running state: Process is in execution
4. Halt or termination: Process completed execution
5. Wait: Process is in wait state(For i/o operation or because of time expire).
Below diagram is the process state diagram.


Possible state transitions for particular process

Case1. New->Ready->Running->Halt

Case2. New->Ready->Running->Wait->Ready->running->Halt

Case3. New->Ready->Running->Ready->Running->Halt

When the process is in Running state means it acquired the CPU. After the completing it releases the CPU to other process. In single user systems like DOS there is no need of Ready state so from wait process directly go back to running state. Case1 is possible in DOS systems. Case2 is possible in systems supporting non-preemptive scheduling. In this case process is kept in wait queue either for I/O or by timeout of the cpu burst time. Case3 is possible in systems supporting non-preemptive scheduling. In this case processes are placed in Ready queue by preempting from Running state.

Here two schedulers comes into picture one is in selecting a process from poll of New queue processes and place it in Ready queue this is done by Long term scheduler(LTS), selecting of process from pool of Ready queue processes and place it in Running state, this is done by short term scheduler(STS). LTS takes more time in deciding which process to put in Ready queue but STS takes less time in deciding which process to be given to the CPU.

Above we have discussed the process and state transitions in process execution. Now we discuss about process management. Process management is nothing but sharing CPU time to different processes. If more number of processes running doesn't mean that system is having more number of CPUs, CPU is being shared between all these processes. This is the job of CPU scheduling.

CPU scheduling is divided in to two types Non-preemptive scheduling and preemptive scheduling.

Non-preemptive scheduling: If a process is allotted to the CPU, the process is not removed until it complete the CPU burst time. FCFS, SJF, priority based scheduling are coming under non-preemptive scheduling.

Preemptive scheduling: Process is being forcefully removed from the running state even before completion of CPU burst time. Round robin, Multilevel feedback queue are coming under preemptive scheduling.

Before get in to the details of above we look into Waiting time and Turn around time.

Waiting time - amount of time process is waiting in the ready queue.
Turnaround time – amount of time the process is submitted to when it has completed.
Scheduler should be selected such that waiting time and turnaround time should be minimum in order to keep CPU busy as much as possible.


FCFS - First Come First Serve
Processes are given time on the CPU in the order of arrival. Process is not preempted till CPU burst complete. Consider an example Job1,2,3 with their respective cpu burst times shown below.Average time =(0+10+16)/3=8.67
Turn around time=(10+16+19)/3=15
In FCFS waiting time is more. Here low CPU burst process have to wait till high cpu burst process complete their task.

SJF - Shortest Job First
In this processes are given to the CPU based their burst time. For above example using SJF
Average waiting time=(9+3+0)/3=4.
Average Turn around time=(19+9+3)/3=10.34
In this case waiting time is less. Problem with SJF is, process with more cpu burst time have to wait for longer time, leads to starvation. To avoid this generally aging technique is used. It works by adding an aging factor to the priority of each request. The aging factor must increase the request’s priority as time passes.

Priority based:
This can be obtained from SJF. Process having lowest CPU burst time is equal to the process having highest priority. In this process is given to the CPU based on the their priority.

P(t)=1/T(t)

Generally priority based scheduling is used in real time OS(RTOS).

Round robin:
In this each process is given to the CPU for a certain amount of time called Quantum, once this time is completed then the process is forcefully preempted from Running state and placed in the Ready queue. For the above example with quantum time 3ms

Average waiting time=(0+3+6)/3=3.
Average Turn around time=(19+9+3)/3=10.34.

Problems with RR:
If quantum time is less then most of the time dedicated for context switching only which is useless work.
If quantum time high then it is just like FCFS.

Multi level feedback queue:
In this Ready queue divided in to sub queues and for each queue has given with own quantum time. Processes are allowed to move between different queues based on their CPU burst time.

OS introduction

Before get in to the details of operating system i clarify, What is operating system, and its responsibilities.

Basically an operating system is an resource allocator. Consider an example in our daily life: You are having telephonic call, at the same time bell is ringing. Now at this moment you have to decide which task to do first. Here your allocating the time to each task. Simply to say sharing the time between different processes(Tasks).

Similarly operating system is a resource allocator in the system. Now we look at what are the resources present in the system.

1. Central processing Unit(CPU)
2. Main memory
3. Secondary memory
4. Input&output devices(I/O dev's)

=>CPU is an most important unit in the system. Its responsbility is to execution of instructions present in the main memory. It doesn't have direct access to secondary memory.

=>Main memory is the one where executable code is placed to execute. Generally executable files are placed in secondary memory. when CPU is ready to execute then the code is bring to the main memory and then start executing.

=> Secondary memory is an auxiliary memory which is an low speed & low cost memory. Note accessing main memory and secondary memory are totally different

=> I/O devices are used for user to write data, read data from the system. Keyboard is an example for input device and printer is an example for output device.

Operating systems responsibility is to manage all the above resource to different users at the same time to utilize them optimally.