Transcript Operating System Concepts

Operating System
Principles
Ku-Yaw Chang
[email protected]
Assistant Professor, Department of
Computer Science and Information Engineering
Da-Yeh University
Chapter 3 Process Concept
A process

A program in execution
A system consists of a collection of processes

OS processes
System code

User processes
User code
All processes are executed concurrently


Switching the CPU between processes
Make the computer more productive
Ku-Yaw Chang
Chapter 3 Process Concept
2
Chapter 3 Process Concept
1.
2.
3.
4.
5.
6.
7.
8.
Overview
Process Scheduling
Operations on Processes
Interprocess Communication
Examples of IPC Systems
Communication in Client-Server Systems
Summary
Exercises
Ku-Yaw Chang
Chapter 3 Process Concept
3
3.1 Overview
An operating system executes a variety of
programs


Batch system – jobs
Time-shared systems – user programs or tasks
All these activities are similar


Called processes
The terms job and process are used almost
interchangeably
Ku-Yaw Chang
Chapter 3 Process Concept
4
3.1.1 The Process
A process is a program in execution

Text section

Stack
Temporary data
Program code

Data section

Current activity
Program counter
Contents of registers
Global variables

Heap
Dynamically allocated memory
An active entity

A program is a passive entity
Two processes may be associated with the
same program
Ku-Yaw Chang
Chapter 3 Process Concept
5
Process in Memory
Ku-Yaw Chang
Chapter 3 Process Concept
6
3.1.2 Process State
As a process executes, it changes state.
Each process may be in one of the following states

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.
Only one process can be running on any processor at
any instant.
Ku-Yaw Chang
Chapter 3 Process Concept
7
Diagram of process state
Ku-Yaw Chang
Chapter 3 Process Concept
8
3.1.3 Process Control Block
Each process is presented by a process control
block (PCB) – also called a task control block.


Process state
Program counter
The address of the next instruction to be executed

CPU registers
Vary in number and type, depending on the computer
architecture
Accumulators, index registers, stack pointer, generalpurpose registers..

CPU scheduling information
A process priority, pointers to scheduling queues…
Ku-Yaw Chang
Chapter 3 Process Concept
9
3.1.3 Process Control Block

Memory-management information
Base and limit registers
Page or segment tables

Accounting information
The amount of CPU, real time used, time limits…

I/O status information
A list of I/O devices allocated to this process
A list of open files
Repository for any information that may vary
from process to process

Context switch
Save/load the state of the old/new process
Ku-Yaw Chang
Chapter 3 Process Concept
10
Process control block (PCB)
Ku-Yaw Chang
Chapter 3 Process Concept
11
Diagram showing CPU
switch from process to process
Ku-Yaw Chang
Chapter 3 Process Concept
12
3.1.4 Threads
A process is a program that performs a
single thread of execution.

Could not simultaneously type in characters
and run the spell checker within the same
process
Extend the process concept to allow a
process to have multiple threads of
execution.
Ku-Yaw Chang
Chapter 3 Process Concept
13
Chapter 3 Process Concept
1.
2.
3.
4.
5.
6.
7.
8.
Overview
Process Scheduling
Operations on Processes
Interprocess Communication
Examples of IPC Systems
Communication in Client-Server Systems
Summary
Exercises
Ku-Yaw Chang
Chapter 3 Process Concept
14
3.2 Process Scheduling
Multiprogramming

Have some processes running at all times
To maximize CPU utilization
Time-sharing

Switch CPU among processes so frequently
Users can interact with each program while it is running
Ku-Yaw Chang
Chapter 3 Process Concept
15
3.2.1 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.
each device has its own device queue
Other queues
Ku-Yaw Chang
Chapter 3 Process Concept
16
The ready queue and
various I/O device queues
Ku-Yaw Chang
Chapter 3 Process Concept
17
Queueing-diagram representation
of process scheduling
Ku-Yaw Chang
Chapter 3 Process Concept
18
3.2.2 Schedulers
A process migrates between various scheduling
queues throughout its lifetime.

Carried out by the appropriate scheduler
Long-term scheduler (or job scheduler)

select which processes should be brought into the
ready queue (load into memory for execution)
Short-term scheduler (or CPU scheduler)

select which process should be executed next and
allocate CPU
Ku-Yaw Chang
Chapter 3 Process Concept
19
3.2.2 Schedulers
Primary distinction between these two
schedulers

The frequency of their execution
Short-term executes frequently

Must be fast.
Long-term executes much less frequently


Ku-Yaw Chang
Control the degree of multiprogramming – the number of
processes in memory
Afford to take more time to select a process
Chapter 3 Process Concept
20
3.2.2 Schedulers
Processes can be described as

I/O-bound process
spend more time doing I/O than computations

CPU-bound process
spend more time doing computations
Best performance

A combination of CPU-bound and I/O-bound
processes
Long-term scheduler
Ku-Yaw Chang
Chapter 3 Process Concept
21
3.2.2 Schedulers
Long-term scheduler may be absent or minimal.


Put every process in memory for the
short-term scheduler
Stability depends on
Physical limitation
Self-adjusting nature of human users
Ku-Yaw Chang
Chapter 3 Process Concept
22
3.2.2 Schedulers
Medium-term scheduler

Remove processes from memory (swap out)
Reduce the degree of multiprogramming

Reintroduce the process and continue its execution
(swap in)
Such a scheme is called swapping

May be necessary to
Improve the process mix
A change in memory requirement has overcommitted
available memory
Ku-Yaw Chang
Chapter 3 Process Concept
23
Addition of
medium-term scheduling
Ku-Yaw Chang
Chapter 3 Process Concept
24
3.2.3 Context Switch
Context Switch

When CPU switches to another process, the
system must
save the state of the old process
load the saved state for the new process

Context-switch time
pure overhead

the system does no useful work while switching.
highly depend on hardware support

Ku-Yaw Chang
Multiple sets of registers
Chapter 3 Process Concept
25
Chapter 3 Process Concept
1.
2.
3.
4.
5.
6.
7.
8.
Overview
Process Scheduling
Operations on Processes
Interprocess Communication
Examples of IPC Systems
Communication in Client-Server Systems
Summary
Exercises
Ku-Yaw Chang
Chapter 3 Process Concept
26
3.3 Operations on Processes
Processes can execute concurrently

Be created and deleted dynamically
OS must provide a mechanism (or facility) for
process creation and termination.
Ku-Yaw Chang
Chapter 3 Process Concept
27
3.3.1 Process Creation
A process may create new processes

Create-process system call
The creating process is called a parent process,
whereas the new processes are called the
children of that process.

May form a tree of processes
Each process is identified by its unique
process identifier (PID)

An integer number
Ku-Yaw Chang
Chapter 3 Process Concept
28
A tree of processes on a typical
Solaris system
Ku-Yaw Chang
Chapter 3 Process Concept
29
3.3.1 Process Creation
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.
Address space


Child is a duplicate of the parent.
Child has a program loaded into it.
Ku-Yaw Chang
Chapter 3 Process Concept
30
3.3.1 Process Creation
UNIX example

fork system call creates a new process
A copy of the address space of the original process

execlp system call used after a fork to replace the
process’ memory space with a new program.
Ku-Yaw Chang
Chapter 3 Process Concept
31
C Program
Forking a Separate Process
pid_t pid = fork();
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 */
wait(NULL);
printf(“Child Complete”);
exit(0);
}
Ku-Yaw Chang
Chapter 3 Process Concept
32
Process Creation
Ku-Yaw Chang
Chapter 3 Process Concept
33
3.3.1 Process Creation
Windows example

CreateProcess Win32 API creates new process
STARTUPINFO: specify many properties of the new process
PROCESS_INFORMATION: contain a handle and the
identifiers to the newly created process and its thread
Ku-Yaw Chang
Chapter 3 Process Concept
34
3.3.2 Process Termination
Process executes last statement and asks the operating
system to delete it (use exit system call).


Output data from child to parent (via wait system call).
Process’ resources are deallocated by operating system.
Parent may terminate execution of children processes
(abort system call).



Child has exceeded allocated resources.
Task assigned to child is no longer required.
Parent is exiting.
Operating system does not allow a child to continue if its parent
terminates.
Cascading termination
Ku-Yaw Chang
Chapter 3 Process Concept
35
Chapter 3 Process Concept
1.
2.
3.
4.
5.
6.
7.
8.
Overview
Process Scheduling
Operations on Processes
Interprocess Communication
Examples of IPC Systems
Communication in Client-Server Systems
Summary
Exercises
Ku-Yaw Chang
Chapter 3 Process Concept
36
3.4 Interprocess Communication
Independent process

A process cannot affect or be affected by the
execution of another process.
Cooperating process

A process can affect or be affected by the execution
of another process
Reasons for process cooperation




Information sharing
Computation speed-up
Modularity
Convenience
Ku-Yaw Chang
Chapter 3 Process Concept
37
3.4 Interprocess Communication
Cooperating processes require an interprocess
communication (IPC) mechanism

To exchange data and information
Two fundamental models

Shared memory
A region of memory that is shared by cooperating processes
is established.

Message passing
Messages are exchanged between cooperating processes
Most operating systems implement both
Ku-Yaw Chang
Chapter 3 Process Concept
38
Communication Models
Ku-Yaw Chang
Chapter 3 Process Concept
39
3.4 Interprocess Communication
Shared memory

Fast access
At memory speed

Problems exist
Protection and synchronization

Suitable for large amounts of data
Message passing

Slow access
Require kernel intervention


Easy to implement
Suitable for small amounts of data
Ku-Yaw Chang
Chapter 3 Process Concept
40
3.4.1 Shared-Memory Systems
Normally, OS prevents one process from
accessing another process’s memory
Shared-memory


One process creates the shared-memory segment
Other processes attach it to their address space
Exchange information by reading and writing
data in the shared areas


Not under OS’s control
Process are responsible for ensuring not to write to
the same location simultaneously
Ku-Yaw Chang
Chapter 3 Process Concept
41
3.4.1 Shared-Memory Systems
Producer-Consumer Problem


A producer process produces information that is
consumed by a consumer process.
The producer and consumer must be synchronized.
A buffer can be provided


Filled by the producer
Emptied by the consumer
Two types of buffers

unbounded-buffer
no practical limit on the size of the buffer

bounded-buffer
a fixed buffer size
Ku-Yaw Chang
Chapter 3 Process Concept
42
Producer-Consumer Problem
Bounded-buffer

Shared-memory solution
Shared data
#define BUFFER_SIZE 10
typedef struct {
...
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
Ku-Yaw Chang
Chapter 3 Process Concept
43
Producer-Consumer Problem
The share buffer is a circular array with two
logical pointers



in : the next free position in the buffer
out : the first full position in the buffer
Empty buffer
in == out

Full buffer
( (in+1) % BUFFER_SIZE) == out

At most BUFFER_SIZE – 1 items
Ku-Yaw Chang
Chapter 3 Process Concept
44
Producer Process
item nextProduced;
while (1) {
while (((in + 1) % BUFFER_SIZE) == out)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
}
Ku-Yaw Chang
Chapter 3 Process Concept
45
Consumer Process
item nextConsumed;
while (1) {
while (in == out)
; /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
}
Ku-Yaw Chang
Chapter 3 Process Concept
46
3.4.2 Message-Passing Systems
Allow processes to communicate and to synchronize
their actions


Without sharing the same address space
Useful in a distributed environment
Two operations

send(message) and receive(message)
Messages could be

Fixed size
Straightforward system-level implementation
More difficult programming

Variable size
More complex system-level implementation
Simpler programming
Ku-Yaw Chang
Chapter 3 Process Concept
47
3.4.2 Message-Passing Systems
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)
Ku-Yaw Chang
Chapter 3 Process Concept
48
3.4.2 Message-Passing Systems
Several methods for logical implementation



Direct or indirect communication
Synchronous or asynchronous communication
Automatic or explicit buffering
Ku-Yaw Chang
Chapter 3 Process Concept
49
3.4.2.1 Naming
Direct communication

Explicitly name the recipient or sender of the
communication
send (P, message) – send a message to process P
receive(Q, message) – receive a message from process Q

Properties
A link is established automatically between every pair of
processes that want to communicate.

Know each other’s identity
A link is associated with exactly two processes.
Exactly one link exists between each pair of processes.
Ku-Yaw Chang
Chapter 3 Process Concept
50
3.4.2.1 Naming
Symmetry in addressing

Both the sender and the receiver must name the
other to communicate
Asymmetry in addressing


Only the sender name the recipient
The recipient is not required to name the sender
send (P, message) – send a message to process P
receive(id, message) – receive a message from any process

id is set to the name of the process with which communication
has taken place
Disadvantage in both schemes

Limited modularity
Ku-Yaw Chang
Chapter 3 Process Concept
51
3.4.2.1 Naming
Indirect communication

Messages are sent to and received from mailboxes or
ports.
Each mailbox has a unique identification

send and receive primitives
send (A, message) – send a message to mailbox A
receive(A, message) – receive a message from mailbox A

Properties
A link is established only if processes have a shared mailbox
A link may be associated with more than two processes.
Each pair of processes may share several communication
links.
Ku-Yaw Chang
Chapter 3 Process Concept
52
3.4.2.1 Naming
A mailbox is owned by

A process
the owner(receive) and the user(send)

The operating system
Not attached to any particular process
Provide a mechanism that allows a process to



Ku-Yaw Chang
Create a new mailbox
Send and receive messages through the mailbox
Delete a mailbox
Chapter 3 Process Concept
53
3.4.2.2 Synchronization
Message passing may be either blocking (synchronous)
or nonblocking (asynchronous)

Blocking send
The sending process is blocked until the message is received.

Nonblocking send
The sending process sends the message and resumes operation.

Blocking receive
The receiver blocks until a message is available.

Nonblocking receive
The receive retrieve either a valid message or a null.
A rendezvous

Both the send and receive are blocking
Ku-Yaw Chang
Chapter 3 Process Concept
54
3.4.2.3 Buffering
Messages exchanged by communicating
processes reside in a temporary queue.

Zero capacity
Maximum length is 0
The sender must block until the recipient receives the
message.

Bounded capacity
A finite length n
The sender must block until the space is available in the
queue.

Unbounded capacity
An infinite length
The sender never blocks.
Ku-Yaw Chang
Chapter 3 Process Concept
55
Chapter 3 Process Concept
1.
2.
3.
4.
5.
6.
7.
8.
Overview
Process Scheduling
Operations on Processes
Interprocess Communication
Examples of IPC Systems
Communication in Client-Server Systems
Summary
Exercises
Ku-Yaw Chang
Chapter 3 Process Concept
56
Examples of IPC Systems
P.100 - P.105
Ku-Yaw Chang
Chapter 3 Process Concept
57
Chapter 3 Process Concept
1.
2.
3.
4.
5.
6.
7.
8.
Overview
Process Scheduling
Operations on Processes
Interprocess Communication
Examples of IPC Systems
Communication in Client-Server Systems
Summary
Exercises
Ku-Yaw Chang
Chapter 3 Process Concept
58
3.6.1 Sockets
A socket


An endpoint for communication
Identified by an IP address concatenated with a port
number
The socket 161.25.19.8:1625 refers to port 1625 on host
161.25.19.8
Client-server

The server waits for incoming client requests by
listening to a specific port
Port 23: telnet
Port 21: ftp
Port 80: http

All ports below 1024 are considered well known.
Ku-Yaw Chang
Chapter 3 Process Concept
59
Communication using sockets
146.86.5.20/1625
Ku-Yaw Chang
Chapter 3 Process Concept
60
3.6.1 Sockets
Java provides three different types of sockets.

Connection-oriented (TCP) sockets
Socket class

Connectionless (UDP) sockets
DatagramSocket class

Multicast
MulticastSocket class
Low-level communication

Sockets : an unstructured stream
High-level communication


RPC : remote procedure calls
RMI : remote method invocation
Ku-Yaw Chang
Chapter 3 Process Concept
61
3.6.2 Remote Procedure Calls
Remote procedure call (RPC) abstracts
procedure calls between processes on
networked systems.
A stub

Client-side proxy
locate the server and marshall parameters.

Server-side proxy
receive this message, unmarshall parameters, and perform
the procedure on the server.
Data representation

Machine independent : external data representation
(XDR)
Ku-Yaw Chang
Chapter 3 Process Concept
62
3.6.2 Remote Procedure Calls
Semantics of a call


Local procedure calls fail only under extreme circumstances
RPC can fail, or be duplicated, due to common network errors
Attach each message a timestamp

Acted on at most once
Communication


Binding can be predetermined
Binding can be done dynamically by a rendezvous mechanism
A rendezvous daemon ( also called a matchmaker ) on a fixed PRC
port
Features


Ku-Yaw Chang
More flexible
Extra overhead
Chapter 3 Process Concept
63
Execution of a RPC
Ku-Yaw Chang
Chapter 3 Process Concept
64
Execution of a RPC
Ku-Yaw Chang
Chapter 3 Process Concept
65
3.6.3 Remote Method Invocation
A Java mechanism similar to RPCs.

allow a Java program to invoke a method on a
remote object
In a different Java virtual machine
Differences with PRC


Invocations of methods on remote objects
Possible to pass objects as parameters
Object serialization

Stub/skeleton
Ku-Yaw Chang
Chapter 3 Process Concept
66
Remote method invocation
Ku-Yaw Chang
Chapter 3 Process Concept
67
Marshalling parameters
Ku-Yaw Chang
Chapter 3 Process Concept
68
Chapter 3 Process Concept
1.
2.
3.
4.
5.
6.
7.
8.
Overview
Process Scheduling
Operations on Processes
Interprocess Communication
Examples of IPC Systems
Communication in Client-Server Systems
Summary
Exercises
Ku-Yaw Chang
Chapter 3 Process Concept
69
Summary
P.113 - P.114
Ku-Yaw Chang
Chapter 3 Process Concept
70
Chapter 3 Process Concept
1.
2.
3.
4.
5.
6.
7.
8.
Overview
Process Scheduling
Operations on Processes
Interprocess Communication
Examples of IPC Systems
Communication in Client-Server Systems
Summary
Exercises
Ku-Yaw Chang
Chapter 3 Process Concept
71
Exercises
3-1
3-2
3-4
Ku-Yaw Chang
Chapter 3 Process Concept
72
The End