Module 4: Processes
• Process Concept
• Process Scheduling
• Operation on Processes
• Cooperating Processes
• Threads
• First Programming Assignment
Applied Operating System Concepts 1.1 Silberschatz, Galvin, and Gagne 1999
Process Concept
• An operating system executes variety of
programs:
– Batch system – jobs
– Time-shared systems – user programs
• Textbook uses the terms job and process.
• Process – a program in execution; process
execution must progress in sequential fashion.
• A process includes program counter, stack, data
section
Applied Operating System Concepts 1.2 Silberschatz, Galvin, and Gagne 1999
Simple Two-State Process Model
Dispatch
Enter Exit
Not
Running
Running Pause
(a) State transition diagram
Queue Dispatch Exit
Enter Processor
Pause
(a) Queuing diagram
Applied Operating System Concepts 1.3 Silberschatz, Galvin, and Gagne 1999
1
Dispatcher
• Program that moves the processor from one
process to another
• Prevents a single process from monopolizing
processor time
Applied Operating System Concepts 1.4 Silberschatz, Galvin, and Gagne 1999
5 State Process State
• As a process executes, it changes state
– New: The process is being created.
– Running: Instructions are being executed.
– Waiting or blocked: The process is
waiting for some event to occur.
– Ready: The process is waiting to be
assigned to a process.
– Terminate or Exit: The process has
finished execution.
Applied Operating System Concepts 1.5 Silberschatz, Galvin, and Gagne 1999
Diagram of Process State
Applied Operating System Concepts 1.6 Silberschatz, Galvin, and Gagne 1999
2
OS Control Structures
Memory Tables
Process Image
Memory
I/O Tables User data
I/O User program
System stack
File File Tables PCB
Processes
Primary Table
Process 1
Process 2
…
Process N
Applied Operating System Concepts 1.7 Silberschatz, Galvin, and Gagne 1999
Operating System Control
Structures
• Schedules and dispatches processed for
execution by the processor
• Allocates resources to processes
• Responds to requests by user programs
• Tables are constructed for each entity the
operating system manages
Applied Operating System Concepts 1.8 Silberschatz, Galvin, and Gagne 1999
Memory Tables
• Allocation of main memory to processes
• Allocation of secondary memory to processes
• Protection attributes for access to shared
memory regions
• Information needed to manage virtual memory
Applied Operating System Concepts 1.9 Silberschatz, Galvin, and Gagne 1999
3
I/O Tables
• I/O device is available or assigned
• Status of I/O operation
• Location in main memory being used as the
source or destination of the I/O transfer
Applied Operating System Concepts 1.10 Silberschatz, Galvin, and Gagne 1999
File Tables
• Existence of files
• Location on secondary memory
• Current Status
• Attributes
• Sometimes this information is maintained by a
file-management system
Applied Operating System Concepts 1.11 Silberschatz, Galvin, and Gagne 1999
Process Table
• Process image consists of program, data, stack,
and attributes
• Attributes or PCB
– process control block
Applied Operating System Concepts 1.12 Silberschatz, Galvin, and Gagne 1999
4
Process Control Block (PCB)
Information associated with each process.
• Process state
• Program counter
• CPU registers
• CPU scheduling information
• Memory-management information
• Accounting information
• I/O status information
Applied Operating System Concepts 1.13 Silberschatz, Galvin, and Gagne 1999
Process Control Block (PCB)
Applied Operating System Concepts 1.14 Silberschatz, Galvin, and Gagne 1999
CPU Switch From Process to
Process
Applied Operating System Concepts 1.15 Silberschatz, Galvin, and Gagne 1999
5
Process Scheduling Queues
• Job queue – set of all processes in the
system.
• Ready queue – set of all processes residing
in main memory,
ready and waiting to execute.
• Device queues – set of processes waiting for
an I/O device.
• Process migration between the various
queues.
Applied Operating System Concepts 1.16 Silberschatz, Galvin, and Gagne 1999
Ready Queue, I/O Device Queues
Applied Operating System Concepts 1.17 Silberschatz, Galvin, and Gagne 1999
Representation of Process
Scheduling
Applied Operating System Concepts 1.18 Silberschatz, Galvin, and Gagne 1999
6
Schedulers
• Long-term scheduler (or job scheduler) –
selects which processes should be brought
into the ready queue.
• Short-term scheduler (or CPU scheduler) –
selects which process should be executed
next and allocates CPU.
Applied Operating System Concepts 1.19 Silberschatz, Galvin, and Gagne 1999
Addition of Medium Term
Scheduling
Applied Operating System Concepts 1.20 Silberschatz, Galvin, and Gagne 1999
Schedulers (Cont.)
• Short-term scheduler invoked frequently (ms)
⇒ (must be fast).
• Long-term scheduler invoked infrequently
(seconds, minutes) ⇒ (may be slow).
• The long-term scheduler controls the degree of
multiprogramming.
• Processes can be described as either:
– I/O-bound process
– CPU-bound process
Applied Operating System Concepts 1.21 Silberschatz, Galvin, and Gagne 1999
7
Context Switch
• When CPU switches to another process, the
system must save the state of the old process
and load the saved state for the new process.
• Context-switch time is overhead; the system
does no useful work while switching.
• Time dependent on hardware support.
Applied Operating System Concepts 1.22 Silberschatz, Galvin, and Gagne 1999
Process Creation
• Parents create children; results in a tree of
processes.
• Resource sharing
– Parent and children share all resources.
– Children share subset of parent’s resources.
– Parent and child share no resources.
• Execution
– Parent and children execute concurrently.
– Parent waits until children terminate.
Applied Operating System Concepts 1.23 Silberschatz, Galvin, and Gagne 1999
Process Creation (Cont.)
• Address space
– Child duplicate of parent.
– Child has a program loaded into it.
• UNIX examples
– fork system call creates new process
– execve system call used after a fork to
replace the process’ memory space with a
new program.
Applied Operating System Concepts 1.24 Silberschatz, Galvin, and Gagne 1999
8
A Tree of Processes On A Typical
UNIX System
Applied Operating System Concepts 1.25 Silberschatz, Galvin, and Gagne 1999
Process Termination
• Process executes last statement (exit).
– Output data from child to parent (via wait).
– resources deallocated by operating system.
• Parent may terminate execution of children
processes (abort).
– Child has exceeded allocated resources.
– Task assigned to child is no longer required.
– Parent is exiting.
✴ Operating system does not allow child to continue
✴ Cascading termination.
Applied Operating System Concepts 1.26 Silberschatz, Galvin, and Gagne 1999
Cooperating Processes
• Independent process cannot affect or be
affected by the execution of another process.
• Cooperating process can affect or be affected
by the execution of another process
• Advantages of process cooperation
– Information sharing
– Computation speed-up
– Modularity
– Convenience
Applied Operating System Concepts 1.27 Silberschatz, Galvin, and Gagne 1999
9
Producer-Consumer Problem
• Paradigm for cooperating processes, producer
process produces information that is
consumed by a consumer process.
– unbounded-buffer places no practical limit
on the size of the buffer.
– bounded-buffer assumes that there is a
fixed buffer size.
Applied Operating System Concepts 1.28 Silberschatz, Galvin, and Gagne 1999
Bounded-Buffer – Shared-Memory
Solution
• Shared data
var n;
type item = … ;
var buffer. array [0..n–1] of item;
in, out: 0..n–1;
• Producer process
repeat
…
produce an item in nextp
Applied Operating System Concepts
… 1.29 Silberschatz, Galvin, and Gagne 1999
hil i 1 d d
Bounded-Buffer (Cont.)
• Consumer process
repeat
while in = out do no-op;
nextc := buffer [out];
out := out+1 mod n;
…
consume the item in nextc
Applied Operating System Concepts … 1.30 Silberschatz, Galvin, and Gagne 1999
10
Exception Conditions – Error
Recovery
• Process terminates
• Lost messages
• Scrambled Messages
Applied Operating System Concepts 1.31 Silberschatz, Galvin, and Gagne 1999
UNIX Process State Diagram fork
Created
Preempted
return
enough not enough memory
to user
memory (swapping system only)
User
Running preempt Ready to Run
swap out
return reschedule Ready to Run Swapped
process in Memory
swap in
system call,
interrupt Kernel
Running
sleep wakeup wakeup
interrupt,
interrupt return exit
swap out Sleep,
Asleep in
Zombie Swapped
Memory
Applied Operating System Concepts 1.32 Silberschatz, Galvin, and Gagne 1999
11
