Transcript Chapter - 5th Semester Notes

Chapter 2
Processes
1
Processes
Topics
•
•
•
•
•
Process Concept
Process Scheduling
Operations on Processes
Cooperating Processes
Interprocess Communication
2
Process Concept
• An operating system executes a variety of programs:
– Batch system – jobs
– Time-shared systems – user programs or tasks
• Process – a program in execution; process execution
must progress in sequential fashion
• A process includes:
– program counter (Current activity)
– Stack
(Temporary Data)
– data section
(Global Variables)
3
Why Have Processes?
 Resource sharing ( logical (files) and physical
(hardware) ).
 Computation speedup - taking advantage of
multiprogramming – i.e. example of a
customer/server database system.
 Modularity for protection.
4
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. (I/O
Completion or reception of a signal).
– Ready: The process is waiting to be assigned to a processor.
– Suspended: Another process has explicitly told this process to
sleep. It will be awakened when a process explicitly awakens it.
– Terminated: The process has finished execution.
• Only one process can be running on any processor at any
instant.
5
Diagram of Process State
6
Suspended state and swapping
 Suspended : Another process has explicitly told this
process to sleep. It will be awakened when a process
explicitly awakens it.
• So far, all the processes had to be (at least partly) in main
memory
• The OS may need to suspend some processes, ie: to swap
them out to disk. We add 2 new states:
• Blocked Suspend: blocked processes which have been
swapped out to disk
• Ready Suspend: ready processes which have been
swapped out to disk
7
A Seven-state Process Model
8
New state transitions (mid-term scheduling)
• Blocked --> Blocked Suspend
– When all processes are blocked, the OS will make room
to bring a ready process in memory
• Blocked Suspend --> Ready Suspend
– When the event for which it has been waiting occurs
(state info is available to OS)
• Ready Suspend --> Ready
– when no more ready process in main memory
• Ready--> Ready Suspend (unlikely)
– When there are no blocked processes and must free
memory for adequate performance
9
Process Control Block (PCB)
Contains Information Associated With Each Process:
•
It's a data structure holding:

PC, CPU registers,

memory management information,

Accounting ( Amount of CPU used, ID, ... )

I/O status ( such as file resources ),

scheduling data ( relative priority, etc. )

Process State (so running, suspended, etc. is
simply a field in the PCB )
CPU Switch From Process to Process
11
Process Scheduling Queues
• Job queue – set of all processes entered in the system.
• Ready queue
– Set of all processes residing in main memory, and are ready and
waiting to execute.
– Header will contain pointers to the first and last PCBs in the list.
• Device queues – set of processes waiting for an I/O
device.
• Process migration between the various queues.
12
Ready Queue And Various I/O Device
Queues
13
Representation of Process Scheduling
14
Schedulers
• Long-term scheduler (or job scheduler) – selects which
processes should be brought into the ready queue.
• Medium-term scheduling
– Swaps processes out to secondary storage
– Scheduling involves suspending or resuming
processes by swapping (rolling) them out of or into
memory.
• Short-term scheduler (or CPU scheduler) – selects which
process should be executed next and allocates CPU.
15
Life cycle of a typical process
16
Addition of Medium Term Scheduling
17
Schedulers (Cont.)
• Short-term scheduler is invoked very frequently
(milliseconds)  (must be fast).
• Long-term scheduler is invoked very 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 – 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.
18
Dispatcher (short-term scheduler)
• Swaps processes out to secondary storage.
• It prevents a single process from monopolizing
processor time.
• It decides who goes next according to a scheduling
algorithm. (chapter 6)
• The CPU will always execute instructions from the
dispatcher while switching from process A to process B.
19
Dispatcher at work
20
Context Switch
• When an event occurs, the operating system saves the
state of the active process and restores the state of the
interrupt service routine (ISR). This mechanism is called a
Context Switch.
• What must get saved? Everything that the next process
could or will damage. For example:
–
–
–
–
Program counter
CPU registers
File access pointer
Memory
• While saving the state, the operating system should mask
(disable) all interrupts.
21
Memory: to save or NOT to save
• Here are the possibilities:
• Save all memory onto disk.
– Could be very time-consuming. E.g., assume data transfers to disk
at 1MB/sec. How long does saving a 4MB process take?
• Don't save memory; trust next process.
• This is the approach taken by PCs.
• Isolate (protect) memory from next process. This is
memory management,
22
Process Creation
• Parent process create children processes, which, in turn
create other processes, forming 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.
23
Process Creation (Cont.)
• Address space
– Child duplicate of parent.
– Child has a program loaded into it.
• UNIX examples
– fork system call creates new process
– exec system call used after a fork to replace the
process’ memory space with a new program.
24
A fork() System Call
25
Process Creation
26
A exec() System Call
27
Process Creation
• Parent process create children processes, which, in turn
create other processes, forming a tree of processes.
Processes Tree on a UNIX System
28
Process Termination
• Process executes its last statement and asks the operating
system to delete it by using the exit system call.
– Process may return data (output) to its parent (via wait system
call).
– Process’ resources are deallocated by operating system.
• Parent may terminate execution of children processes (via
system call abort).
– Child has exceeded allocated resources.
– Task assigned to child is no longer required.
– Parent is exiting, and the operating system does not allow a child
to continue if its parent terminates.
29
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
• Several users may be interested in the same piece of information (a
shared file).
30
Cooperating Processes (Contd..)
– Computation speed-up
• We want a particular task to run faster, we must break it into
subtasks, each of which will be executing in parallel with the
others. (Multiple processing elements CPUs)
– Modularity
• Construct the system in a modular fashion, dividing the system
functions into separate processes.
– Convenience
• An individual user may have many tasks to work on at one time.
(Editing, printing and compiling in parallel).
31
Interprocess Communication (IPC)
• Mechanism for processes to communicate and to
synchronize their actions.
• Message system – processes communicate with each other
without resorting to shared variables.
• IPC facility provides two operations:
– Send (message) – message size fixed or variable
– Receive (message)
32
Interprocess Communication (IPC)
• If P and Q wish to communicate, they need to:
– establish a communication link between them
– exchange messages via send/receive
• Implementation of communication link
– physical (e.g., shared memory, hardware bus)
– logical (e.g., logical properties)
33
Direct Communication
• Processes that wants to communicate must explicitly name
the recipient or sender of comm. :
– send (P, message) – send a message to process P
– receive(Q, message) – receive a message from process Q
• Properties of communication link
– Links are established automatically.
– A link is associated with exactly one pair of
communicating processes.
– Between each pair there exists exactly one link.
– The link may be unidirectional, but is usually bidirectional.
34
Indirect Communication
• Messages are directed and received from mailboxes (also
referred to as ports).
– Each mailbox has a unique id.
– Processes can communicate only if they share a mailbox.
• Properties of communication link
– Link established only if processes share a common
mailbox
– A link may be associated with many processes.
– Each pair of processes may share several communication
links.
– Link may be unidirectional or bi-directional.
35
Indirect Communication
• Operations
– create a new mailbox
– send and receive messages through mailbox
– destroy a mailbox
• Primitives are defined as:
send(A, message) – send a message to mailbox A
receive(A, message) – receive a message from mailbox A
36
Indirect Communication
• Mailbox sharing
– P1, P2, and P3 share mailbox A.
– P1, sends; P2 and P3 receive.
– Who gets the message?
• Solutions
– Allow a link to be associated with at most two
processes.
– Allow only one process at a time to execute a receive
operation.
– Allow the system to select arbitrarily the receiver.
– Sender is notified who the receiver was.
37
Buffering
•
Queue of messages attached to the link; implemented
in one of three ways.
1. Zero capacity – 0 messages (Max. length = 0)
Sender must wait until the recipient receives the
message.
2. Bounded capacity – finite length of n messages
at most n messages can reside in the queue.
Sender must wait if link full.
3. Unbounded capacity – infinite length
Sender never waits.
38