Transcript PPT

CS444/CS544
Operating Systems
Processes
1/24/2006
Prof. Searleman
[email protected]
CS444/CS544


Spring 2006
Operating System Structures
Introduction to Processes
NOTE:
Thursday’s class will be held in the ITL
(Science Center 334)
Operating System Structures



Protected Mode of Execution (user vs kernel)
System Call (“software interrupts”)
Interrupts (hardware)



Timer
I/O devices
Software “exceptions”


“trap” - request for OS service
“faults” - software errors that transfer control to
the OS
Synchronization


When we write a program, we think about adjacent
instructions happening in order without interruption
We’ve seen lots of things that can interrupt the
execution of a process (timers, I/O request
completion, etc.)



Most times this is ok; the state of our process is restored and
the illusion is maintained
But sometimes it is really important that two things happen
together with no interruption
Specifically if two processes are sharing resources
 Example: two processes updating a shared database of
account balances; one reads balance and adds $100, one
reads balance and removes $100
Hardware support for
Synchronization


Need a way to guarantee that a sequence of
instructions occur at once – at least with respect to
other entities that are accessing the same data
Solution 1: Disable Interrupts



Until re-enabled, instruction sequence will run to
completion
Would you like to allow applications to do this?
Solution 2: Provide Locks


Acquire lock, perform sequence, release lock
Sequence may be interrupted but interruption not visible to
others because they wait to acquire the lock
Building Locks


Acquiring a shared lock is the same problem as
updating a shared bank balance
Read balance ($300)
Read balance ($300)
Decrement $100 ($200)
Increment $100 ($400)
Write balance ($200)
Write balance ($400)
Is lock free? (yes)
Is lock free? (yes)
Write “I’ve got lock”
Write “I’ve got lock”
Proceed to access
Proceed to access
Withdrawal lost!
Concurrent access violating lock!
Hardware can provide a grouping of instructions that
it will guarantee to happen atomically


Test and set, read/modify/write
From these build locks, from locks build any atomic unit
Overlapping I/O and
Computation


If we want the OS to be able to efficiently
keep the CPU busy, then I/O devices need to
be able to operate independently
Even if CPU can do other work while I/O is
pending, system is still inefficient if CPU
constantly needs to check for I/O completion
(polling)



Interrupts
DMA
Buffering
Intel Architecture’s PIC


Programmable Interrupt Controller (PIC) is a chip
that offloads some interrupt processing from the
main CPU
Serves a referee to prioritize interrupt signals and
allows devices to prevent conflicts



Device interrupts go to the PIC; PIC determines which
device raised the interrupt; Sends interrupt to the CPU with
a value indicating the interrupt service routine to invoke
If multiple interrupts, PIC will buffer them and send them
one at a time to the CPU
Treated by the main CPU as a peripheral
DMA

Still if we want to transfer large chunks of data, CPU
will still need to be very involved



For each small chunk of data, CPU must write a command
to the command and address registers and transfer data
to/from the data register
Very regular pattern
DMA or Direct Memory Access automates this
process and provides even greater overlap of
computation and I/O


Tell device controller with DMA: Starting memory address
and length and it will get each piece directly from memory
as it needs it
Scatter/gather list: don’t limit it to single start/length
Buffering


Still more can be done to overlap computation and
I/O
What if I/O is slow enough and requested frequently
enough, all processes may be waiting for I/O


For writes, copy data to a buffer and then allow
process to continue while data is written from buffer
to device


I/O bound vs compute bound jobs
If system crashes?
For reads, read data ahead in anticipation of
demand
Memory Mapped I/O



For each device, set aside a range of memory that
will be mapped to the registers of the device
The CPU thinks it is reading/writing memory
locations (same instructions, same addressing
scheme)
Without memory mapped I/O, CPU needs a way to
name each register on each device controller


Special instructions? Device/register addresses?
Required knowledge of number and type of devices at
design time
Programmers/users demand
functionality

Operating systems provide commonly needed
functionality






Programmers want stable storage, want to be able to share
contents with other apps => file system with naming scheme
shared by all processes
Programmers don’t want to deal with paging their own code and
data in and out of limited physical memory (and want
protection/isolation from other processes) => virtual memory
Programmers want running processes to be able to
communicate (not complete protection and isolation) => shared
memory regions, pipes, sockets, events
Users don’t want a single task to be able to monopolize the
CPU => preemptive scheduling
Users want to be able to designate high and low priority
processes => priority scheduling
…….
Application demands exceed
OS functionality?



Not all applications are happy with the
operating system’s services
Many things an operating system does,
application programmers could do on their
own if they were sufficiently motivated
Examples:


Databases traditionally ask for a raw disk partition
and manage it themselves (who needs the FS?)
User-level thread libraries can be more efficient
than kernel level threads
Application Moves Into the OS

If a computer system is going to be used, for
one application, can avoid overhead of
crossing user/kernel protection boundary by
putting the application in the kernel
Driving forces for OS
development?



Many times platform implies operating system;
system hardware usually marketed more than OS
Choice of OS for the PC platform is not the norm
Even on PC platform, what drives OS development



Application mix, stability, politics bigger factors than OS
features?
OS features driven by stability and ease of porting/writing
apps
All this implies OS you use every day doesn’t follow
the bleeding edge like hardware
Programs vs Processes

A program is passive


Sequence of commands waiting to be run
A process is active



An instance of program being executed
There may be many processes running the same
program
Also called job or task
What makes up a process?






Address space
Code
Data
Stack (nesting of procedure calls made)
Register values (including the PC)
Resources allocated to the process

Memory, open files, network connections
Address Space Map
Biggest
Virtual
Address
Stack
(Space for local variables etc.
For each nested procedure call)
Sometimes
Reserved for
OS
Stack Pointer
Heap
(Space for memory dynamically
allocated e.g. with malloc)
Statically declared variables
(Global variables)
Code
Ox0000
(Text Segment)
PC
Sometimes
Reserved for
Error Catching
How is a process represented?



Usually a process or task object
Process Control Block
When not running how does the OS
remember everything needed to start this job
running again


Registers, Statistics, Working directory, Open
files, User who owns process, Timers, Parent
Process and sibling process ids
In Linux, task_struct defined in
include/linux/sched.h
struct task_struct {
/* these are hardcoded - don't touch */
volatile long state; /* -1 unrunnable, 0 runnable, >0
stopped */
long counter;
long priority;
unsigned long signal;
unsigned long blocked; /* bitmap of masked signals
*/
unsigned long flags; /* per process flags, defined
below */
int errno;
long debugreg[8]; /* Hardware debugging registers */
struct exec_domain *exec_domain; /* various fields
*/
struct linux_binfmt *binfmt;
struct task_struct *next_task, *prev_task;
struct task_struct *next_run, *prev_run;
unsigned long saved_kernel_stack;
unsigned long kernel_stack_page;
int exit_code, exit_signal; /* ??? */
unsigned long personality;
int dumpable:1;
int did_exec:1; /* shouldn't this be pid_t? */
int pid;
int pgrp; int tty_old_pgrp;
int session; /* boolean value for session group
leader */
int leader; int groups[NGROUPS];
/* * pointers to (original) parent process, youngest
child, younger sibling, * older sibling,
respectively. (p->father can be replaced with * p>p_pptr->pid) */
struct task_struct *p_opptr, *p_pptr, *p_cptr,
*p_ysptr, *p_osptr;
struct wait_queue *wait_chldexit; /* for wait4() */
unsigned short uid,euid,suid,fsuid;
unsigned short gid,egid,sgid,fsgid;
unsigned long timeout, policy, rt_priority;
unsigned long it_real_value, it_prof_value,
it_virt_value;
unsigned long it_real_incr, it_prof_incr, it_virt_incr;
struct timer_list real_timer;
long utime, stime, cutime, cstime, start_time;
/* mm fault and swap info: this can arguably be seen
as either mm-specific or thread-specific */
unsigned long min_flt, maj_flt, nswap, cmin_flt,
cmaj_flt, cnswap;
int swappable:1;
unsigned long swap_address;
unsigned long old_maj_flt; /* old value of maj_flt */
unsigned long dec_flt; /* page fault count of the last
time */
unsigned long swap_cnt; /* number of pages to
swap on next pass */
*semsleeping;
/* limits */
struct rlimit rlim[RLIM_NLIMITS];
unsigned short used_math;
char comm[16];
/* file system info */
int link_count;
struct tty_struct *tty; /* NULL if no tty */
/* ipc stuff */
struct sem_undo *semundo; struct sem_queue
/* ldt for this task - used by Wine. If NULL,
default_ldt is used */
struct desc_struct *ldt;
/* tss for this task */
struct thread_struct tss;
/* filesystem information */
struct fs_struct *fs;
/* open file information */
struct files_struct *files;
/* memory management info */
struct mm_struct *mm;
/* signal handlers */
struct signal_struct *sig;
#ifdef __SMP__
int processor;
int last_processor;
int lock_depth; /* Lock depth. We
can context switch in and out of holding a syscall kernel lock... */
#endif };
Management of PCBs



PCBs are data structures (just like you are used to
at user level)
Space for them may be dynamically allocated as
needed or perhaps a fixed sized array of PCBs for
the maximum number of possible processes is
allocated at init time
As process is created, a PCB is assigned and
initialized for it


Often process id is an offset into an array of PCBs
After process terminates, PCB is freed (sometimes
kept around for parent to retrieve its exit status)
Process States

During their lifetime, processes move
between various states



New – just created
Ready – waiting for a turn to use the CPU
Running – currently executing on the CPU



How many processes can be in this state? 
Waiting – Unable to use the CPU because
blocked waiting for an event
Terminated/Zombie – Finished executing but state
maintained until parent process retrieves state
State Transitions
New
Ready
Schedule/unschedule
Running
Request Resource
or Service
Grant Resource
Waiting
Terminated
State Queues

OS’s often maintain a number of queues of
processes that represent the state of the
processes



All the runnable processes are linked together
into one queue
All the processes blocked (or perhaps blocked for
a particular class of event) are linked together
As a process changes state, it is unlinked from
one queue and linked into another
State Queues
Tail ptr
Head ptr
Prev
next
Prev
next
Prev
next
Rest of PCB
Rest of PCB
Rest of PCB
Ready queue, queues per device, queue of all processes, …
Context Switch



When a process is running, some of its state is
stored directly in the CPU (register values, etc.)
When the OS stops a process, it must save all of
this hardware state somewhere (PCB) so that it
can be restored again
The act of saving one process’ hardware state
and restoring another’s is called a context switch

100s or 1000s per second!
Context Switch
Schedulers


Technically two kinds of schedulers
Short-term scheduler (or CPU scheduler)



Selects which process should be executed next
and allocates CPU.
Short-term scheduler is invoked very frequently
(milliseconds)  (must be fast).
Long-term scheduler (or job scheduler)



Selects which processes should be brought into
the ready queue.
Determines the degree of multiprogramming
In reality this is usually you the human user
What kinds of processes are
there?







Compute bound/ IO bound
Long-running/short-running
Interactive/batch
Large/small memory footprint
Cooperating with other processes?
…
How do we get all these different kinds of
processes?
Family Tree


Age old questions – where do new processes
come from?
New processes are created when an existing
process requests it



Creating process called the parent; created called
the child
Children of same parent called siblings
Children often inherit privileges/attributes
from their parent

Working directory, Clone of address space
pstree
init-+-18*[Xvnc]
|-amd
|-atd
|-bdflush
|-crond
|-16*[deskguide_apple]
|-8*[gconfd-1]
|-gedit
|-18*[gnome-name-serv]
|-16*[gnome-session]
|-16*[gnome-smproxy]
|-gnome-terminal-+-csh---gtop
|
`-gnome-pty-helpe
|-gnome-terminal-+-csh-+-gtop
|
| `-tcsh
|
`-gnome-pty-helpe
|-gnome-terminal-+-csh---tcsh--xterm---csh
|
`-gnome-pty-helpe
|-gpm
|-8*[hyperbola]
|-keventd
|-khubd
|-5*[kjournald]
|-klogd
|-ksoftirqd_CPU0
|-ksoftirqd_CPU1
|-kswapd
|-kupdated
|-lockd
init-+-18*[Xvnc]
|-16*[magicdev]
|-mdrecoveryd
|-migration_CPU0
|-migration_CPU1
|-6*[mingetty]
|-2*[nautilus---nautilus---8*[nautilus]]
|-2*[nautilus---nautilus---10*[nautilus]]
|-3*[nautilus---nautilus---9*[nautilus]]
|-nautilus---nautilus---7*[nautilus]
|-7*[nautilus-histor]
|-nautilus-mozill---nautilus-mozill---4*[nautilusmozill]
|-8*[nautilus-news]
|-8*[nautilus-notes]
|-7*[nautilus-throbb]
|-ntpd
|-13*[oafd]
|-16*[panel]
|-portmap
|-16*[rhn-applet]
|-rhn-applet---gnome_segv
|-rhnsd
|-rpc.statd
|-rpciod
|-14*[sawfish]
|-2*[sawfish---rep]
|-scsi_eh_0
|-scsi_eh_1
|-sendmail
init-+-18*[Xvnc]
|-sshd-+-2*[sshd---csh---mc]
|
|-sshd---csh
|
|-sshd---csh-+-more
|
|
`-netstat
|
`-sshd---csh---pstree
|-syslogd
|-16*[tasklist_applet]
|-xemacs
|-xfs---xfs
|-xinetd---fam
|-xscreensaver---greynetic
|-xscreensaver---hopalong
|-2*[xscreensaver---xscreensaver]
|-xscreensaver---kumppa
|-xscreensaver---spotlight
|-xscreensaver---spiral
|-xscreensaver---nerverot
|-xscreensaver---strange
|-xscreensaver---flame
|-xscreensaver---grav
|-xscreensaver---lightning
|-xscreensaver---penetrate
|-xscreensaver---rotzoomer---xscreensaver-ge
|-xscreensaver---deluxe
|-xscreensaver---rd-bomb
|-xscreensaver---sonar
|-xscreensaver---moire2
`-ypbind---ypbind---2*[ypbind
UNIX process creation

Fork() system call






Creates a new PCB and a new address space
Initializes the new address space with a *copy* of the
parent’s address space
Initializes many other resources to copies of the parents
(e.g. same open files)
Places new process on the queue of runnable processes
Fork gives two processes exactly alike
Fork() returns twice: to parent and child


Returns child’s process ID to the parent
Returns 0 to the child
Example Code Snippet
int main (int argc, char **argv)
{
int childPid;
childPid = fork();
if (childPid == 0){
printf(“Child running\n”);
} else {
printf(“Parent running: my child is %d\n”,
childPid);
}
}
Output
%./tryfork
Parent running: my child is 707
Child running
%
Experiments – Be Careful!



Try putting an infinite loop in the child’s portion ( do
you return to the command shell?) and then looking
for it in the ps output
Try putting an infinite loop in the parent’s portion (do
you return to the command shell?)
Put an infinite loop in both


try killing the child (look in the ps output for the child and
the parent)
Try killing the parent – what happens to the child?
Exec

How do we get a brand new process not just a
copy of the parent?



Exec:





Stops the current process
Loads the program, prog, into the address space
Passes the arguments specified in argv
Places the PCB back on the ready queue
Exec “takes over” the process



Exec () system call
int exec (char * prog, char ** argv)
There is no going back to it when it returns
Try to exec something in your shell (example: exec ls) –
when ls is done your shell is gone because ls replaced it!
Note: execvp will search users path automatically
Better way?

Don’t fork/exec seem a bit wasteful to you

Why make a full copy of the parent’s virtual memory space
if we are just going to overwrite it anyway?

Function “vfork” creates a new process without fully
copying the parent’s address space
Parent suspended while child temporarily “borrows”
its memory and thread of control (unlike fork)
Man vfork for warnings about _exit vs exit

Experiment: Time N iterations of fork or vfork


Foreground vs Background
int main (int argc, char **argv){
while (1){
int childPid;
char* cmdLine = readCommandLine();
if (userChooseExit(cmdLine)){
wait for all background jobs
}
childPid = fork();
if (childPid == 0){
setSTDOUT_STDIN_STDERR(cmdLine);
exec( getCommand(cmdLine));
} else if (runInForeground(cmdLine)){
wait(childPid);
} else {
Record childPid In list of background jobs}
}
}