Processes | Operating System - Computer Science Engineering (CSE) PDF Download

Program vs Process

A process is a program in execution. For example, when we write a program in C or C++ and compile it, compiler creates a binary code. The original code and Binary code, both are programs. When we actually run the binary code, it becomes a process.

A process is an ‘active’ entity as oppose to program which considered to be a ‘passive’ entity. A single program can create many processes when run multiple times, for example when we open an exe or binary file multiple times, many instances begin (many processes are created).

How Does a process looks in Memory?

Text Section: Process is also sometime known as the Text Section. It also includes the current activity represented by the value of Program Counter.
Stack: Stack contains the temporary data such as function parameters, return address and local variables.
Data Section: Contains the global variable.
Heap Section: Dynamically allocated memory to process during its run time.

Attributes or Characteristics of a Process

A process has following Attributes.

1. Process Id: A unique identifier assigned by operating system
2. Process State: Can be ready, running, .. etc
3. CPU registers: Like Program Counter (CPU registers must be saved and restored when a process is swapped out and in of CPU)
5. Accounts information:
6. I/O status information: For example devices allocated to process, open files, etc
8. CPU scheduling information: For example Priority (Different processes may have different priorities, for example, a short process may be assigned a low priority
 in shortest job first scheduling) 

All the above attributes of a process are also known as Context of the process.
Every Process has its known Program control Block (PCB) i.e each process will have a unique PCB. All the Above Attributes are the part of the PCB.

States of Process

1. New: Newly Created Process (or) being created process.

2. Ready: After creation Process moves to the Ready state, i.e. the process is ready for execution.

3. Run: Currently running process in CPU (only one process at a time can be under execution in a single processor).

4. Wait (or Block): When process request for I/O request.

5. Complete (or Terminated): Process Completed its execution.

6. Suspended Ready: When ready queue becomes full, some processes are moved to suspend ready state

7. Suspended Block: When waiting queue becomes full.

Context Switching

Process of saving the context of one process and loading the context of other process is known as Context Switching. In simple term it is like loading and unloading of process from running state to ready state.

When does Context switching happen?

1. When a high priority process comes to ready state, compared to priority of running process
2. Interrupt Occurs
3. User and Kernel-mode switch: (It is not necessary though)
4. Preemptive CPU scheduling used.

Context Switch vs Mode Switch

A mode switch occurs when the CPU privilege level is changed, for example when a system call is made or a fault occurs. The kernel works in more privileged mode than a standard user task. If a user process wants to access things which are only accessible to kernel, a mode switch must occur. The currently executing process need not to be changed during a mode switch.
A mode switch typically occurs for a process context switch to occur. Only the Kernel can cause a context switch.

CPU Bound vs I/O Bound Processes:

A CPU Bound Process requires more amount of CPU time or spends more time in the running state.
I/O Bound Process requires more amount of I/O time and less CPU time. I/O Bound process more time in the waiting state.

Process Management | CPU Scheduling

Scheduling of processes/work is done to finish the work on time.

Below are different time with respect to a process.

Arrival Time: Time at which the process arrives in the ready queue.
Completion Time: Time at which process completes its execution.
Burst Time: Time required by a process for CPU execution.
Turn Around Time: Time Difference between completion time and arrival time.          
 Turn Around Time = Completion Time - Arrival Time

Waiting Time(W.T): Time Difference between turn around time and burst time.
Waiting Time = Turn Around Time - Burst Time

Why do we need scheduling?

A typical process involves both I/O time and CPU time. In a unit programming system like MS-DOS, time spent waiting for I/O is wasted and CPU is free during this time. In multiprogramming systems, one process can use CPU while another is waiting for I/O. This is possible only with process scheduling.

Objectives of Process Scheduling Algorithm

Max CPU utilization [Keep CPU as busy as possible]
Fair allocation of CPU.
Max throughput [Number of processes that complete their execution per time unit]
Min turnaround time [Time taken by a process to finish execution]
Min waiting time [Time a process waits in ready queue]
Min response time [Time when a process produces first response]

Different Scheduling Algorithms

First Come First Serve (FCFS): Simplest scheduling algorithm that schedules according to arrival times of processes.

Shortest Job First(SJF): Process which have the shortest burst time are scheduled first.

Shortest Remaining Time First(SRTF): It is preemptive mode of SJF algorithm in which jobs are schedule according to shortest remaining time.

Round Robin Scheduling: Each process is assigned a fixed time in cyclic way.

Priority Based scheduling (Non Preemptive): In this scheduling, processes are scheduled according to their priorities, i.e., highest priority process is schedule first. If priorities of two processes match, then schedule according to arrival time.

Highest Response Ratio Next (HRRN): In this scheduling, processes with highest response ratio is scheduled. This algorithm avoids starvation.

Response Ratio = (Waiting Time + Burst time) / Burst time

Multilevel Queue Scheduling: According to the priority of process, processes are placed in the different queues. Generally high priority process are placed in the top level queue. Only after completion of processes from top level queue, lower level queued processes are scheduled.

Multi level Feedback Queue Scheduling: It allows the process to move in between queues. The idea is to separate processes according to the characteristics of their CPU bursts. If a process uses too much CPU time, it is moved to a lower-priority queue.

Some useful facts about Scheduling Algorithms:

2) Both SJF and Shortest Remaining time first algorithms may cause starvation. Consider a situation when long process is there in ready queue and shorter processes keep coming.

3) If time quantum for Round Robin scheduling is very large, then it behaves same as FCFS scheduling.

4) SJF is optimal in terms of average waiting time for a given set of processes,i.e., average waiting time is minimum with this scheduling, but problems is, how to know/predict time of next job.

Example 1: Consider the following table of arrival time and burst time for three processes P0, P1 and P2.

Process   Arrival time   Burst Time
P0            0 ms          9 ms
P1            1 ms          4 ms
P2            2 ms          9 ms

The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at the arrival or completion of processes. What is the average waiting time for the three processes?
(A) 5.0 ms
(B) 4.33 ms
(C) 6.33
(D) 7.33
Answer: (A)
Process P0 is allocated processor at 0 ms as there is no other process in ready queue. P0 is preempted after 1 ms as P1 arrives at 1 ms and burst time for P1 is less than remaining time of P0. P1 runs for 4ms. P2 arrived at 2 ms but P1 continued as burst time of P2 is longer than P1. After P1 completes, P0 is scheduled again as the remaining time for P0 is less than the burst time of P2.
P0 waits for 4 ms, P1 waits for 0 ms and P2 waits for 11 ms. So average waiting time is (0+4+11)/3 = 5.

Consider the following set of processes, with the arrival times and the CPU-burst times given in milliseconds 

 Process   Arrival Time    Burst Time
    P1          0              5
    P2          1              3
    P3          2              3
    P4          4              1

Example 2: What is the average turnaround time for these processes with the preemptive shortest remaining processing time first (SRPT) algorithm ?
(A) 5.50
(B) 5.75
(C) 6.00
(D) 6.25
Answer: (A)
Solution:
The following is the Gantt Chart of execution

Turn Around Time = Completion Time – Arrival Time
Avg Turn Around Time  =  (12 + 3 + 6+  1)/4 = 5.50

Process Scheduler

1. Long Term or job scheduler It bring the new process to the ‘Ready State’. It controls Degree of Multi-programming, i.e., number of process present in ready state at any point of time.

2. Short-term or CPU scheduler: It is responsible for selecting one process from ready state for scheduling it on the running state. 

Note: Short-term scheduler only selects the process to schedule it doesn’t load the process on running.

The dispatcher is responsible for loading the selected process by Short Term scheduler on the CPU (Ready to Running State) Context switching is done by the dispatcher only. A dispatcher does the following:
1) Switching context.
2) Switching to user mode.
3) Jumping to the proper location in the newly loaded program.

3. Medium-term scheduler It is responsible for suspending and resuming the process. It mainly does swapping (moving processes from main memory to disk and vice versa).