Site hosted by Angelfire.com: Build your free website today!

Department of Computer Science, UMass Amherst Andrew H. Fagg

Announcements/Reminders

_ Homework 1 is available on the website and is due in 8 days.

_ Lab 1 is also available & is due in 11 days.

CMPSCI 377: Operating Systems Lecture 4, Page 1

Department of Computer Science, UMass Amherst Andrew H. Fagg

The Big Picture So Far

From the Architecture to the OS to the User: Architectural resources,

OS management, and User Abstractions.

Hardware

Abstraction

Example OS Services User Abstraction

Processor Process management,

Scheduling, Traps Protection,

Billing, Synchronization

Process

Memory Management, Protection,

Virtual memory

Address space

I/O devices Concurrency with CPU,

Interrupt handling

Terminal, Mouse, Printer,

System Calls

File system Management, Persistence Files

Distributed

systems

Network security, Distributed

_le system

RPC system calls, _le

sharing

CMPSCI 377: Operating Systems Lecture 4, Page 2

Department of Computer Science, UMass Amherst Andrew H. Fagg

Today: Process Management

_ A process as the unit of execution.

_ How are processes represented in the OS?

_ What are possible execution states and how does the system move from

one state to another?

_ How do processes communicate? Is this e_cient?

CMPSCI 377: Operating Systems Lecture 4, Page 3

Department of Computer Science, UMass Amherst Andrew H. Fagg

What's in a Process?

_ Process: dynamic execution context of an executing program

_ Several processes may run the same program, but each is a distinct entity

with its own state (e.g., MS Word).

_ In its simplest form, a process executes sequentially, one instruction at a

time

CMPSCI 377: Operating Systems Lecture 4, Page 4

Department of Computer Science, UMass Amherst Andrew H. Fagg

What's in a Process?

Process state consists of at least:

_ the code for the running program,

_ the static data for the running program,

_ space for dynamic data (the heap), the heap pointer (HP),

_ the Program Counter (PC), indicating the next instruction,

_ an execution stack with the program's call chain (the stack), the stack

pointer (SP),

_ values of CPU registers,

_ a set of OS resources in use (e.g., open _les), and

_ process execution state (ready, running, etc.).

CMPSCI 377: Operating Systems Lecture 4, Page 5

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example Process State in Memory

What you wrote:

void X ( int b ) f

PC! if (b == 1) : : :

g

main() f

int a = 2;

X ( a );

g

What's in Memory:

Process State

X; b = 2

void main() {

X ( a );

int a = 2

}

}

void X ( int b ) {

main; a= 2

HP

PC

SP

if (b==1)...

static data segment

heap

stack

text segment

CMPSCI 377: Operating Systems Lecture 4, Page 6

Department of Computer Science, UMass Amherst Andrew H. Fagg

Process Execution State

_ Execution state of a process indicates what it is doing

new: the OS is setting up the process state

running: executing instructions on the CPU

ready: ready to run, but waiting for the CPU

waiting: waiting for an event to happen (e.g., I/O completion)

terminated: the OS is destroying this process

_ As the program executes, it moves from state to state, as a result of the

program actions (e.g., system calls), OS actions (scheduling), and

external actions (interrupts).

New Running Terminated

Waiting

Ready

CMPSCI 377: Operating Systems Lecture 4, Page 7

Department of Computer Science, UMass Amherst Andrew H. Fagg

Process Execution State

New Running Terminated

Waiting

Ready

Example:

void main() {

printf(`Hello World\n');

}

state sequence

new

ready

running

waiting for I/O

ready

running

terminated

_ The OS manages multiple active process using state queues

(More on this in a minute : : :)

CMPSCI 377: Operating Systems Lecture 4, Page 8

Department of Computer Science, UMass Amherst Andrew H. Fagg

Process Data Structures

Process Control Block (PCB): OS data structure to keep track of all

processes

_ The PCB tracks the execution state and location of each process

_ The OS allocates a new PCB on the creation of each process and places

it on a state queue

_ The OS deallocates the PCB when the process terminates

CMPSCI 377: Operating Systems Lecture 4, Page 9

Department of Computer Science, UMass Amherst Andrew H. Fagg

Process Control Block Contains:

_ Process state (running, waiting, etc.)

_ Process number

_ Program Counter

_ Stack Pointer

_ General Purpose Registers

_ Memory Management Information

_ Username of owner

_ List of open _les

_ Queue pointers for state queues

_ Scheduling information (e.g., priority)

_ I/O status (e.g., open sockets)

_ : : :

CMPSCI 377: Operating Systems Lecture 4, Page 10

Department of Computer Science, UMass Amherst Andrew H. Fagg

Process State Queues

_ The OS maintains the PCBs of all the processes in state queues.

_ The OS generally places the PCBs of all the processes belonging to the

same execution state into the same queue.

_ When the OS changes the state of a process, the PCB is unlinked from

its current queue and moved to its new state queue.

_ The OS can use di_erent policies to manage each queue (e.g., in QNX,

there are di_erent queues for timesliced and for prioritized processes).

_ Each I/O device has its own wait queue.

CMPSCI 377: Operating Systems Lecture 4, Page 11

Department of Computer Science, UMass Amherst Andrew H. Fagg

State Queues: Example

PCB H

head ptr

tail ptr

PCB K Wait Queue

PCB X PCB L PCB A

head ptr

tail ptr

Ready Queue

CMPSCI 377: Operating Systems Lecture 4, Page 12

Department of Computer Science, UMass Amherst Andrew H. Fagg

PCBs and Hardware State

_ Starting and stopping processes is called a context switch, and is a

relatively expensive operation.

_ The OS starts executing a ready process by loading hardware registers

(PC, SP, etc) from its PCB

_ While a process is running, the CPU modi_es the Program Counter (PC),

Stack Pointer (SP), registers, etc.

_ When the OS stops a process, it saves the current values of the registers,

(PC, SP, etc.) into its PCB

CMPSCI 377: Operating Systems Lecture 4, Page 13

Department of Computer Science, UMass Amherst Andrew H. Fagg

PCBs and Hardware State (cont)

This process of switching the CPU from one process to another (stopping

one and starting the next) is the context switch.

_ Time sharing systems may do 100 to 1000 context switches a second.

_ The cost of a context switch and the time between switches are closely

related

CMPSCI 377: Operating Systems Lecture 4, Page 14

Department of Computer Science, UMass Amherst Andrew H. Fagg

Creating a Process

One process can create other processes to do work.

_ The creator is called the parent and the new process is the child.

_ The parent de_nes (or donates) resources and privileges to its children.

_ A parent can either wait for the child to complete, or continue in parallel.

CMPSCI 377: Operating Systems Lecture 4, Page 15

Department of Computer Science, UMass Amherst Andrew H. Fagg

Creating a Process in Unix

In Unix, the fork() system call is used to create child processes

_ Fork copies variables and registers from the parent to the child.

_ The only di_erence between the child and the parent is the value returned

by fork.

{ In the parent process, fork returns the process id of the child.

{ In the child process, the return value is 0.

_ The parent can wait for the child to terminate by executing the wait()

system call or continue execution.

_ The child often starts a new and di_erent program within itself, via a call

to the exec() system call.

CMPSCI 377: Operating Systems Lecture 4, Page 16

Department of Computer Science, UMass Amherst Andrew H. Fagg

Creating a Process: Example

_ When you log in to a machine running Unix, you create a shell process.

_ Every command you type into the shell is executed by a child of your shell

process and is an implicit fork and exec pair.

_ For example, you type emacs, the OS \forks" a new process and then

\exec" (executes) emacs.

_ If you type an \&" after the command, Unix will run the process in

parallel with your shell, otherwise, your next shell command must wait

until the _rst one completes.

CMPSCI 377: Operating Systems Lecture 4, Page 17

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example Unix Program: Fork

main() {

int parentID = getpid(); /* ID of this process */

char prgname[1024];

gets(prgname); /* read the name of program we want to start */

int cid = fork();

if(cid == 0) { /* I'm the child process */

execlp( prgname, prgname, 0); /* Load the program */

/* If the program named prgname can be started, we never get

to this line, because the child program is replaced by prgname */

printf("I didn't find program %s\n", prgname);

} else { /* I'm the parent process */

sleep (1); /* Give my child time to start. */

waitpid(cid, 0, 0); /* Wait for my child to terminate. */

printf("Program %s finished\n", prgname);

} }

CMPSCI 377: Operating Systems Lecture 4, Page 18

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example Unix Program: Explanation

fork() forks a new child process that is a copy of the parent.

execlp() replaces the program of the current process with the named

program.

sleep() suspends execution for at least the speci_ed time.

waitpid() waits for the named process to _nish execution.

gets() reads a line from standard input (stdin).

CMPSCI 377: Operating Systems Lecture 4, Page 19

Department of Computer Science, UMass Amherst Andrew H. Fagg

What is happening on the Fork

cid = fork()

...

...

main

cid = fork()

...

...

main

at the time of the fork.

on the fork

copy everything

except result

of fork

difference between

the parent and the child

Note this is the only

HP heap

PC

stack

SP

static data

text

HP heap

PC

stack

SP

static data

text

parentID = 334

cid = 542

main

parentID = 334

cid = 0

main

Parent Child

CMPSCI 377: Operating Systems Lecture 4, Page 20

Department of Computer Science, UMass Amherst Andrew H. Fagg

Process Termination

_ On process termination, the OS reclaims all resources assigned to the

process.

_ In Unix:

{ a process can terminate itself using the exit() system call.

{ a process can terminate a child using the kill() system call.

{ The kill() system call allows one process to cause another process to

trap (we also call this generating a signal).

{ There are many types of signals: KILL, HUP (hangup), USR (user

de_ned), ILL (Illegal instruction) ...

CMPSCI 377: Operating Systems Lecture 4, Page 21

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example Unix Program: Process Termination

main() {

int parentID = getpid(); /* ID of this process */

int cid = fork();

if(cid == 0) { /* I'm the child process */

sleep (5); /* I'll exit myself after 5 seconds. */

printf ( "Quitting child\n" );

exit (0);

printf ( "Error! After exit call.!"); /* should never get here */

} else { /* I'm the parent process */

printf ( "Type any character to kill the child.\n" );

char answer[10];

gets (answer);

if ( !kill(cid, SIGKILL) ) {

printf("Killed the child.\n");

} } }

CMPSCI 377: Operating Systems Lecture 4, Page 22

Department of Computer Science, UMass Amherst Andrew H. Fagg

Cooperating Processes

_ Any two process are either independent or cooperating.

_ Cooperating processes work with each other to accomplish a single task.

_ Cooperating processes can:

{ improve performance by overlapping activities or performing work in

parallel,

{ enable an application to achieve a better program structure as a set of

cooperating processes, where each is smaller than a single monolithic

program, and

{ easily share information between tasks.

) Distributed and parallel processing is the wave of the future. To program

these machines, we must cooperate and coordinate between separate

processes.

CMPSCI 377: Operating Systems Lecture 4, Page 23

Department of Computer Science, UMass Amherst Andrew H. Fagg

Producers and Consumers: The Concept

Producer

Process

Consumer

Process

Buffer

_ \Producer" generates units of data and places them into the bu_er.

_ \Consumer" picks up units of data from the bu_er and uses it.

_ Communication is asynchronous: each process can do things on its own

time scale ... within limits. What are these limits?

_ Communication can be implemented using message passing or shared

memory

CMPSCI 377: Operating Systems Lecture 4, Page 24

Department of Computer Science, UMass Amherst Andrew H. Fagg

Producers and Consumers: Shared Memory

Producer

Process

Consumer

Process

___

___

___

___

___

___

___

___

___

___

___

___

___ ____

____

____

____

____

____

____

____

____

____

____

____

____ ___

___

___

___

___

___

___

0 n-1

Buffer

out

in

_ \in" and \out" are indices into a _xed-size bu_er (length n).

CMPSCI 377: Operating Systems Lecture 4, Page 25

Department of Computer Science, UMass Amherst Andrew H. Fagg

Producers and Consumers: Shared Memory

n = 100; // max outstanding items

in = 0;

out = 0;

producer

repeat forever f

: : :

nextp = produced item

: : :

// Make sure bu_er not full

while in+1 mod n = out do

no-op

bu_er[in] = nextp

in = in+1 mod n

g

consumer

repeat forever f

// Make sure bu_er not empty

while in = out do no-op

nextc = bu_er[out]

out = out+1 mod n

: : :

consume nextc

: : :

g

_ We will need some way of declaring that \bu_er", \in" and \out" are all

available to both the consumer and producer processes (e.g., this can be

done in C/unix using the mmap() function).

CMPSCI 377: Operating Systems Lecture 4, Page 26

Department of Computer Science, UMass Amherst Andrew H. Fagg

Communication using Message Passing

main()

: : :

if (fork() != 0) producerSR();

else consumerSR();

end

producerSR

repeat

: : :

produce item nextp

: : :

send (nextp, consumer)

consumerSR

repeat

receive (nextc, producer)

: : :

consume item nextc

: : :

CMPSCI 377: Operating Systems Lecture 4, Page 27

Department of Computer Science, UMass Amherst Andrew H. Fagg

Message Passing

_ Distributed systems typically communicate using message passing

_ Each process needs to be able to name the other process.

_ The consumer is assumed to have an in_nite bu_er size.

_ A bounded bu_er would require the tests in the previous slide, and

communication of the \in" and \out" variables (in from producer to

consumer, out from consumer to producer).

_ OS keeps track of messages (copies them, noti_es receiving process, etc.).

) How would you use message passing to implement a single producer and

multiple consumers?

CMPSCI 377: Operating Systems Lecture 4, Page 28

Department of Computer Science, UMass Amherst Andrew H. Fagg

Process Management: Summary

_ A process is the unit of execution.

_ Processes are represented as Process Control Blocks in the OS

{ PCBs contain process state, scheduling and memory management

information, etc.

_ A process is either New, Ready, Waiting, Running, or Terminated.

_ On a uniprocessor, there is at most one running process at a time.

_ The program currently executing on the CPU is changed by performing a

context switch.

_ Processes communicate either with message passing or shared memory

CMPSCI 377: Operating Systems Lecture 4, Page 29

Department of Computer Science, UMass Amherst Andrew H. Fagg

Next Time

_ Wednesday: Threads (Chapter 5)

CMPSCI 377: Operating Systems Lecture 4, Page 30