Transcript module_11

Process Description and Control
Module 1.1
1
When to Switch a Process ?

A process switch may occur whenever the
OS has gained control of CPU. ie when:
 Supervisor
Call
 explicit
request by the program (ex: file open).
The process will probably be blocked
 Trap
 An
error resulted from the last instruction. It may
cause the process to be moved to the Exit state
 Interrupt
 the
cause is external to the execution of the
current instruction. Control is transferred to IH
2

Examples of interrupts
 Clock
 process
has expired his time slice and is
transferred to the ready state
 I/O
 first
move the processes that were waiting for
this event to the ready (or ready suspend) state
 then resume the running process or choose a
process of higher priority
 Memory
fault
 memory
address is in virtual memory so it must
bring corresponding block into main memory
 thus move this process to a blocked state
(waiting for the I/O to complete)
3
Mode Switching





4
It may happen that an interrupt does not
produce a process switch
The control can just return to the
interrupted program
Then only the processor state information
needs to be saved on stack
This is called mode switching (user to
kernel mode when going into IH)
Less overhead: no need to update the PCB
like for process switching
Steps in Process (Context) Switching






5
Save context of processor including
program counter and other registers
Update the PCB of the running process
with its new state and other associate info
Move PCB to appropriate queue - ready,
blocked
Select another process for execution
Update PCB of the selected process
Restore CPU context from that of the
selected process
Execution of the Operating System


6
Up to now, by process we were referring to
“user process”
If the OS is just like any other collection of
programs, is the OS a process?

If so, how it is controlled?

The answer depends on the OS design.
Nonprocess Kernel (old)




7
The concept of process applies only to user
programs
OS code is executed as a separate entity in
privilege mode
OS has its own memory regions and stack
OS code never gets executed within a process
Execution within User Processes



8
Virtually all OS code gets executed within the
context of a user process
On Interrupts, Traps, System calls: the CPU
switch to kernel mode to execute OS routine
within the context of user process (mode switch)
Control passes to process switching functions
(outside processes) only when needed
Execution within User Processes



9
OS code and data are
in the shared address
space and are shared
by all user processes
Separate kernel stack
for calls/returns when
the process is in
kernel mode
Within a user process,
both user and OS
programs may execute
(more than 1)
Process-based Operating System




10
The OS is a collection of system processes
major kernel functions are separate processes
small amount of process switching functions is
executed outside of any process
Design that easily makes use of multiprocessors
UNIX SVR4 Process management


Most of OS executes within user processes
Uses two categories of processes:
 System
processes
 run
periodically in kernel mode for administrative
and housekeeping functions (memory allocation,
process swapping...)
 User
processes
 run
in user mode for user programs
 run in kernel modes for system calls, traps, and
interrupts
11
UNIX SVR4 Process States


Similar to our 7 state model
2 running states: User and Kernel



Sleeping states (in memory, or swapped)
correspond to our blocking states
A preempted state (timeout) is distinguished from
the ready state (but they form 1 queue)


transitions to other states (blocked, ready) must come
from kernel running
In the same ready queue, there are two states
Preemption can occur only when a process is
about to move from kernel to user mode
Kernel code is not preemptable
 To simplify switching, when the process resumes
running, it runs in the user running (with empty kernel
stack)

12
UNIX Process State Diagram
13
14
Context Switch


15
Context Switch Mechanism
 The kernel permits it under four circumstances:
 When a process puts itself to sleep
 When it exits
 When it returns from a system call to user mode
 When it returns to user mode after interrupt handling
 The kernel ensures integrity and consistency of internal data structures by
prohibiting arbitrary context switches.
 The procedure for a context switch is similar to the procedures for
handling interrupts and system calls, except that the kernel restores the
context layer of a different process instead of the previous context layer of
the same process.
Steps for a Context Switch
UNIX Process Image

User-level context
 Process
Text (ie: code: read-only)
 Process Data
 User Stack (calls/returns in user mode)
 Shared memory (for IPC)
 only
one physical copy exists but, with virtual
memory, it appears as it is in the process’s
address space

16
Register context
UNIX Process Image

System-level context
 Process
table entry
 the
actual entry concerning this process in the
Process Table maintained by OS
• Process state, UID, PID, priority, event awaiting, signals
sent, pointers to memory holding text, data...
U
(user) area
 additional
process info needed by the kernel
when executing in the context of this process
• effective UID, timers, limit fields, files in use ...
 Kernel
stack (calls/returns in kernel mode)
 Per Process Region Table (used by memory manager)
 Page
17
tables defining code, stack, data regions
18
UNIX System Processes


19
Process 0 is created at boot time and
becomes the “swapper” after forking
process 1 (the INIT process)
When a user logs in: process 1 creates a
process for that user
Processes in UNIX System



20
User Process
 most processes on typical system
 associated with users at a terminal
Daemon Process
 not associated with any users
 do system-wide functions
 administration and control of networks, execution of timedependent activities, line printer spooling, and so on
 run at user mode and make system calls to access system
service like user process
Kernel Process
 execute only in kernel mode
 process 0 spawns kernel process, such as page-reclaiming
process vhand, and then becomes the swapper process
 extremely powerful, not flexible
A tree of processes on a typical
Solaris
21
UNIX Process Creation

Every process, except process 0, is
created by the fork() system call
 fork()
allocates entry in process table and
assigns a unique PID to the child process
 child gets a copy of process image of parent:
both child and parent are executing the same
code following fork()
 but fork() returns the PID of the child to the
parent process and returns 0 to the child
process
22
C Program Forking Separate Process
int main()
{
Pid_t pid;
/* fork another process */
pid = fork();
if (pid < 0) { /* error occurred */
fprintf(stderr, "Fork Failed");
exit(-1);
}
else if (pid == 0) { /* child process
*/
execlp("/bin/ls", "ls", NULL);
}
else { /* parent process */
/* parent will wait for the
child to complete */
wait (NULL);
printf ("Child Complete");
exit(0);
}
}
23
Note that system(“/bin/ls”)
standard C library function
is equivalent to fork() and
then exec(“bin/ls”).
Virtual Memory – Review

The memory referenced by a
logical address is called virtual
memory
 is maintained on
secondary memory (ex:
disk)
 pieces are brought into
main memory only when
needed
 For better performance,
the file system is often
bypassed and virtual
memory is stored in a
special area of the disk
called the swap space

24
larger blocks are used
and file lookups are not
used.
Paging – Review


25
Typically, each process has
its own page table.
Page tables are variable in
length (depends on process
size). Stored in main
memory instead of registers.
A single register holds the
starting physical address of
the page table of the running
process.
Address Translation in a Paging System –
Review
26
Sharing Pages of a text editor – Review
27
Translation Lookaside Buffer – Review
28
TLB Comments – Review



TLB use associative mapping hardware to simultaneously
interrogates all TLB entries to find a match on page number
The TLB must be flushed each time a new process enters the
Running state
The CPU uses two levels of cache on each virtual memory
reference
 first the TLB: to convert the logical address to the physical
address




29
TLB is a special on-chip cache (other than L1,L2, L3
caches)
If no on-chip TLB, L1 will typically have it.
once the physical address is formed, the CPU then looks
in the cache for the referenced word in L1, L2 and L3
Caches
L1 is the fastest and the most expensive, followed by L2,
followed by L3
L1 & L2 Caches -- Review
30
Referencing a memory word -- Review
31
Unix Processes & Region
Virtual
addresses of the
regions are
connected
Only 4K bytes are
shared, and not the
whole region
32
Layout of the Unix Kernel





33
Although the kernel executes in the context of a process, the
virtual memory mapping associated with the kernel is
independent of all processes.
The code and data for the kernel reside in the system
permanently, and all processes share it.
The kernel page tables are analogous to the page tables
associated with a process.
In many machines, the virtual address space of a process is
divided into several classes, including system and user, and
each class has its own page tables.
When executing in kernel mode, the system permits access
to kernel addresses, but it prohibits such access when
executing in user mode.
•Example of the virtual addresses of
the kernel and a process regions
•Kernel text/data (first two triples)
•Kernel stack within process (third triple)
•Process (text/data,stack)
34
Ref count of
processes accessing
the current directly.
Used when opening
a local filenename,
not starting with “/”.
This is logical
copy. Text is
shared and only
reference count is
copied.
35
In case parent process
or one of its ancestors
did chroot
Fork Creating a New Process Context
Parent Process
Parent
Data
Per Process
Region Table
U Area
Open Files
Current Directory
Changed Root
Parent
User
Stack
File
Table
.
.
.
.
.
Kernel Stack
Shared
Text
Child
Data
Per Process
Region Table
U Area
Open Files
Current Directory
Changed Root
.
.
.
.
.
Kernel Stack
Child
User
Stack
Child Process
36
Inode
Table
37
38
Inode of the
executable file,
with region type
“Data”.
Done also for
code and stack.
39
40
41
If the shell recognizes the input string as a built-in command (e.g., cd, for,
while, …), it executes the command internally without creating new process;
otherwise, it assumes the command is the name of an executable file.
42
For commands with &, the shell does not wait but immediately restarts the
loops and reads the next command line.
We need first to understand system calls for the file systems.
43
Introduction to Unix file system





44
Unix is an indexed file
system
Every file on a UNIX system
has a unique indode that
contains the information
necessary to for a process to
access a file by a well
defines system calls.
Processes specify the file by
its path name.
Internally, the algorithm
namei converts a user-level
path to inode number.
Inodes are stored in a linear
array on disk.
Contains also
link counts
and reference
counts
45
Byte Capacity of a File

System V UNIX. Assume that









46
Run with 13 entries
1 logical block : 1K bytes
Block number address : a 32 bit (4byte) integer
1 block can hold up to 256 block number (1024byte / 4byte)
10 direct blocks with 1K bytes each=10K bytes
1 indirect block with 256 direct blocks= 1K*256=256K bytes
1 double indirect block with 256 indirect blocks=256K*256=64M
bytes
1 triple indirect block with 256 double indirect
blocks=64M*256=16G
Size of a file : 4G (232), if file size field in inode is 32bits


A directory is a file
whose data is a
sequence of entries,
each consisting an
inode number and the
name of a file.
If inode number is 0, it
indicates that the entry
is empty (i.e., available for
use again).
47
namei
48
link count – hard links counts representing file names in directory hierarchy
reference count (will see shortly) -- for opening and referencing files by
processes
49
50
•Kernel maintains two data
structures: file table and
user fd table
•File table is a global kernel
structure
•User fd table is allocated
per process
•The file table keeps track of
the byte offset in the file
where the user’s next read
or write will start, and the
access rights allows to
opening process
51
52
53
So what happens when we do close(stdout)?
How about dup(fd)?
54
DUP


The dup system call copies a fd into the first free
slot of the user fd table, returning the new fd to the
user.
Syntax


Why is this needed?


newfd = dup(fd);
Servers in building sophisticated system programs as
that of the shell
Assume

A process opened the file “/etc/passwd” fd3, then
opened “local” fd4, then opened the file “/etc/passwd”
 fd5, and finally duped fd3 returning fd6.

55
See illustration of this on next slide
56
So what really happened?
 How redirecting input??
57
How about piping?
58
Piping

Pipe
 fifo(first-in-first-out)
 Synchronization
of process execution
 Its data is transient: once data is read from a pipe,
it cannot be read again
 Use only direct block (not the indirect block)
59
60
The Shell
1. reads a command line from its standard input and interprets it
2. built in command
 cd,
for, while …
 executes command internally without creating process
3. simple command line(program and parameters)
grep –n include *.c, ls -l
 forks and creates a child process
 execs the program user specified
 shell waits until the child process exits
 who,
4. run a process asynchronously(in the background)
–mm bigdocument &
 sets an internal variable amper
 shell does not execute wait
 nroff
5. redirect standard output to a file
–mm bigdocument &
 the child creates the output file
 closes its standard output
 dup its file descriptor to standard output
 redirects standard input and standard error in similar way
 nroff
61
The Shell(Cont.)
6. pipe





ls –l | wc
parent process forks and creates a child process
child creates a pipe
child process forks and creates a grandchild process
grandchild process handles the first command(ls)







62
close its standard input file descriptor
dups the pipe read descriptor
close original pipe read descriptor
output of grandchild(ls) goes to the input of child(wc)
parent shell waits its child(wc) to exit
wait
exit
wc
read
child process handles the second command(wc)


close its standard output file descriptor
dups the pipe write descriptor
close original pipe write descriptor
Shell
ls -l
write