Transcript CS307-slides03

CS307 Operating Systems
Processes
Fan Wu
Department of Computer Science and Engineering
Shanghai Jiao Tong University
Spring 2013
Process Concept
 An operating system executes a variety of programs:
Batch system – jobs
 Time-shared systems – user programs or tasks
 All these activities are processes

 Process – a program in execution
 Textbook uses the terms job and process almost interchangeably
Operating Systems
2
The Process
 Multiple parts

The program code, also called text
section

Current activity including program
counter, processor registers

Stack containing temporary data

Function parameters, return
addresses, local variables

Data section containing global
variables

Heap containing memory dynamically
allocated during run time
Operating Systems
3
The Process (Cont.)
 What is the difference between program and process?

Program is passive entity, process is active

Program becomes process when executable file loaded into memory
 Execution of program started via GUI mouse clicks, command line entry of
its name, etc
 One program can be several processes

Consider multiple users executing the same program
Operating Systems
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

ready: The process is waiting to be assigned to a processor

terminated: The process has finished execution
Operating Systems
5
Process Control Block (PCB)
Information associated with each process
 Process state
 Process number
 Program counter
 CPU registers
 CPU scheduling information
 Memory-management information
 Accounting information
 I/O status information
Operating Systems
6
Process Representation in Linux
 Represented by the C structure task_struct
pid t pid; /* process identifier */
long state; /* state of the process */
unsigned int time slice /* scheduling information */
struct task struct *parent; /* this process’s parent */
struct list head children; /* this process’s children */
struct files struct *files; /* list of open files */
struct mm struct *mm; /* address space of this pro */
Operating Systems
7
CPU Switch From Process to Process
Operating Systems
8
Process Scheduling
 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
Operating Systems
9
Ready Queue And Various I/O Device Queues
Operating Systems
10
Representation of Process Scheduling
Operating Systems
11
Schedulers
 Long-term scheduler (or job scheduler) – selects which
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
Operating Systems
12
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
Operating Systems
13
Operations on Processes
 Process Creation
 Process Termination
Operating Systems
15
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)
Operating Systems
16
Process Creation (Cont.)
 Resource sharing

Parent and children share all resources

Children share subset of parent’s resources

Parent and child share no resources
 Initialization data
 Execution

Parent and children execute concurrently

Parent waits until children terminate
 Address space

Child duplicate of parent

Child has a program loaded into it
Operating Systems
17
C Program Forking Separate Process
 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
Operating Systems
18
#include <sys/types.h>
#include <studio.h>
#include <unistd.h>
int main()
{
int i = 1;
pid_t pid;
/* fork another process */
pid = fork();
if (pid < 0) { /* error occurred */
fprintf(stderr, "Fork Failed");
return 1;
}
else if (pid == 0) { /* child process */
printf(“This
is child.");
execlp("/bin/ls",
"ls", NULL);
}
else { /* parent process */
/* parent will wait for the child */
wait (NULL);
printf ("Child Complete.");
}
return 0;
}
Process Execution
Operating Systems
19
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 systems do not allow child to continue if its
parent terminates
–
Operating Systems
All children terminated - cascading termination
20
Interprocess Communication
 Processes within a system may be independent or cooperating
 Cooperating process can affect or be affected by other processes, 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
Operating Systems
21
Communications Models
Message Passing
Operating Systems
Shared Memory
22
Interprocess Communication – Shared Memory
 A region of memory that is shared by cooperating processes is established.
 Processes can then exchange information by reading and writing data to the
shared region.
Operating Systems
23
Producer-Consumer Problem
 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
Producer
Buffer
Consumer
Operating Systems
24
Bounded-Buffer – Shared-Memory Solution
 Shared data
#define BUFFER_SIZE 10
typedef struct {
...
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
Operating Systems
25
Bounded-Buffer – Shared-Memory Solution
Producer
while (true) {
/* Produce an item */
while (((in + 1) % BUFFER_SIZE) == out)
; /* do nothing -- no free buffers */
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
}
Consumer
while (true) {
while (in == out)
; // do nothing
// remove an item from the buffer
item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
return item;
}
Operating Systems
26
Bounded-Buffer – Shared-Memory Solution
 Weakness:

Busy waiting

The solution allows only BUFFER_SIZE-1 elements at the same time
 Popquiz:

Rewrite the previous processes to allow BUFFER_SIZE items in the
buffer at the same time
Operating Systems
27
Ordinary Pipes
 Ordinary Pipes allow communication in standard producer-
consumer style

Producer writes to one end (the write-end of the pipe)

Consumer reads from the other end (the read-end of the pipe)
 Ordinary pipes are in fact unidirectional
 Require parent-child relationship between communicating processes
Operating Systems
29
Ordinary Pipe
Output
WRITE
Pipe
Process A
Operating Systems
READ
Input
Process B
30
Using Pipe – Part 1
 First, create a pipe and check for errors
int mypipe[2];
mypipe[0]
mypipe[1]
if (pipe(mypipe)) {
fprintf (stderr, "Pipe failed.\n");
return -1;
}
 Second, fork your threads
 Third, close the pipes you don't need in that thread

reader should close(mypipe[1]);

writer should close(mypipe[0]);
Operating Systems
31
read-end
write-end
Using Pipe – Part 2
 Fourth, the writer should write the data to the pipe

write(mypipe[1],&c,1);
 Fifth, the reader reads from the data from the pipe:

while (read(mypipe[0],&c,1)>0) {
//do something, loop will exit when WRITER closes pipe
}
 Sixth, when writer is done with the pipe, close it

close(mypipe[1]); //EOF is sent to reader
 Fifth, when reader receives EOF from closed pipe, close the pipe and exit
your polling loop

close(mypipe[0]); //all pipes should be closed now
Operating Systems
32
Interprocess Communication – Message Passing
 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)

 If P and Q wish to communicate, they need to:

establish a communication link between them
 exchange messages via send/receive
Operating Systems
33
Direct Communication
 Processes must name each other explicitly:

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; The processes need to know
only each other’s identity to communicate

A link is associated with exactly one pair of communicating
processes

Between each pair there exists exactly one link
Operating Systems
34
Indirect Communication
 Messages are directed to and received from mailboxes (also referred
to as ports)

Each mailbox has a unique id

Processes can communicate only if they share a mailbox
 Primitives are defined as:
send(A, message) – send a message to mailbox A
receive(A, message) – receive a message from mailbox A
 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
Operating Systems
35
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
Operating Systems
38
Socket Communication
Operating Systems
39
Steps to Create Server Side
1.
2.
3.
4.
5.
6.
Create a socket with the
socket() system call
Bind the socket to an
address using the bind()
system call.
Listen for connections with
the listen() system call
Accept a connection with
the accept() system call
(This call typically blocks
until a client connects with
the server)
Send and receive data with
read() and write() system
calls
Close connection with close()
system call
Operating Systems
40
socket()
bind()
listen()
accept()
read()/write()
close()
Steps to Create Client Side
1.
Create a socket with the
socket() system call
socket()
2.
3.
4.
Connect the socket to the
address of the server using
the connect() system call
Send and receive data with
read() and write() system
calls.
Close the socket with close()
system call
Operating Systems
41
connect()
read()/write()
close()
Interaction Between Client and Server
socket()
socket()
bind()
listen()
accept()
connect()
read()/write()
read()/write()
close()
close()
Server
Client
Operating Systems
42
Internet Domain Socket
 IP address:
 32 bits (IPv4) or 128 bits (IPv6)
 C/S work on same host: just use localhost
 Port
 16 bit unsigned integer
 Lower numbers are reserved for standard services
 Transport layer protocol: TCP / UDP
Operating Systems
43
Headers
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <sstream>
 #include <unistd.h>
 #include <sys/types.h>

Definitions of a number of data types used in system calls
 #include <sys/socket.h>

Definitions of structures needed for sockets
 #include <netinet/in.h>

Constants and structures needed for internet domain addresses
Operating Systems
44
Creating Socket
int sockfd
sockfd = socket(AF_INET, SOCK_STREAM, 0);
if (sockfd < 0) {
perror(“ERROR opening socket”);
exit(2);
}
 AF_INET: address domain
 SOCK_STREAM: stream socket, characters are read in
a continuous stream as if from a file or pipe
 0: protocol. The operating system chooses the most
appropriate protocol. It will choose TCP for stream
sockets.
Operating Systems
45
Binding Socket
struct sockaddr_in serv_addr;
serv_addr.sin_family = AF_INET;
serv_addr.sin_addr.s_addr = htonl(INADDR_ANY);
serv_addr.sin_port = htons(BASIC_SERVER_PORT);
bind(sockfd, (sockaddr*) &serv_addr, sizeof(serv_addr));
//error check
 INADDR_ANY: get IP address of the host automatically
 htonl, htons: data format conversion
 bind(): binds a socket to an address
Operating Systems
46
Listening and Accepting Connection
listen(sockfd, 5);
 listen(): allows the server to listen on the socket for
connections, with a backlog queue of size 5.
int client_sockfd;
struct sockaddr_in client_addr;
int len = sizeof(client_addr);
client_sockfd = accept(sockfd, (sockaddr *) &client_addr,
&len);
//error check
 accept(): block process until a client connects to the
server. It returns a new socket file descriptor, if the
connection is created.
Operating Systems
47
Reading and Writing
char buf[1024];
int nread = read(client_sockfd, buf, 1024);
read(): reads from the socket
write(client_sockfd, buf, len);
write(): writes to the socket
close(client_sockfd);
close(): closes the socket
Operating Systems
48
Connecting A Client to A Server
int sockfd;
sockfd = socket(AF_INET, SOCK_STREAM, 0);
// error check
struct sockaddr_in serv_addr;
struct hostent *host;
serv_addr.sin_family = AF_INET;
host = gethostbyname(argv[1]);
// error check
memcpy(&serv_addr.sin_addr.s_addr, host->h_addr,
host->h_length);
serv_addr.sin_port = htons(BASIC_SERVER_PORT);
connect(sockfd, (sockaddr *) &serv_addr, sizeof(serv_addr))
// error check
Operating Systems
49
Homework
 Reading

Chapter 3
Operating Systems
50