Transcript Slide set 14

operating
systems
Processes
operating
systems
Definitions
A program
is a file that contains an executable module.
Running a program
loading the list of machine level instructions
into memory and having the CPU execute
the instructions one at a time.
Hardware View
operating
systems
Program Counter
Memory
environment variables
stack
stack frame
return address
Registers
parameters
status
copy of registers
heap
At the hardware level, the
computer is pretty dumb. It
simply marches through memory,
executing one instruction after
another. It knows nothing of
programs, processes, or threads.
static data
machine
instructions
local variables
operating
systems
Definitions
A program
is a file that contains an executable module.
A process
is a program that has been loaded into memory,
along with it’s stack, registers, program counter,
and status. Processes live in user space.
i.e. a process is a program in execution on a von Neumann
computer!
operating
systems
Definitions
A program
is a file that contains an executable module.
A process
is a program that has been loaded into memory,
along with it’s stack, registers, program counter,
and status. Processes live in user space.
We can think of all of the resources required to run
a process (cpu, registers, memory, …) as a virtual
or abstract machine.
A Single Process
Program Counter
Memory
stack frame
environment
variables
stack
return address
parameters
status
Registers
heap
static data
machine
instructions
copy of registers
local variables
Multi-Processing
Program Counter
Memory
environment
variables
stack
stack frame
return address
parameters
Registers
heap
static data
machine
instructions
Program Counter
status
copy of registers
local variables
Memory
environment
variables
stack
stack frame
return address
parameters
Registers
Virtual
Machine 1
heap
static data
machine
instructions
status
copy of registers
local variables
Virtual
Machine 2
Virtual
Machine 2
Load Process 1
Virtual
Machine 1
Execute Program 1
for a while …
Program Counter
Memory
stack frame
environment
variables
stack
return address
parameters
status
Registers
heap
static data
machine
instructions
copy of registers
local variables
Virtual
Machine 2
Save the state
of Process 1
on disk
Program Counter
Memory
stack frame
environment
variables
stack
Registers
Virtual
Machine 1
return address
parameters
status
heap
static data
machine
instructions
copy of registers
local variables
Virtual
Machine 2
Load Process 2
Virtual
Machine 1
Execute Program 2
for a while …
Program Counter
Memory
stack frame
environment
variables
stack
return address
parameters
status
Registers
heap
static data
machine
instructions
copy of registers
local variables
Save the state
of Process 2
on disk
Program Counter
Virtual
Machine 1
Memory
stack frame
environment
variables
stack
parameters
status
Registers
Virtual
Machine 2
return address
heap
static data
machine
instructions
copy of registers
local variables
The Process Address Space
operating
systems
0
Memory
Manager
Real Memory
In the current generation
of machines, each process
has 232 bits of address
space.
232
Address Space
Memory mapped
devices, etc
operating
systems
A process has
An address space
a program (the program segment)
data (the data segment)
resources (for example, open files)
a process identifier
Shared by all threads
Each thread running in a process has a unique
set of general purpose registers
instruction register
status registers
stack
heap
a thread identifier
Using the ps Command
The ps command provides a way to list
the current processes running on a Unix
system.
ps
lists your processes
ps –a
list all user processes
ps –al
list all user processes, in detail
ps -ax
list system processes
process id
state
niceness
parent’s
process id priority
size
terminal
operating
systems
The Process Manager
Process creation and termination
Thread creation and termination
Process/Thread synchronization
Resource allocation
Resource protection
Cooperation with device manager for I/O
Cooperation with memory manager for
address space mapping
operating
systems
Simplified
Process Management
operating
systems
Process Creation
Processes are created
* At system initialization time
* By system call from an existing process
- fork( ) in Unix
- CreateProcess( ) in Windows
* When a user requests a new process
* When a batch job is initiated
operating
systems
Process Termination
A processes terminates when
* It is done and it exits normally
* The process discovers an error and exits
* There is a fatal error and the system kills the process
* Another process kills it
operating
systems
Process Control Blocks
Program Counter
Memory
environment
variables
stack
stack frame
Implementation of
Processes
return address
parameters
Registers
heap
static data
Interrupt vector
machine
instructions
status
copy of registers
local variables
For each process, the operating system maintains a
Process control block (PCB) or Process Descriptor.
The process control block contains
important information about each process that
is used whenever a context switch takes place.
operating
systems
typical entries in a
process control block
Process Management
registers
program counter
program status word
process state
priority
scheduling parameters
process id
parent process
process group
signals
accounting info
Stack
Signal mask
ooo
Memory Management
pointer to program text
pointer to data segment
pointer to stack
base and limit regs
FileManagement
root directory
working directory
open file descriptors
user ID
group ID
Creating a New Process
(Linux)
PCB of running
process
calls fork( )
Creating a New Process
(Linux)
PCB of running
process
calls fork( )
PCB of child
process
A new process control
block is created
Creating a New Process
(Linux)
PCB of running
process
PCB of child
process
The contents of the parent PCB
are copied into the new child PCB
Then fields unique to this
process are modified
* process id
* accounting info
* timers
*…
Creating a New Process
(Linux)
PCB
PCB
The new PCB is added to a
Linked list of PCBs
PCB
PCB of child
process
Creating a New Process
(Linux)
PCB of CHILD
process
file
table
A file table is created for
the new process, and a file
descriptor is created for
each file that is open in the
parent process (i.e. the child
shares the parent’s open files.
Creating a New Process
(Linux)
The child is made the
running process
PCB of CHILD
process
address
space
file
table
An address space is created for
the new process and the contents
of the parent’s data segment and program
segment are copied into this new address space.
When a process starts another new process, two
possibilities exist in terms of execution:
1. The parent continues to execute concurrently
with its children
2. The parent waits until some or all of its children
have terminated
When a process starts another new process, two
possibilities exist in terms of the address space of
the new process:
1. The child process is an exact duplicate of the
parent process.
2. The child process has a unique program loaded
into its address space.
Process States
operating
systems
Process requests
A resource:
• Page fault
1
• I/O
Running
2
3
Process is pre-empted
by a higher priority
process, interrupt,
timer, or makes a system call
Ready
Blocked
4
The resource request
is satisfied
new
operating
systems
System
calls
Operation
old state
new state
Create
Request
Release
Destroy
(none)
running
blocked
any
ready
blocked
ready
(none)
Scheduler
ready
running
running
ready
The init process is created automatically when the system
starts up, and is destroyed when the system shuts down.
operating
systems
The ready list
pcb
pcb
pcb
When a new process is created,
It’s pcb is added to the ready list
(the set of processes that can be run).
null
operating
systems
The Scheduler
The scheduler selects the next process to be
executed. Various scheduling algorithms are
possible. We will study scheduling algorithms
in a later set of slides. For this example case, we
will use a multi-level priority scheduler with
fixed priority levels.
In this example, the ready list contains n queues,
one for each priority level. Each queue contains
a list of pointers to PCBs at that priority level.
The scheduler services the ready list in FIFO
order, starting with the highest priority queue.
The ready list
operating
systems
0
Showing priority queues
1
pcb
pcb
pcb
null
operating
systems
Context Switches
When the next process to be run has been selected
by the scheduler, the process is dispatched.
The context of a process is contained in the process
control block. When a new process is dispatched, a
context switch occurs. The state of the current process
is saved in it’s pcb, and the cpu is loaded with the context
of the new running process.
Context switches are pure overhead – there is no useful
work done during a context switch.
Trapping
operating
systems
Kernel programs are run in supervisory mode. That is,
they can execute privileged instructions not available to
normal users.
When a user program invokes a system call, the calling
code puts the system call number in a register and invokes
the trap function.
The trap function switches the machine into supervisory
mode and begins executing the dispatcher. This requires a
context switch. The dispatcher looks at the system call
number, and uses it to locate the executable code for the
function call.
The system call code executes, control is returned to the
calling program, (another context switch) and the machine
switches back to user mode.
operating
systems
Timer
To implement time-sharing, some kind of timer must be
provided. The timer issues periodic interrupts that call
the scheduler.
operating
systems
Resource Managers
operating
systems
Mechanism: generic management functions
Policy: Resource specific behavior
-Who
- Under what circumstances
- shared or exclusive
Resource Manager
Blocked
Processes
Policy
Process
request( )
release( )
Resource
Pool
operating
systems
Waiting For Resources
When a process requires a resource, it makes the
request for the resource. If the resource is not
immediately available, the process is blocked and
it waits for the resource to become available.
operating
systems
Resource Control Blocks
Resource ID
Status
• Free
• Allocated
Wait List
pcb
pcb
Requesting a Resource
operating
systems
Request ( RID)
{
r = getRCB(RID);
if (r->status == “free”)
{
r->status = “allocated”;
insert (pcb, r); // show r as being allocated to process (pcb)
}
else
{
self->status = “blocked”; // show blocked in pcb
remove (self, ready_list); // remove self from ready_list
insert ( r->waiting_list, self); // add self to resources wait list
}
scheduler( );
}
Releasing a Resource
operating
systems
Release (RID)
{
r = get_RCB(RID);
if (waiting_list == NULL) // nobody is waiting
{
r->status = “free”;
}
else
{
remove ( r->waiting_list, q); // get next process from queue
q->status = “ready”; // mark it as ready
insert (ready_list, q); // insert on ready list
}
scheduler( );
}