Transcript bound process

CHAPTER 4: PROCESSES
Process concept
 Process scheduling
 Process operations
 Process cooperating
 Inter-process communication
 Communication in client-server systems

PROCESS CONCEPT




An operating system executes a variety of programs:
 Batch system – jobs
 Time-shared systems – system/user programs or tasks.
 Processes (The current popular term).
Process – a program in execution.
 Relationship between process and program.
Two or more processes may be associated with the same
program. A process can spawn new processes.
A process includes:
 program code
 program counter value and processor register contents
 stack section and data section
Process concept: States
Two state model
 Five state model
 Six state model
 Seven State model
 Other models

Process concept: Two state model
Process concept: Five state model
Process concept: Five state model
Process concept: Five state model
Process concept: Six state model
Process concept: Seven state model
Process concept: PCB
PCB: Information associated with each process.
 Process state,
 Program counter,
 CPU registers (This info must be saved in order to
allow the process to be continued correctly afterward,
See the following Fig),
 CPU scheduling information,
 Memory-management information,
 I/O status information,
 Accounting information,
 For Linux: /usr/src/linux-2.4/include/linux/sched.h
Process concept: PCB
Process concept: PCB
PROCESS SCHEDULING


The Queues in the OS
 Job queue,
 Read queue: set of all processes ready for execution.
(Swapped out or in main memory),
 Device queue: A set of processes waiting for an I/O
device. Each device has its own device queue.
A process migrates among the various queues throughout
its life time.
Process scheduling:
Ready Queue Various I/O Device Queues
Process scheduling: Representation
Process scheduling: Schedulers




The lifetime of a process
 Job pool  memory pool  CPU pool
Long-term scheduler (or job scheduler) (长程调度)–
selects which processes should be brought into the
system.
Medium-term scheduler (中程调度) – selects which
swapped out process should be swapping into
memory.
Short-term scheduler (or CPU scheduler) (短程调
度)– selects which process should be executed next
and allocates CPU.
Process scheduling: Schedulers



Short-term scheduler is invoked very frequently
(milliseconds) must be fast.
Medium-term scheduler is invoked infrequently fast.
Long-term scheduler is invoked very infrequently (seconds,
minutes)  may be slow.
 The long-term scheduler controls the degree of
multiprogramming.
 The long-term scheduler should select a good process
mix of I/O-bound and CPU-bound processes.
 I/O-bound process (I/O约束进程) – spends more
time doing I/O than computations, many short CPU
bursts.
 CPU-bound process （CPU约束进程）– spends
more time doing computations; few very long CPU
bursts.
Process scheduling: Context switch




When CPU switches to another process, the system
must save the context of the old process and load the
saved context for the new process.
 The context of a process is represented in the PCB
of a process.
 To freeze it; to preserve it; to thaw it.
Context-switch time is overhead; the system does no
useful work while switching.
Context-switch time is mainly dependent on hardware
support.
OS programmer try new structures to reduce contextswitch time whenever possible.
PROCESS OPERATION




Process creation
Process execution
 Get/set process attributes
 Wait for time/event/
 Signal events
 Allocate/free memory
Process termination
Process communication
 Shard-memory (Threads belonging to single
process)
 IPC on the same computer
 C/S on the distributed systems.
Process operation: Process creation
Parent process create children processes, which, in turn
create other processes, forming a tree of processes.
Process operation: Process creation



In general, a process will need certain resources to
accomplish its task.
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.
Process operation: Process creation



Address space
 The child process is a duplicate of the parent process.
 The child has a program loaded into it.
The DEC VMS example
 Creating a new process and loading a specified
program into that process and starting it running.
The UNIX example
 fork system call creates new process
 exec system call used after a fork to replace the
process’ memory space with a new program.
Process operation: Process termination


Process executes last statement and asks the operating
system to decide it (exit).
 Output data from child to parent (via wait).
 Process’ resources are de-allocated.
Parent may terminate execution of children processes
(abort).
 Child has exceeded allocated resources.
 Task assigned to child is no longer required.
 Parent is exiting.
 Operating system does not allow child to continue
if its parent terminates.
 Cascading termination.
PROCESS COOPERATING

Independent processes vs cooperating processes



Why process cooperation?





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
Information sharing
Computation speed-up
Modularity (system)
Convenience (user)
Mechanisms for process cooperation


Communication and
synchronization
Process cooperating:
The Producer-consumer problem


The producer-consumer problem: a producer process
produces information that is consumed by a consumer
process.
 Print program  print driver,
 Compiler  assembler  loader.
Communication choices:
 IPC (Interprocess-communication),
 Shared memory.
SHARED MEMORY COMMUNICATION

A buffer pool: filled by the producer and consumed
by the consumer.
 unbounded-buffer places no practical limit on the
size of the buffer,
 bounded-buffer assumes that there is a fixed buffer
size.
Shared memory:
Bounded-Buffer – Shared-Memory Solution

Shared data
#define BUFFER_SIZE 10
typedef struct
{
. . .
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
Shared memory:
Bounded-Buffer – Shared-Memory Solution

Producer process
item nextProduced;
while (1)
{
while(((in + 1)%BUFFER_SIZE) == out)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
}
Shared memory:
Bounded-Buffer – Shared-Memory Solution

Consumer Process
item nextConsumed;
while (1) {
while (in == out)
; /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
}
INTER-PROCESS COMMUNICATION (IPC)



IPC v.s. Shared-memory
 Efficiency,
 Centralized vs Distributed.
Two IPC operations
 send
 receive
IPC issues
 Naming: direct or indirect communication
 Symmetric or asymmetric communication
 Automatic or explicit buffering
 Send by copy or send by reference
 Fixed-sized or variable-sized messages
Inter-Process Communication (IPC)

Implementation issues
 How to refer to each other:
 Direct communication
 Indirect communication
 How to synchronize each other
 Blocking
 Nonblocking
 How to handle messages in the link.
IPC: Naming

Direct communication
 Processes must name each other explicitly:
 send (P, message) – send to process P
 receive(Q, message) – receive from process Q
 Properties of direct 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.
 Asymmetry in addressing


Send (P, message)
Receive (id, message): the variable id is set to the name of
the process with which communication has taken place.
IPC: Naming

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.
 Two primitives
 send(A, message) – send a message to mailbox A
 receive(A, message) – receive a message from
mailbox
IPC: Naming

How about three processes?
 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. The sender is notified who the
receiver was.
IPC: Naming

Properties of indirect 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.
 Mailbox can be owned by a process or OS.
 create a new mailbox
 send and receive messages through mailbox
 destroy a mailbox
IPC: Synchronization



Blocking and Nonblocking
 Blocking send
 Nonblocking send
 Blocking receive
 Nonblocking receive
Blocking send and blocking receive  rendezvous.
Nonblocking send and blocking receive  the most
common one.
IPC: Buffering

Queue of messages attached to the link; implemented
in one of three ways.
 Zero capacity – 0 messages
Sender must wait for receiver (rendezvous).
 Bounded capacity – finite length of n messages
Sender must wait if link full.
 Unbounded capacity – infinite length
Sender never waits.
IPC: An example: Mach



Each task has two special mailboxes: the Kernel
mailbox and the Notify mailbox.
Message transferring
 msg_send, msg_receive, msg_rpc.
Mailbox creation
 port_allocate.
IPC: An example: Windows 2K



LPC: local procedure call facility
Two types of ports: connection ports and
communication ports.
Message-passing techniques
 For small messages, to use the port’s message
queue as intermediate storage and copies the
message from one process to other
 For a large message, to pass the message through a
section object (or shared memory)
…
CLIENT-SERVER
COMMUNICATION
Sockets
 Remote Procedure Calls
 Remote Method Invocation (Java)

C/S: 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.

C/S: Socket Communication
C/S: Java Socket Programming

Writing C/S Application using Java Sockets
 KnockKnockProtocol
Server: "Knock knock!"
Client: "Who's there?"
Server: "Dexter."
Client: "Dexter who?"
Server: "Dexter halls with boughs of holly."
Client: "Groan."
KnockKnockClient
 KnockKnockServer

C/S: Remote Procedure Calls





Remote procedure call (RPC) abstracts procedure
calls between processes on networked systems.
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.
XDR (External data representation).
C/S: Execution of RPC
C/S: Remote Method Invocation
Remote Method Invocation (RMI) is a Java
mechanism similar to RPCs.
 RMI allows a Java program on one machine
to invoke a method on a remote object.

C/S: Marshalling Parameters
Exercises

Exercises
 4.2
 4.4
 4.5
 4.8*