lOMoARcPSD|53420317

Chap3 Processes in

nguyên lí hệ điều hành (Trường Đại học Cần Thơ)

messages.pdf_cover_qr_code_label

messages.studocu_not_sponsored_or_endorsed_by_college
messages.downloaded_by
 lOMoARcPSD|53420317

Outline
1. Process Concept
Operating Systems
2. Process Scheduling
3. Operations on Processes
Chapter 3
4. Interprocess Communication
Processes
LECTURER: LAM NHUT KHANG

Slides are either from or adapted from

Operating System Concepts 10th Ed. Silberschatz, Galvin, Gagne, 2018.

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 2

Process Concept The Process

An operating system executes a variety of programs: Multiple parts
Batch system jobs The program code, also called text section
Time-shared systems user programs or tasks Current activity including program counter, processor registers
Stack containing temporary data
We use the terms job and process interchangeably Function parameters, return addresses, local variables
Data section containing global variables
Process a program in execution; process execution must Heap containing memory dynamically allocated during run time
progress in sequential fashion
Program is passive entity, process is active
A process includes: Program becomes process when executable file loaded into memory
program counter
stack One program can be several processes
data section Consider multiple users executing the same program

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 3 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 4

messages.downloaded_by
 lOMoARcPSD|53420317

Process in Memory 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 processor
terminated: The process has finished execution

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 5 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 6

Diagram of Process State 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

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 7 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 8

messages.downloaded_by
 lOMoARcPSD|53420317

CPU Switch From Process to

Process Control Block (PCB) Process

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 9 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 10

Ready Queue And Various

Process Scheduling I/O Device Queues
Maximize CPU use, quickly switch processes onto CPU for
time sharing
Process scheduler selects among available processes for next
execution on CPU
Maintains scheduling queues of processes
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
Processes migrate among the various queues

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 11 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 12

messages.downloaded_by
 lOMoARcPSD|53420317

Representation of Process
Scheduling Schedulers
Long-term scheduler (or job scheduler) selects which
Job queue
processes should be brought into the ready queue
Short-term scheduler (or CPU scheduler) selects which
process should be executed next and allocates CPU
Sometimes the only scheduler in a system

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 13 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 14

Addition of Medium Term

Schedulers (Cont.) Scheduling
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

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 15 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 16

messages.downloaded_by
 lOMoARcPSD|53420317

Process Creation Process Creation

Parent process create children processes, which, in turn create
other processes, forming a tree of processes
Generally, process identified and managed via a process identifier
(pid)
Resource sharing
Parent and children share all resources

Parent and child share no resources

Execution
Parent and children execute concurrently
Parent waits until children terminate

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 17 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 18

A Tree of Processes on Solaris Process Termination

Process executes last statement and asks the operating system
to delete it (exit)
Output data from child to parent (via wait)

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 systems do not allow child to continue if its parent terminates
All children terminated - cascading termination

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 19 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 20

messages.downloaded_by
 lOMoARcPSD|53420317

Interprocess Communication Communications Models

Processes within a system may be independent or cooperating
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, including
sharing data
Reasons for cooperating processes:
Information sharing
Computation speedup
Modularity
Convenience
Cooperating processes need interprocess communication (IPC)
Two models of IPC
Shared memory
Message passing

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 21 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 22

Bounded-Buffer
Producer-Consumer Problem Shared-Memory Solution
Paradigm for cooperating processes, producer process Shared data
produces information that is consumed by a consumer process #define BUFFER_SIZE 10
typedef struct {
unbounded-buffer places no practical limit on the size of the buffer
...
bounded-buffer assumes that there is a fixed buffer size } item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;

Solution is correct, but can only use BUFFER_SIZE-1

elements

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 23 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 24

messages.downloaded_by
 lOMoARcPSD|53420317

Bounded-Buffer Producer Bounded Buffer Consumer

while (true) {
while (true) {
/* Produce an item */ while (in == out)
while (((in = (in + 1) % BUFFER SIZE) == out)
; // do nothing -- nothing to consume
; /* do nothing -- no free buffers */
buffer[in] = item;
in = (in + 1) % BUFFER SIZE; // remove an item from the buffer
} item = buffer[out];
out = (out + 1) % BUFFER SIZE;
return item;
}

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 25 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 26

Interprocess Communication
Message Passing Implementation Questions
Mechanism for processes to communicate and to synchronize their actions How are links established?
Message system processes communicate with each other without
resorting to shared variables Can a link be associated with more than two processes?
IPC facility provides two operations: How many links can there be between every pair of
send(message) message size fixed or variable
receive(message) communicating processes?
If P and Q wish to communicate, they need to: What is the capacity of a link?
establish a communication link between them
exchange messages via send/receive
Is the size of a message that the link can accommodate fixed
Implementation of communication link or variable?
physical (e.g., shared memory, hardware bus)
logical (e.g., logical properties) Is a link unidirectional or bi-directional?
LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 27 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 28

messages.downloaded_by
 lOMoARcPSD|53420317

Direct Communication Indirect Communication

Processes must name each other explicitly: Messages are directed and received from mailboxes (also
send (P, message) send a message to process P referred to as ports)
receive(Q, message) receive a message from process Q Each mailbox has a unique id
Processes can communicate only if they share a mailbox
Properties of communication link
Links are established automatically Properties of communication link
A link is associated with exactly one pair of communicating processes Link established only if processes share a common mailbox
Between each pair there exists exactly one link A link may be associated with many processes
The link may be unidirectional, but is usually bi-directional Each pair of processes may share several communication links
Link may be unidirectional or bi-directional

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 29 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 30

Indirect Communication Indirect Communication

Operations Mailbox sharing
create a new mailbox P1, P2, and P3 share mailbox A
send and receive messages through mailbox P1, sends; P2 and P3 receive
destroy a mailbox Who gets the message?

Primitives are defined as: Solutions

Allow a link to be associated with at most two processes
send(A, message) send a message to mailbox A Allow only one process at a time to execute a receive operation
receive(A, message) receive a message from mailbox A Allow the system to select arbitrarily the receiver. Sender is notified who the
receiver was.

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 31 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 32

messages.downloaded_by
 lOMoARcPSD|53420317

Synchronization Buffering
Message passing may be either blocking or non-blocking Queue of messages attached to the link; implemented in one of
Blocking is considered synchronous three ways
1. Zero capacity 0 messages
Blocking send: the sending process is blocked until the message is received Sender must wait for receiver (rendezvous)
by the receiving process or by the mail box
2. Bounded capacity finite length of n messages
Blocking receive: the receiver blocks until a message is available Sender must wait if link full
Non-blocking is considered asynchronous 3. Unbounded capacity infinite length
Sender never waits
Non-blocking send: the sender sends the message and continue
Non-blocking receive: the receiver receives a valid message or null

LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 33 LNK_CT178 REF. OPERATING SYSTEM CONCEPTS. SILBERSCHATZ, GALVIN, GAGNE©2009. 34

End of Chapter 3

messages.downloaded_by