MIT School of Computing

Department of Computer Science & Engineering

Third Year Engineering

21BTCS504-Operating System

Class - T.Y.
PLD(SEM-I)

Unit - II
PROCESS MANAGEMENT

AY 2024-2025 SEM-I

1
 MIT School of Computing
Department of Computer Science & Engineering

Unit-II Syllabus/Contents

• Process Concept,
• Operations on Processes,
• Process Scheduling, PLD
• Inter-process Communication, 5 Examples of IPC Systems
• Multithreading Models, Threading Issues,
• CPU Scheduling, Basic Concepts, Scheduling Criteria,
Scheduling Algorithms, Multiple-Processor Scheduling, Thread
Scheduling

2
 MIT School of Computing
Department of Computer Science & Engineering

Process
• Program under execution
• An instance of a program
• Schedulable/Dispatch unit (CPU)
• Unit of execution (CPU)PLD

3
 MIT School of Computing
Department of Computer Science & Engineering

Process as a Data structure

• Definition (Same as last slide)
• Representation/Implementation
• Operations
PLD
• Attributes

4
 MIT School of Computing
Department of Computer Science & Engineering

Process representation

PLD

5
 MIT School of Computing
Department of Computer Science & Engineering

Process operations
• Create (space allocation)
• Schedule/run
• Wait/Block
• Suspend/Resume PLD

• Terminate (space deallocation)

6
 MIT School of Computing
Department of Computer Science & Engineering

Process Attributes in Process Control Block (PCB)

PLD

7
 MIT School of Computing
Department of Computer Science & Engineering

More about PCBs

• OS maintains 1 PCB for each process
• Contents of a PCB are also called collectively as
context of a process
PLD
OS
PCB1, PCB2, PCB3…PCBn

Process 1 (Stack, heap, code, data sections)

Process 2 (Stack, heap, code, data sections)

Process 3 (Stack, heap, code, data sections)

.
.

Process n (Stack, heap, code, data sections)

8
 MIT School of Computing
Department of Computer Science & Engineering

Context Switching in OS
• CPU uses registers to store current process
execution state
• When stopped in between, have to save these
values in PCB to resumePLDfrom that point onwards
• Saving current running process’s content(CPU
register values) from CPU to PCB of the process and
loading other process’s context in CPU registers

9
MIT School of Computing
Department of Computer Science & Engineering

Example Context Switching

PLD

10
 MIT School of Computing
Department of Computer Science & Engineering

Preemptive Process States

PLD

11
 MIT School of Computing
Department of Computer Science & Engineering

Non-preemptive process states

PLD

12
 MIT School of Computing
Department of Computer Science & Engineering

Explanation
• New: All installed processes are here (SSD, HDD)
• Ready: Processes among the installed processes that
are wanting to run on CPU (in MM)
PLD
• Running: Running on CPU (MM)
• Blocked: Waiting for any I/O or event (MM)
• Terminated: All completed processes are in this state
(goes out from the MM)

13
 MIT School of Computing
Department of Computer Science & Engineering

Note
• When a new process is formed, OS makes the PCB
• In non preemptive process, no factor can force a
running process to come out of CPU. Termination or
PLD
going to waiting is only its wish.
• PCB will be there in running, ready and waiting
state. In these three states, process will be in MM
only

14
 MIT School of Computing
Department of Computer Science & Engineering

CPU scheduling
• Make a selection of ready processes to run on CPU.
• Needed for better performance
• Metric for performancePLDmay vary
• Multiple policies according to metric

15
 MIT School of Computing
Department of Computer Science & Engineering

Scheduling Queue
• Job queue: to keep all processes in new state
• Ready queue: to keep all processes in ready state
• Device queue: to keep the processes in blocked
state PLD

16
 MIT School of Computing
Department of Computer Science & Engineering

Scheduling Objectives
• Maximize throughput.
• Maximize number of users receiving acceptable
response times.
• Be predictable. PLD

• Balance resource use.

• Enforce Priorities.
• Give preference to processes holding key resources

17
 MIT School of Computing
Department of Computer Science & Engineering

CPU scheduling need

• Make a selection of ready processes to run on CPU.
• Needed for better performance
• Metric for performance may vary
PLD
• Multiple policies according to metric

18
 MIT School of Computing
Department of Computer Science & Engineering

Types of scheduler
• Long term scheduler: new to ready
• Short term scheduler: ready to running
• Mid term scheduler: swapping
PLD
is done by this.
Swapping leads to suspension

19
MIT School of Computing
Department of Computer Science & Engineering

PLD

20
 MIT School of Computing
Department of Computer Science & Engineering

CPU Scheduling
• Types: Preemptive and non preemptive
• Assumption initially: No process has I/O requirement
• Some terminologies:
• Arrival Time(AT): Process arrival time(admitted by LTS)
• Burst/Service time(BT): burst time is the time, required the cpu to
PLD
execute that job, it is in milli seconds.
• Completion time (CT): Time when process completes execution
• Turn around time (TAT): Time from arrival until completion (TAT=CT-
AT)
• Waiting time (WT): Waiting for CPU in ready queue (WT=TAT-BT)
• Response time: Time from arrival to the first response on CPU
• Scheduling length: max(CT)-min(AT)
• Throughput: No of processes executed per unit time

21
 MIT School of Computing
Department of Computer Science & Engineering

Scheduling Criteria
• CPU Utilization
• Throughput
• Turnaround time PLD

• Waiting Time
• Response Time

22
 MIT School of Computing
Department of Computer Science & Engineering

CPU SCHEDULING ALGORITHMS:

• FCFS (First come first serve) – Non
preemptive
• SJF (Shortest Job first) – Non preemptive
PLD
• Priority Scheduling
• Round Robin - Preemptive
• Others

23
 MIT School of Computing
Department of Computer Science & Engineering

FCFS (First Come First Serve)

• The process that request the CPU first is holds the cpu first.
• If a process request the cpu then it is loaded into the ready
queue PLD

• Mode: Non preemptive

• Tie breaker: Smallest ID first of the processes at tie (P1
and P2, P1 will execute first)

24
 MIT School of Computing
Department of Computer Science & Engineering

FCFS Example no. 1

Process Id Arrival time Burst time

P1 3 4

P2 5 3
PLD
P3 0 2

P4 5 1

P5 4 3

calculate the average waiting time and average turn around

time.

25
 MIT School of Computing
Department of Computer Science & Engineering

Solution-
Gantt Chart-

PLD

Here, black box represents the idle time of CPU.

• Turn Around time = Exit time – Arrival time
• Waiting time = Turn Around time – Burst time

26
 MIT School of Computing
Department of Computer Science & Engineering

rocess Id Exit time Turn Around time Waiting time

P1 7 7–3=4 4–4=0

P2 13 13 – 5 = 8 8–3=5
PLD
P3 2 2–0=2 2–2=0

P4 14 14 – 5 = 9 9–1=8

P5 10 10 – 4 = 6 6–3=3

27
 MIT School of Computing
Department of Computer Science & Engineering

• Average Turn Around time = (4 + 8 + 2 + 9

+ 6) / 5 = 29 / 5 = 5.8 unit

• Average waiting time = (0 + 5 + 0 + 8 + 3) /

PLD
5 = 16 / 5 = 3.2 unit

28
 MIT School of Computing
Department of Computer Science & Engineering

Pros and Cons

• Advantages
• Very easy to implement
• No complex logic
• No starvation
PLD

• Disadvantages
• No option of preemption
• Convoy effect

29
 MIT School of Computing
Department of Computer Science & Engineering

Convoy effect
• Only FCFS suffers
• If a slow process (large service time) is scheduled first, then it makes
entire system slow

PLD

30
 MIT School of Computing
Department of Computer Science & Engineering

SJF
• Criteria: min BT first
• Mode: Non preemptive
• Tie breaker: FCFS

PLD

31
MIT School of Computing
Department of Computer Science & Engineering

Example

PLD

32
MIT School of Computing
Department of Computer Science & Engineering

PLD

33
 MIT School of Computing
Department of Computer Science & Engineering

More about SJF

• Advantages:
• Min waiting time among non preemptive scheduling
• Better throughput in continuous execution
• No convoy effect
PLD
• Disadvantages
• No practical implementation because burst time cannot be known in
advance
• No option of preemption
• Longer processes may suffer from starvation
• No fairness

34
 MIT School of Computing
Department of Computer Science & Engineering

Priority Scheduling

PLD

35
 MIT School of Computing
Department of Computer Science & Engineering

[Link] Around Time = Completion Time - Arrival Time

[Link] Time = Turn Around Time - Burst Time

PLD

36
 MIT School of Computing
Department of Computer Science & Engineering

Avg Waiting Time = (0+11+2+7+12+2+18)/7 =

52/7 units
Preemptive Priority Scheduling

PLD

37
MIT School of Computing
Department of Computer Science & Engineering

PLD

38
 MIT School of Computing
Department of Computer Science & Engineering

Round Robin Scheduling

• Criteria: Arrival time + (Q)Quantum time/timeslice
• Mode: Preemptive
• Quantum time/time slice: Max amount of time for which a
process runs on CPU beforePLDpreemption

39
MIT School of Computing
Department of Computer Science & Engineering

PLD

40
MIT School of Computing
Department of Computer Science & Engineering

PLD

41
 MIT School of Computing
Department of Computer Science & Engineering

Multilevel Queue
• Ready queue is partitioned into separate queues, eg:
• foreground (interactive)
• background (batch)
• Process permanently in a given queue
PLD
• Each queue has its own scheduling algorithm:
• foreground – RR
• background – FCFS
• Scheduling must be done between the queues:
• Fixed priority scheduling; (i.e., serve all from foreground then from
background). Possibility of starvation.
• Time slice – each queue gets a certain amount of CPU time which it can
schedule amongst its processes; i.e., 80% to foreground in RR
• 20% to background in FCFS
42
 MIT School of Computing
Department of Computer Science & Engineering

Multilevel Queue Scheduling

PLD

43
 MIT School of Computing
Department of Computer Science & Engineering

Multilevel Feedback Queue

• A process can move between the various queues;

aging can be implemented this way
• Multilevel-feedback-queue scheduler defined by the
following parameters: PLD

• number of queues
• scheduling algorithms for each queue
• method used to determine when to upgrade a process
• method used to determine when to demote a process
• method used to determine which queue a process will
enter when that process needs service

44
 MIT School of Computing
Department of Computer Science & Engineering

Example of Multilevel Feedback Queue

• Three queues:
• Q0 – RR with time quantum 8 milliseconds
• Q1 – RR time quantum 16 milliseconds
• Q2 – FCFS

• Scheduling PLD
• A new job enters queue Q0 which is
served FCFS
• When it gains CPU, job receives 8
milliseconds
• If it does not finish in 8
milliseconds, job is moved to
queue Q1
• At Q1 job is again served FCFS and
receives 16 additional milliseconds
• If it still does not complete, it is
preempted and moved to queue Q2

45
 MIT School of Computing
Department of Computer Science & Engineering

Thread Scheduling
• Distinction between user-level and kernel-level threads
• When threads supported, threads scheduled, not processes
• Many-to-one and many-to-many models, thread library
schedules user-level threads
PLD
to run on LWP
• Known as process-contention scope (PCS) since scheduling
competition is within the process
• Typically done via priority set by programmer
• Kernel thread scheduled onto available CPU is system-
contention scope (SCS) – competition among all threads in
system

46
 MIT School of Computing
Department of Computer Science & Engineering

Multiple-Processor Scheduling
• CPU scheduling more complex when multiple CPUs are available
• Homogeneous processors within a multiprocessor
• Asymmetric multiprocessing – only one processor accesses the
system data structures, alleviating the need for data sharing
PLD
• Symmetric multiprocessing (SMP) – each processor is self-
scheduling, all processes in common ready queue, or each has
its own private queue of ready processes
• Currently, most common
• Processor affinity – process has affinity for processor on which
it is currently running
• soft affinity
• hard affinity
• Variations including processor sets
47
 MIT School of Computing
Department of Computer Science & Engineering

Multiple-Processor Scheduling – Load Balancing

• If SMP, need to keep all CPUs loaded for efficiency

• Load balancing attempts to keep workload evenly distributed
• Push migration – periodic taskPLD
checks load on each
processor, and if found pushes task from overloaded CPU to
other CPUs
• Pull migration – idle processors pulls waiting task from busy
processor

48
 MIT School of Computing
Department of Computer Science & Engineering

Multicore Processors

• Recent trend to place multiple processor cores on

same physical chip
• Faster and consumes less power
PLD
• Multiple threads per core also growing
• Takes advantage of memory stall to make progress on
another thread while memory retrieve happens

49
 MIT School of Computing
Department of Computer Science & Engineering

Multithreaded Multicore System

PLD

50
 MIT School of Computing
Department of Computer Science & Engineering

The inter-process communication examples include the following.

• Posix uses the shared memory technique.

• Windows XP uses message passing technique.

PLD
• Mach uses the message passing technique.

• Pipes.

• Server.

51
 MIT School of Computing
Department of Computer Science & Engineering

Advantages
• It permits one application to manage another application

• Allows data communication through different processes to

utilize semaphores, segments & other techniques to
share data & memory. PLD

• helps in transferring efficient messages in between

processes.

• avoid synchronization & named pipes blocking issues by

sending a message.
52
 MIT School of Computing
Department of Computer Science & Engineering

Disadvantages
• Similar to the pipe, every data block includes the highest limit
of length.
• Complete system data length for all blocks integrated within
the queue also includes anPLD
upper limit.
• All the processes or programs that utilize the model of shared
memory need to check that they are not writing to a similar
memory location.
• A shared memory model may form issues like synchronization
& protection of memory that require to be addressed.
• As compared to straight function calls, it is slow.
53
 MIT School of Computing
Department of Computer Science & Engineering

PLD

This Photo by Unknown Author is licensed under CC BY 54

MIT School of Computing
Department of Computer Science & Engineering

PLD

55
MIT School of Computing
Department of Computer Science & Engineering

PLD

56
MIT School of Computing
Department of Computer Science & Engineering

PLD

57
MIT School of Computing
Department of Computer Science & Engineering

PLD

58
MIT School of Computing
Department of Computer Science & Engineering

PLD

59