Transcript pptx

CMPT 300
Introduction to Operating
Systems
Operating Systems
Processes
© Janice Regan, CMPT 300, May 2007
0
Multiprogramming
 When multiple programs share the same
processor
 An example of pseudoparallelism
 Processes share processor (each get a short
turn) so that in a perceptible length of time it
appears processes run in parallel
 True parallelism happens when multiple
processors are running processes at the
same time
© Janice Regan, CMPT 300, May 2007-2016
1
What is a process?
 A process (active entity) is a program (static
entity) in execution, and includes

An address space, an area in memory (memory
location x to y) containing



List of instructions
Any required data
The stack for the program
Registers (program counter … )
 Other information (includes resources used, I/O status)
 Multiple processes may execute different instances of the
same program (even at the same time)

© Janice Regan, CMPT 300, May 2007-2016
2
Process context
 The context of a process must be
preserved, It includes
 The values of the registers (e.g. Program counter)
 Any other information necessary to restore
the process after it has been saved.
 Saving and restoring the context of a
process, is called context switching
 When context switching the scheduler may
be used to determine which process to
restore
© Janice Regan, CMPT 300, May 2007-2016
3
Why should an OS use processes
 A computer application accepts input, processes it and
returns output


Every application must use the computer hardware to execute
(CPU, I/0 devices …)
It is inefficient to rewrite the low level code to interact with the
hardware within each application: Let the OS deal with this and
use the OS
 We wish to run multiple applications “at the same time”
to efficiently use our computer (multiprogramming)



Each application will run as one or more processes
The data, I/0 use, and other resource use of one process must
be protected from the other applications
The OS provides the support for sharing between processes
© Janice Regan, CMPT 300, May 2007-2016
4
The process model
 Multiprogramming (running multiple processes in
“parallel”) is based on a process model
 When a program is used a process is created that
places that program in memory, and identifies and labels
the details about that process needed for that program
to run
 Once the process is started it will share the resources
with other active processes
 Because the process is sharing resources


there is no way to accurately predict when a particular part of
the program will be completed. Our processes cannot make
assumptions about absolute timing.
There must be protections so that a process cannot access data
belonging to or resources being used by another process.
© Janice Regan, CMPT 300, May 2007-2016
5
Process Control Block
 A system runs an O/S to manage how resources are
shared between processes




O/S must provide a consistent and secure interface for the
processes to interact with
At any point in time when a process exists the process can be
uniquely described by a number of elements (see next slide for
a partial list)
The Process control block is a data structure built to hold the
values of these elements for a given process
The Process control block, along with an image of the process’s
address space (core image), completely describes the process
 An O/S manages processes using a process table that
may be a list of pointers to these Process Control blocks
for each process, or even a linked list of process control
blocks
© Janice Regan, CMPT 300, May 2007-2016
6
Process Control Block: Contents
 At any point in time when a process is executing the
process can be uniquely described by a number of
elements including







Program counter, context data (register values), memory
pointers (where in data or instructions for the program?)
State (running, ready, blocked, suspended)
Process Identifier (pid)
Other status information (I/0 and other resource usage)
Priority, Scheduling parameters
Accounting information
Parent and child processes related to the process
 These elements are part of the Process control block, a
data structure built for each process
© Janice Regan, CMPT 300, May 2007-2016
7
Using the process control block
 Consider a running process that has just been
interrupted

The process control block is updated to include the
present values of all members
 The state of the process is changed from running to
ready (or another state)
 The ISR executes and on return the operating
system chooses the next process to run
 The OS loads the information in the process control
block of the process about to run into the CPU
© Janice Regan, CMPT 300, May 2007-2016
8
Process Creation
 Processes can be created by the OS or by a user





OS will create a process to execute the program waiting in the
queue or just submitted (if nothing in queue) in a batch system
OS will create processes (at boot time and after boot time) that
run in the background and administer resources such as
printers (print queue …)
Logon of a new interactive user (OS creates new shell)
Opening of a new window by an interactive user (OS)
User or OS creates a new process from an existing process

A parent process spawns a child process

A file transfer server spawns a copy of itself to service
the transfer a a particular file

A process spawns another process to watch for real time
input from hardware
© Janice Regan, CMPT 300, May 2007-2016
9
Spawning
 The system call used to spawn a process is OS
dependent. So are the details of its operation


In Windows use a CreateProcess
In Unix/Linux use fork()
 fork() will create a copy (exact replica) of the
parent process (a child process) and begin the
execution of that child process

The child will have an independent copy of the
address space (code and data)
 any subsequent changes in values in the address
space are unique to the process (parent or child) that
made the changes.
© Janice Regan, CMPT 300, May 2007-2016
10
Spawning a process (windows)
 Use the CreateProcess system call
 Has many (~10 arguments)
 Must specify what program new process will
run
 Creates new process
© Janice Regan, CMPT 300, May 2007-2016
11
Spawning a process (linux)
 When fork() makes a new copy of a process the entire
process control block is copied, this means



The child will have the same connections to open files or
network connections (this includes pointers within the files) as
the parent. Both parent and child must close those connections
that are not needed before proceeding.
The program counter is copied, the next instruction to be
executed in the parent will be the first instruction executed in the
child.
fork() returns a integer, the pid (process id). It returns 0 to the
child (does not need to know its own id), and the actual process
id of the new process to the parent.
© Janice Regan, CMPT 300, May 2007-2016
12
Creating a child (Linux/Unix)
 To create a process in UNIX use the fork command
#include <sys/types.h>
#include <unistd.h>
pid_t fork(void)
 fork() creates a copy of the process
 fork() returns the process id of the new child process to
the parent, and a process id of 0 to the new child
process. (-1 to the parent on failure)
© Janice Regan, CMPT 300, May 2007-2016
13
Example, creating a child
listen( listenfd, LISTENQ);
for( ; ; ) {
connfd = accept(listenfd, …);
if ( (pid = fork()) == 0 ) {
close(listenfd);
processit(connfd); /* uses connection to do something */
close( connfd );
exit (0);
}
close (connfd);
}
© Janice Regan, CMPT 300, May 2007-2016
14
Interpretation of Example (1)
 The example is a part of a simple file transfer server.



At the start of the sample code the server is waiting for a client
to contact it and request a file transfer. (listen command is
listening for a request)
When a request is received the for loop is executed. The first
line inside the loop makes a connection to the client requesting
the transfer. Any data written or read on the connection will use
the connection id (connfd) like a file descriptor
Next fork() is called to make copy of the process


both connections (listening for further requests, and connection to
transfer data) are open in both the parent and the child processes.
When fork() returns the memory image of the parent and child are
identical. The process control block will be almost identical,
differing mainly in process number and information about
parents/children
© Janice Regan, CMPT 300, May 2007-2016
15
Interpretation of Example (2)

After fork() returns the value of the variable pid in the
memory space of the parent process is set to the
process ID of the new child process, and to 0 in the
memory space of the child process
 Next the if will take the execution of the program along
different traces for the parent and child processes.
 First consider the parent.



The parent wishes to pass responsibility for transferring the
file to the child, it will not need to use the connection set up
for file transfer.
The parent’s will closing the file transfer connection
(remember this connection is still open in the child)
The parent will then go back to listening for further requests
(will eventually end up back at the first line of our example
code)
© Janice Regan, CMPT 300, May 2007-2016
16
Interpretation of Example (3)

Next consider the child.





The child does not need to continue to listen for additional
requests for connections to the file transfer server, its sole
responsibility is servicing the request it was created to service
The child will close the connection listening for new
connection requests (close(listenfd);)
The child will then service the file transfer request (actually
transfer the file)
The child will then close the connection established for file
transfer (now complete) (close( connfd );
The child will terminate itself since it has now completed
purpose (exit())
© Janice Regan, CMPT 300, May 2007-2016
17
Executing a different program
 The example we looked at continues to execute the
same program in both the parent and the child
processes.
 What if we want to create a process to execute a
completely different program?



Still use fork()
But also use another system call to execve() (or one of five
other specific purpose exec system functions)
The system function execve()


Replaces the memory image (program, data, and stack) by a
completely different program memory image for a new program.
It then starts execution at the beginning of the new program.
© Janice Regan, CMPT 300, May 2007-2016
18
Why execute a new program
 Simple example: consider using a command line




shell
The shell is one process
When you type a command into the shell you
are asking the OS to create a process to run
that command
In this case the new process would be created
using fork as we discussed
The first line executed by the child process after
the fork would be an execve to start the process
we just requested on the command line.
© Janice Regan, CMPT 300, May 2007-2016
19
Wait for the child?
 There are two possibilities
 Allow the parent to continue execution while
the child runs

E. g. file transfer server, parent continues listening for the
next request to transfer a file
 Make the parent wait for the child to complete
before continuing it’s own execution

E. g. interactive shell, shell waits for command typed on the
command line to complete, prints any results, then the
parent is ready for the next command
© Janice Regan, CMPT 300, May 2007-2016
20
How to make the parent wait
 Use waitpid()
 Can tell the parent to wait for a particular
child to complete
 Can tell the parent to wait for any child to
complete
 Can tell if the child process terminated
normally or with a particular error
© Janice Regan, CMPT 300, May 2007-2016
21
Process Termination
 There are several kinds of reasons for a process
to terminate,


Normal completion
Terminated by another process




Fatal Error




By OS if time limit exceeded
By administrator’s shell
By parent
Protection error (accessing prohibited hardware/data)
I/0 error (file not found, …)
Programming error (divide by zero, unitialized data …)
Voluntary exit due to detected error
© Janice Regan, CMPT 300, May 2007-2016
22
Termination
 From within the process
 ExitProcess(status)
Windows
 exit(status) Unix/Linux
 On process terminating another
 kill() killpg() Unix/Linux
 TerminateProcess() Windows
© Janice Regan, CMPT 300, May 2007-2016
23
Process Hierarchy
 In Unix / Linux
 When one process creates another the creating process
is called the parent process, the created process is
called the child process.





A process created by a child process is the child’s child or the
parent’s descendent.
A parent’s parent is the child’s ancestor
The parent and all its children form a process group.
Processes can be put into new process groups or other existing
process groups using setpgid()
All processes in a process groups can be sent a signal (like kill)
by sending to the process group rather than each member
© Janice Regan, CMPT 300, May 2007-2016
24
Unix / Linux Zombie
 When a child process completes (or is terminated)
before the parent process it “dies” but is not removed
from the system
 It remains so the parent process can access information
about the process.



If the parent process calls wait() or waitpid() then the child
process is ‘cleaned up’ and removed from the system
If the parent process does not call wait() or waitpid() the child
process becomes a zombie and continues using a slot in the
process table
If the parent process terminates without calling wait then
children are passed to the init process and ‘waited’ by init
© Janice Regan, CMPT 300, May 2007-2016
25
User and OS processes (1)
 Kernel (OS)
 contains all OS functions
 executes separately from processes
 User processes run in protected mode.
 OS is not considered a process
 Older operating systems
UP1
UP3
UP2
Kernel
© Janice Regan, CMPT 300, May 2007-2016
26
User and OS processes (2)
 System call may be executed by changing to
privileged mode and executing (to remove need
of a context switch)
 Approach used in UNIX
OS
user
Process Switching
© Janice Regan, CMPT 300, May 2007-2016
27
Process State
Initiating
Exiting
Process
terminated
Process
initiated
Ready
Scheduling
Interrupt or
event
Wait event
Timeout
Next process
dispatched
© Janice Regan, CMPT 300, May 2007-2016
Blocked
Running
Process
complete
28
Transitions/States
 Initiating: New Process Control block built
 Initiating to Ready: OS accepts new process, loads
process control block into the process control table,
allocates memory and resources, loads process into
memory
 Ready to Running: OS scheduler chooses process as
next to run and dispatches it to the CPU (loads registers
and state into CPU)
 Running to Ready: OS scheduler has interrupted
because


Allocated time for the process has been used
Higher priority process is about to run (preempting present
process)
© Janice Regan, CMPT 300, May 2007-2016
29
Transitions/States
 Running to Exit: process has terminated (for one




of the reasons discussed )
Running to Blocked: process has requested
action that requires waiting (like I/0)
Blocked to Ready: Interrupt at end of wait has
been received, process that is waiting can now
continue
Blocked to exit: process terminated by another
process
Ready to exit: process terminated by another
process
© Janice Regan, CMPT 300, May 2007-2016
30
Multiprocessing: queues
done
Ready queue
Dispatch next job
in queue
Read queue
Read
complete
Processor
Read wait
Write queue
Write
complete
Write wait
© Janice Regan, CMPT 300, May 2007-2016
31
What if all processes are blocked?
 Each process uses some fraction of available memory.
 Only so many processes will fit into the physical memory
 Our present model will cause a process to move to




blocked state when it must wait. In blocked state it still
occupies its slot in memory
If there is not room to load additional processes into
memory, and all processes are blocked then the CPU
will be idle
THEN WHAT?
Can increase the size of physical memory, but this is a
limited and expensive solution
Add virtual memory and paging to the operating system.
© Janice Regan, CMPT 300, May 2007-2016
32
Virtual Memory
 We will discuss the topic in detail later, for now lets just look




deep enough to understand how it effects our process model
Virtual memory allows us to treat our system as if the memory is
larger than the actual physical memory (main memory).
A portion of our disk memory will be used to image active
processes that are not presently in main memory.
This introduces another possible state, suspended. A suspended
process is not running and its image is not stored in main
memory. Its image is stored on disk.
A suspended process may still be ready to run or waiting for an
interrupt before it can become ready to run. But before it can run
it must also be loaded back into actual physical memory.
 Loading a suspended process into memory may require
that some process in memory be suspended to make room
© Janice Regan, CMPT 300, May 2007-2016
33
Swapping
 A simplified version of virtual memory
 Swapping copies the entire process image to
disk, and restores the entire image
 Virtual memory will copy pieces of the
process (can be all the pieces but usually
isn’t)
 Conceptually easier to understand but not as
efficient
© Janice Regan, CMPT 300, May 2007-2016
34
Suspended process
 Not immediately available for execution (not completely
stored in main memory)
 May or may not be blocked.

Blocked (and suspended) process cannot be executed
immediately (must be loaded into main memory first) even when
the blocking condition is removed
 A process can be suspended (to prevent it execution) by
an agent such as an OS process, its parent process, or
some other process.
 The suspended process cannot be reloaded until the
agent that placed it into a suspended state indicates that
it should be reloaded.
© Janice Regan, CMPT 300, May 2007-2016
35
Process State
Initiating
Insufficient
memory
Exiting
Enough
memory
Process
initiated
Process
complete
activate
Ready
Ready/Suspend
suspend
Interrupt or
event
Interrupt or
event
Scheduling
Next process
dispatched
Running
Wait event
activate
Blocked/Suspend
Timeout
Blocked
suspend
© Janice Regan, CMPT 300, May 2007-2016
Activate = load process into main memory
36
Additional Transitions/States
 Ready/Suspend State: process is in memory on disk but is
ready to be loaded and run
 Blocked/Suspend State: process is in memory on disk and
is awaiting an event before it can be reloaded and run
 Blocked to Blocked/suspend: process is blocked, no
appropriate process is available to run, move process to
virtual memory
 Blocked/suspend to Ready/suspend: Interrupt at end of
wait has been received, process that is waiting can now
continue, process is stored outside main memory (cannot
run before it is restored to main memory)
© Janice Regan, CMPT 300, May 2007-2016
37
Additional Transitions/States
 Ready/Suspend to Ready: load into main memory, may
replace a process with lower priority, or replace any process if
all processes are blocked.
 Ready to Ready/Suspend: ready process being preempted by
higher priority task being moved to Ready from
Ready/Suspend
 Running to Ready/Suspend: If a presently suspended
process is preempting the present process it may be
necessary to move the process directly to Ready/Suspend
rather than to ready
 Blocked/suspend to Blocked: space becomes available in
main memory, the suspended blocked process is higher
priority than the next suspended ready process, and the block
is about to be removed. (not a common transition)
© Janice Regan, CMPT 300, May 2007-2016
38
Example UNIX (systemV)
Initiating
Insufficient
memory
Process
initiated
Return
to user
Enough
memory
return
Swap in
Ready
Ready/Swapped
User/Mode
Running
Schedule
System
interrupt
Swap out
preempt
Wakeup
Wakeup
Running
Kernel mode
Go to sleep
Asleep/Swapped
Asleep
exit
Zombie
suspend
© Janice Regan, CMPT 300, May 2007-2016
Activate = load process into main memory
39