Process Management

Process Management

Process Description, State and Control

2.1.1 Process

Process is the abstraction of any running program. In other words, a process is an activity of some kind that the processor performs which contains program. Input, output and a state. A process is an executing program along with the current values of pc, registers and variables. Each process has its own virtual CPU.

---

2.1.2 Process model

A multiprogramming system is capable of doing multiple things at the same time. But , actually, at any programs are organized into a number of sequential processes. The CPU switches back and forth form process to process rapidly.

---

2.1.3 process State (3-state model)

- A process, at any instant, may be in one of the following state:
a) Running  using CPU at that instant
b) Ready  runnable but temporarily stopped to let another process run
c) Blocked  unable to run until some external event happens.

Among these three states, four transitions are possible as follow: -
a) Process blocks for input
b) Scheduler picks another process
c) Scheduler pikes this process
d) Input becomes available

---

2.1.4 Process State (5 State Model)

---

2.1.4 Process Control

Process control box is a data structure maintained by OS every process representing the process and its state. PCB is by OS when a process is created and PCB is released pool of free memory locations when a process terminates.

---

2.1.5 Program Vs Process

Program:
1) It is set of instructions in a programming language
2) It is static object.
3) It is loaded into secondary storage
4) It has unlimited time span.
5) It is passive entity.

Process:
1) It is a sequence od execution of instructions.
2) It is dynamic object.
3) It is loaded into main memory.
4) It has limited time span.
5) It is active entity.

---

2.1.6 Other Topics

Q) Define zombile and orphan states of process. [3]

- A process is in orphan state if its parent process has finished or terminated, through it remains running.
- A process is in Zombile state if it has completed execution but still has an entry in the process table.
- Kill command cannot affect zombile state.

Q) What is dispatcher? [1]

- Also, called short term scheduler
- It selects the process from waiting queue and allocates CPU to that process.

---

Thread

Thread is a single sequential execution stream within a process which can not run independently. It consists of registers, PC, stack and stack pointer. A thread shares address space, global variable, OS resources, etc other threads.

Threads are used to increase CPU efficiency. With multiple threads within a process, if one thread blocks, others can still continue executing without wasting CPU time.

---

2.2.1 Multithreading

The use of multiple threads within a process and all of them running at the same time to perform different tasks is call multithreading. Eg. JAVA browser.

The advantages of multithreading are enlisted below: -
a) For a single processor system, it can be used where:
- Some tasks take much longer to execute than others.
- Some tasks need a better deterministic outcome than others.
- Some UI is to be run concurrently with hardware communications.
b) On multiprocessor system, it makes utilization of additional hardwares improving performance.

---

Process vs Thread

Process

a) Can not share same memory.
b) More time for creation.
c) Execution is very slow.
d) More time to terminate.
e) More time to switch.
f) Less resource sharing.
g) Communication is difficult.
h) System calls required for communication
i) Not suitable for exploiting parallelism

---

Thread

a) Can share memory.
b) Less time for creation.
c) Execution is very fast.
d) Less time to terminate.
e) Less time to switch.
f) More resource sharing.
g) Communication is easy.
h) System calls are not required.
i) Suitable for exploiting parallelism.

---

Scheduling Algorithms

Scheduling is the operation performed by an OS so as to decide which process to run first when more than one process is in ready state. Scheduler is responsible to schedule processes and the algorithm used is scheduling algorithm.

---

2.3.1 Good Scheduling Algorithm

The criteria that constitutes a good scheduling algorithm are as follows: -
a) Fair  It must ensure fair share of CPU to each process.
b) Efficient  It must keep CPU busy all the time.
c) Response time  It must ensure as less response time as possible.
d) Turnaround  It must reduce the waiting time for o/p by batch users.
e) Throughput  It must maximize the no. of jobs processed per hours.

---

2.3.2 Types of scheduling

- Preemptive scheduling: It is the scheduling in which the processes that are logically runnable are allowed to be temporarily suspendent.
- Non - preemptive: It is the scheduling in which the current process much run to completion before the next process gets share of CPU.
- Non - preemptive may result in denying of other processes indefinitely. So, it is not suitable for general purpose system.

---

2.3.3 Scheduling in Batch system

In batch system, scheduling is non-preemptive. It means the processes are set up by initial commands and afterwards they are scheduled to the run to completion strategy.

---

2.3.4 Round Scheduling (RR)

- Each process is assigned a time interval for which it is called to run such interval is call quantum.
- If process is not completed at the end of quantum, the CPU is preempted and given to another process.
- If process is blocked or finished before quantum time, the context switching occurs immediately.
- When switching form one process to another, it requires certain time to save and load registers, update tables, etc.
- For efficiency, quantum should neither be too short nor be to long.

---

2.3.5 Priority Scheduling

- Each process is assigned a priority and the runnable process with highest priority is allowed to run.
- At each clock interrupt, the scheduler decrease priority of currently running process and if its priority drops below that of next highest process, context switches.
- Also, a quantum may be assigned. When quantum ends. The next highest priority of process is run.
- Group processes into priority classes and use RR with in each class.

---

2.3.6 Multiple Queues

- Defining priority class
- Processes in highest class run for one quantum, next highest class run for two quanta, next for four quanta and so on.

---

2.3.7 Shortest Job First (SJF)

- Especially for batch system.
- Provides optimal turnaround time average.
- Only optimal when all the jobs are available simultaneously.

---

2.3.8 Guaranteed Scheduling

- CPU time each process actually had is calculated i.e time since creation divided by no. of processes(n).
- Compute ratio of actual CPU had to CPU time entitled.
- Run the process with lowest ratio until its ratio has moved above its closest competitor.

---

2.3.9 Lottery Scheduling

- Giver lottery tickets to each process
- For scheduling decision, a ticket is chosen at random and the process holding that ticket gets the CPU share.
- For priority, ,more tickets are given to a process.

---

2.3.10 Real Time scheduling

In real time systems, time is very critical factor. The OS is responsible to schedule all the events so that all of them meet their deadlines. The events that system have to respond can be periodic (occurring at regular intervals) or aperiodic ( accruing unpredictably).

If there are m periodic events and event i occurs with period p; requiring c; second of CPU time to handle each event, then the system is said to be schedulable if it satify the criteria:

{∑ C(i) / P(i) } <= 1 ---- for i = 1 to m

- Rate monotonic algorithm:
It assigns each process a priority proportional to frequency of occurrence of occurrence of its triggering event.

- Earliest of its deadline first
The process is added to list of ready processes sorted by deadline whenever an event is detected.

- Least laxity
Laxity is the amount of time a process has to spare. It first laxity of each process and choses the process with least laxity.

---

2.3.11 Scheduling Algorithms

Batch System
a) First come first serve
b) Shortest job first
c) Shortest remaining time next

Interactive System
a) Round Robin
b) Priority
c) Multiple Queue

---

Q) schedule processes according to RR. Calculate average waiting time and average turnaround time (q = 4)
Process : A B C D
Arrival time : 0 2 5 10
CPU time : 12 8 7 9

Answer =
Gant chart (RR) = A-B-A-C-B-D-A-C-D-D
Av. Turnaround time = (28+18+25+26) / 4 = 24.5 MS
Av. Waiting time = (16+10+19+17) / 4 =15.50 MS

---

Q) for the processes below, schedule using facts.
Process P₀ P₁ P₂ P₃
Arrival time 0 1 3 5
Burst time 10 6 2 4

Ans=
GANT Chart = P0 - P1 - P2 - P3

Now,
Process Arrival Time Burst Time Finish Time TAT WT
P₀ 0 10 10 10-0=10 10-10=0
P₁ 1 6 16 16-1=15 15-6=9
P₂ 3 2 18 18-3=15 15-2=13
P₃ 5 4 22 22-5=17 17-4=13

: . ATAT = 14.25ms
: . AWT = 8.75ms

---

Q) Allocate CPU with SJF scheduling.
Process P₁ P₂ P₃ P₄
Arrive Time 0 1 2 3
Burst Time 8 4 9 5

Ans=
GANT Chart : P1 - P2 - P4 - P1 - P3

Process Arrival Time Burst Time Finish Time TAT WT
P₁ 0 8 17 17 9
P₂ 1 4 5 4 0
P₃ 2 9 26 24 15
P₄ 3 5 10 7 2

: . ATAT = 13ms
: . AWT = 6.5ms

---

Q) Schedule using Shortest Remaining Time First (SRTF)
Process P1 P2 P3 P4 P5
Arrival Time 0 2 4 6 8
Service Time 3 6 4 5 2

Ans=
GANTT Chart = P1 - P2 - P3 - P5 - P2 - P4

Process Arrival Time Burst Time Finish Time TAT WT
P₁ 0 3 3 3 0
P₂ 2 6 15 13 7
P₃ 4 4 8 4 0
P₄ 6 5 20 14 9
P₅ 8 2 10 2 0

: . ATAT = 7.2ms
: . AWT = 3.2ms

---

Q) Use priority scheduling (preemptive and non-preemptive)
Process Arrival Time Burst Time Priority
P₁ 0 10 3
P₂ 1 5 2
P₃ 2 2 1
Where, 1 = highest priority
3= lowest priority

Answer:

---

Q) Schedule using HRRN.
Process Arrival Time CPU Time
A 0 3
B 2 6
C 4 4
D 6 5
E 8 2

Ans=

RR = (Waiting time + Service time) / Service time

At time 9, RR of C = 2.25
RR of D = 2
RR of E = 1.5

At the time 13, RR of D = 2.4
RR of E = = 3.5

 

  -by SURAJ AWAL