Transcript Module 4: Processes

Chapter 3: Processes
Objectives
 Understand

Process concept

Process scheduling

Creating and terminating processes

Interprocess communication
Operating System Concepts
3.2
Silberschatz, Galvin and Gagne ©2005
Process Concept
 An operating system executes a variety of programs:

Batch system – jobs

Time-shared systems – user programs or tasks
 The terms job and process are almost interchangeable
 Process – a program in execution; process execution must
progress in sequential fashion
 A process includes:

program counter

stack

data section
Operating System Concepts
3.3
Silberschatz, Galvin and Gagne ©2005
Process in Memory
int global = 0;
int main (int arg)
{
float local;
char *ptr;
Local variables
Return address
ptr = malloc(100);
local = 0;
local += 10*5;
…..
….
foo();
…. /* return addr */
….
return 0;
Dynamically
allocated
Global variables
Program code
}
Operating System Concepts
3.4
Silberschatz, Galvin and Gagne ©2005
Process State
 As a process executes, it changes state

new: The process is being created

running: Instructions are being executed

waiting: The process is waiting for some event to occur

ready: The process is waiting to be assigned to a process

terminated: The process has finished execution
Operating System Concepts
3.5
Silberschatz, Galvin and Gagne ©2005
Process Control Block (PCB)
 OS maintains info about process in PCB

Process state

Program counter

CPU registers

CPU scheduling information

Memory-management information

Accounting information

I/O status information
 Typically, a large C structure in the kernel

Linux: struct task_struct
 Used extensively to manage processes

E.g., to switch CPU from one process
to another
Operating System Concepts
3.6
Silberschatz, Galvin and Gagne ©2005
CPU Switch From Process to Process
(Context Switch)
 When switching occurs,
kernel
 Saves state of P0 in
PCB0 (in memory)

Loads state of P1
from PCB1 into
registers
 State = values of the
CPU registers, including
the program counter,
stack pointer
Operating System Concepts
3.7
Silberschatz, Galvin and Gagne ©2005
Context Switch
 Context-switch time is pure overhead; no useful work is done
 The switching time depends on the hardware support

Some systems (Sun UltraSPARC) provide multiple register sets
 very fast switching (just change a pointer)

Typical systems, few milliseconds for switching
Operating System Concepts
3.8
Silberschatz, Galvin and Gagne ©2005
Job Types
 Jobs (Processes) can be described as either:

I/O-bound process – spends more time doing I/O than
computations, many short CPU bursts

CPU-bound process – spends more time doing computations;
few very long CPU bursts
Operating System Concepts
3.9
Silberschatz, Galvin and Gagne ©2005
Scheduling: The Big Picture
 Consider a large computer system to which many jobs are submitted
 Initially, jobs go to the secondary storage (disk)
 Then, job scheduler chooses some of them to go to the memory
(ready queue)
 Then, CPU scheduler chooses from the ready queue a job to run on
the CPU
 Medium-term scheduler may move (swap) some partially-executed
jobs from memory to disk (to enhance performance)
Operating System Concepts
3.10
Silberschatz, Galvin and Gagne ©2005
Scheduling: The Big Picture (cont’d)
Midterm sched.
Jobs
Disk
Job sched.
CPU sched.
In most small and interactive systems (UNIX, WinXP, …),
only the CPU scheduler exists
Operating System Concepts
3.11
Silberschatz, Galvin and Gagne ©2005
Schedulers
 Long-term scheduler (or job scheduler)

Selects which processes should be brought into ready queue

Controls the degree of multiprogramming

Invoked infrequently (seconds, minutes)  (can be slow)

Should maintain a ‘good mix’ of CPU-bound and I/O-bound jobs in
the system
 Short-term scheduler (or CPU scheduler)

selects which process should be executed next and allocates CPU

Short-term scheduler is invoked very frequently (milliseconds) 
(must be fast)
 Medium-term scheduler

Operating System Concepts
Swap processes in and out of the ready queue to enhance
performance (i.e., maintain the good mix of jobs)
3.12
Silberschatz, Galvin and Gagne ©2005
Process Scheduling Queues
 Processes migrate among
various 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
Operating System Concepts
3.13
Silberschatz, Galvin and Gagne ©2005
Process Lifetime
Operating System Concepts
3.14
Silberschatz, Galvin and Gagne ©2005
Process Creation
 Parent process creates children processes, which, in turn create
other processes, forming a tree of processes
 Execution

Parent and children execute concurrently

Parent waits until children terminate
 Resource sharing can take the form (depending on the OS):

Parent and children share all resources

Children share subset of parent’s resources

Parent and children share no resources
Operating System Concepts
3.15
Silberschatz, Galvin and Gagne ©2005
Process Creation: Unix Example
 Process creates another process (child) by using fork system call

Child is a copy of the parent

Typically, child loads another program into its address space
using exec system

Parent waits for its children to terminate
Operating System Concepts
3.16
Silberschatz, Galvin and Gagne ©2005
C Program Forking Separate Process
int main()
{
pid_t pid;
pid = fork(); /* fork another process */
if (pid < 0) { /* error occurred */
fprintf (stderr, "Fork Failed");
exit(-1);
}
else if (pid == 0) { /* child process */
execlp ("/bin/ls", "ls", NULL);
}
else { /* parent process */
/* parent will wait for child to complete */
wait (NULL);
printf ("Child Complete");
exit(0);
Note: fork returns 0 to child and the pid of the
}
}
Operating System Concepts
new process to parent.
3.17
Silberschatz, Galvin and Gagne ©2005
A tree of processes on a typical Solaris
Operating System Concepts
3.18
Silberschatz, Galvin and Gagne ©2005
Process Termination
 Process executes last statement and asks the operating system to
delete it (exit)

Output data from child to parent (via wait)

Process’ resources are 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

If parent is exiting

Some operating system do not allow child to continue if its
parent terminates
–
Operating System Concepts
All children terminated - cascading termination
3.19
Silberschatz, Galvin and Gagne ©2005
Cooperating Processes
 Cooperating process can affect or be affected by the execution of
another process
 Why processes cooperate?

Information sharing

Computation speed-up

Modularity, Convenience
 Interprocess Communications (IPC) methods

Shared memory

Message passing
Operating System Concepts
3.20
Silberschatz, Galvin and Gagne ©2005
Interprocess Communications Models
Message Passing
Operating System Concepts
Shared Memory
3.21
Silberschatz, Galvin and Gagne ©2005
IPC: Shared Memory
 Processes communicate by creating a shared place in memory

One process creates a shared memory—shmget()

Other processes attach shared memory to their own address
space—shmat()

Then, shared memory is treated as regular memory

Synchronization is needed to prevent concurrent access to
shared memory (conflicts)
 Pros

Fast (memory speed)

Convenient to programmers (just regular memory)
 Cons

Need to manage conflicts (tricky for distributed systems)
Operating System Concepts
3.22
Silberschatz, Galvin and Gagne ©2005
IPC: Message Passing
 If processes P and Q wish to communicate, they need to:

establish a communication channel between them
 exchange messages via:
 send (message) – message size fixed or variable
 receive (message)
 Pros
No conflict  easy to exchange messages especially in
distributed systems
 Cons
 Overhead (message headers)
 Slow

prepare messages
 Kernel involvement: sender  kernel  receiver (several
system calls)

Operating System Concepts
3.23
Silberschatz, Galvin and Gagne ©2005
IPC: Message Passing (cont’d)
 Communication channel can be


Direct: Processes must name each other explicitly:

send (P, message) – send a message to process P

receive (Q, message) – receive a message from process Q
Indirect: Processes communicate via mailboxes (or ports)

Messages are sent to and received from mailboxes

Each mailbox has a unique id
Operating System Concepts
–
Send (A, message) – send a message to mailbox A
–
Receive (A, message) – receive a message from
mailbox A
3.24
Silberschatz, Galvin and Gagne ©2005
IPC: Message Passing (cont’d)

Synchronization: message passing is either



Blocking (or synchronous)

send () has the sender block until the message is received

receive () has the receiver block until a message is
available
Non-blocking (or asynchronous)

send () has the sender send the message and continue

receive () has the receiver receive a valid message or null
Buffering: Queue of messages attached to the comm. channel

Zero capacity – Sender must wait for receiver (rendezvous)

Bounded capacity – Sender must wait if link full

Unbounded capacity – Sender never waits
Operating System Concepts
3.25
Silberschatz, Galvin and Gagne ©2005
Summary
 Process is a program in execution

OS maintains process info in PCB

Process State diagram

Creating and terminating processes (fork)
 Process scheduling

Long-, short-, and medium-term schedulers

Scheduling queues
 Interprocess communication

Shared memory

Message passing
Operating System Concepts
3.26
Silberschatz, Galvin and Gagne ©2005