Transcript ppt
Chapter 3: Process Concept
Lecture 3, 9.30.2008
Hao-Hua Chu
1
A fun project: Lucid Touch (MSR)
• What more can we extend
from multi-touch UI?
– Use both front and back surfaces
for interaction
2
Menu (are you hungry?)
• What is a process?
– Process lifecycle, process state, process control block, process vs.
thread
• Process scheduling
– Long-term vs. short-term schedulers, ready vs. I/O queues,
context switching
• Interprocess communication
– Shared memory vs. message passing
• Client-server communication
– Socket, RPC vs. RMI
3
Process overview
• What is a program?
– A file containing instructions to be executed
• What is a process (also called a “job”)?
– A program in execution on the computer
• What resources does OS provide to run a process (a web
browser process)?
– CPU, Memory, file (I/O), network (I/O)
• What is a process made up of in memory?
• What is the lifecycle of a process?
4
Process in Memory
• Text: program code
• Stack: temporary data (local
variable, function parameters,
return addresses)
• Data: global variables
• Heap: dynamic allocated
memory, malloc()
• Process info not kept in
memory:
– Program counters & registers
5
Process Lifecycle
• What is the process lifecycle (and the 5 process state)?
– Think about a web browser from birth to death …
6
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
• Multiprogramming!
– What is the benefit?
– What is the cost?
7
Process Control Block (PCB)
• What info does the system
need to track for each
process?
– Save & reload each time the
process goes in/out of the
“running” state.
8
Process Control Block (PCB)
• What info does the system
need to track for each
process?
– Save & reload each time the
process goes in/out of the
“running” state.
– CPU-related
– Memory-related
– I/O related
– Accounting
– See 3.1.3 for a complete list
9
Process vs. Thread
• Why thread?
– Say you start several web
browsers, each with its own
process.
– What is the “memory” overhead?
– Is there a way to reduce this
memory overhead?
– What memory sections can be
shared vs. cannot be shared?
10
Process Scheduling
• Go back to multiprogramming
• What is the benefit of multiprogramming?
– At the system-level: Maximize CPU utilization
– At the user-level: Users can interact with several programs almost
at the same time.
• What is the cost of providing multiprogramming?
– Consider that only one running process per processor
– Scheduling (overhead): decide the next “ready” process to run
and dispatch it.
• Let’s look at scheduling data structure (& algorithms)
– Called “queues”
11
Ready and I/O 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
• Processes migrate among
the various queues
12
Process Migration among Queues
13
Process Scheduler
• Short-term scheduler
– Select the next ready process to execute on CPU
• Also called CPU scheduler
– What makes a good short-term scheduling algorithm (more on Ch5)?
• Long-term scheduler (in a batch system)
– Select process(es) into the memory (and the ready queue)
– Keep short-term schedule busy!
– How does it differ from
short-term scheduler?
– What makes a good longterm scheduling algorithm?
14
Long vs. Short-term Schedulers
• Short-term scheduler is invoked very frequently
(milliseconds) (must be fast)
– Context switch processes overhead is fast but significant
– Say 1 ms, out of time quantum 20 ms -> Overhead 5%
• Long-term scheduler is invoked very infrequently (seconds,
minutes) (may be slow)
– Swapping processes (between disk and memory) is slow
• The long-term scheduler controls the degree of
multiprogramming (# of processes in memory)
• What makes a “good” degree of multiprogramming?
15
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
• Want to have a good process mix of both
– Keep both CPU and I/O busy!
• What happen when most processes are I/O bound?
• What happen when most processes are CPU bound?
16
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
17
Process Operations
• Review from “System programming class”.
• Process creation
– Parent-child tree relationship
– Process identifier called PID
– Resource sharing
• Process termination
18
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
19
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
Process Creation
C Program Forking Separate Process
int main()
{
Pid_t pid;
/* fork another process */
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 */
/* parent will wait for the child to complete */
wait (NULL);
printf ("Child Complete");
exit(0);
}
}
A tree of processes on a typical
Solaris
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
– All children terminated - cascading termination
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
– Communicate or share data
– Need for OS support on interprocess communication (IPC)
Two IPC Mechanisms
• How can two (or more) processes communicate data?
– Shared memory and message passing
Shared memory vs. Message passing
• What is shared memory?
– Create a “shared memory region” between two processes
– Exchange data by reading and writing to this shared region.
• What is message passing?
– Create mailboxes between two processes to exchange data
• No perfect thing …
– What are their strengths and
weaknesses?
– Think performance & concurrency
– Systems people call it “Tradeoff”
Shared-memory vs. Messagepassing
• Shared memory
–
–
–
–
OS does less work
Only one-time setup overhead
Fast communication, same as memory access time
Concurrent write to shared memory by both processes?
• Message passing
– OS does more work
– Data double-copy
– No concurrent read & write problem
Producer-Consumer Problem
• As an example to illustrate the “concurrency problem” for
shared memory
• 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
Bounded-Buffer: Shared-Memory
Solution
• Shared data (in the shared memory)
#define BUFFER_SIZE 10
Typedef struct {
...
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
• Solution is correct, but can only use BUFFER_SIZE-1
elements
Bounded-Buffer: Concurrent access to
shared memory buffer (2 producers)
Insert()
Remove()
while (true) {
/* Produce an item */
while (((in + 1) % BUFFER_SIZE)
== out)
; /* do nothing -- no free
buffers */
buffer[in] = item;
in = (in + 1) % BUFFER SIZE;
}
while (true) {
while (in == out)
; // do nothing -- nothing to
consume
// remove an item from the
buffer
item = buffer[out];
out = (out + 1) % BUFFER SIZE;
return item;
}
Message-Passing
• IPC facility provides 2 basic operations
– send(message) – message size fixed or variable
– receive(message)
• If P and Q wish to communicate, they need to:
– Establish a communication link between them
– Exchange messages via send/receive
• Implementation details …
– Direct vs. indirect communication
– Synchronous vs. asynchronous communication
– Buffering size
Message-Passing Implementation
Details
• Direct vs. indirect communication
–
–
–
–
–
Direct: send (P, message) & receive (Q, message)
Disadvantage: when either P/Q dies, re-establish communication
How to solve this issue?
Indirection using a “mailbox” or “port”
send (A, message) & receive (A, message), where A is a mailbox
• Synchronous vs. asynchronous communication
– Blocking/noblocking send/receive
• Buffering size
– Zero, bounded, and unbounded capacity
– How to implement zero or bounded capacity?
– What are their advantages & disadvantages?
Client-Server Communication
• Process communication across two different computers
– Not IPC (on the same machine)
• Sockets
• Remove procedure call (RPC)
• Remote method call (RMI) in Java
Sockets
• A socket is defined as an
endpoint for communication
• Concatenation of IP address
and port
• The socket 161.25.19.8:1625
refers to port 1625 on host
161.25.19.8
• Communication consists
between a pair of sockets
Remote Procedure Calls (RPC)
• Call the function of a process running on another machine
– Calling a remote function as easy as calling a “local function”
– Used extensively in distributed file system (calling file servers)
• Stubs – client-side proxy for the actual procedure on the
server.
• The client-side stub locates the server and marshalls the
parameters.
• The server-side stub receives this message, unpacks the
marshalled parameters, and performs the procedure on
the server.
Execution of RPC
Remote Method Invocation (RMI)
• Java objected-oriented version of RPC
– RMI allows a Java program on one machine to invoke a method
on a remote object.
– What does “OO” buy RMI over RPC?
Marshalling Parameters
RPC (procedure-based) vs. RMI (objectbased)
• What are the differences between RPC and RMI?
– RMI can pass of (remote) objects as parameters to remote
methods
– RMI can invoke remote methods on these (remote) objects
– RPC cannot do both
Summary
• Process overview
– Process lifecycle, process state, process control block, process vs.
thread
• Process scheduling
– Long-term vs. short-term schedulers, ready vs. I/O queues,
context switching
• Interprocess communication
– Shared memory vs. message passing
• Client-server communication
– Socket, RPC vs. RMI
41
End of Chapter 3