Transcript Process Management

Operating Systems
Course: Operating Systems
Instructor: Umar Kalim
NUST Institute of Information Technology, Pakistan
http://www.niit.edu.pk
Agenda ~ Process Management
•
Processes
−
−
−
−
−
Process Concept
Process Scheduling
Operations on Processes
Cooperating Processes
Inter-process Communication
Process Concept
•
•
An operating system executes a variety of programs:
− Batch system – jobs
− Time-shared systems – user programs or tasks
− Textbook uses the terms job and process almost interchangeably
Process – a program in execution; a unit of work; process
execution must progress in sequential fashion
− Earlier OSes ~ only one program to be executed
Past: program had complete control over the system
• Now: multiple programs loaded and executing concurrently
•
−
•
Finer control and compartmentalization is required
Resources to be allocated
− CPU time, memory, files and I/O Devices
− These resources are allocated to the process either when it is
created or while it is executing
Process in Memory
•
•
A process is more than
program code (a.k.a. text
section)
It includes:
− program counter
− stack
− data section
•
−
global variables
heap
•
Variables required for the
scope of the program ~
allocated dynamically; at
runtime
Process is not same as a program
•
A program is a passive entity, a process is an active entity
−
•
•
With a program counter specifying the next instruction to
execute and a set of associated resources
Program ~ *.exe
Although two processes may be associated with the
same program, they are nevertheless considered two
separate execution sequences
Several users may be running different copies of the mail
program
− The same user may invoke many copies of the editor
program
− Each of these is a separate process
−
•
Text sections are equivalent, the data sections carry
Process State
•
As a process executes, it changes state
new: The process is being created
running: Instructions are being executed
waiting: The process is waiting for some event to occur
ready: The process is waiting to be assigned to a
processor
− terminated: The process has finished execution
−
−
−
−
The ps Command
•
Shows the snapshot of the current processes
−
−
−
bash$ ps
To view documentation
• bash$ man ps
To view the status of current processes, execute
• bash$ ps -S
• Look for entries under STAT header
PID TTY
3361 pts/2
3589 pts/2
STAT TIME COMMAND
Ss 0:00 /bin/bash
R+ 0:00 \_ ps -Sf
ps -S (status codes)
Here are the different values that the s, stat and state output specifiers
(header "STAT" or "S") will display to describe the state of a process.
D Uninterruptible sleep (usually IO)
R Running or runnable (on run queue)
S Interruptible sleep (waiting for an event to complete)
T Stopped, either by a job control signal or because it is being traced.
W paging (not valid since the 2.6.xx kernel)
X dead (should never be seen)
Z Defunct ("zombie") process, terminated but not reaped by its parent.
For BSD formats and when the stat keyword is used, additional characters may
be displayed:
< high-priority (not nice to other users)
N low-priority (nice to other users)
L has pages locked into memory (for real-time and custom IO)
s is a session leader
l is multi-threaded (using CLONE_THREAD, like NPTL pthreads do)
+ is in the foreground process group
ps -S
•
Try
−
−
−
−
−
ps -s
ps -as
pstree
X
ps -A S
[umar@dexter ~]$ ps
PID TTY
TIME CMD
3361 pts/2 00:00:00 bash
3836 pts/2 00:00:00 ps
[umar@dexter ~]$ ps -S
PID TTY
STAT TIME COMMAND
3361 pts/2 Ss
0:01 /bin/bash
3611 pts/3 Ss
0:00 /bin/bash
3630 pts/3 S+
0:00 man ps
3633 pts/3 S+
0:00 sh -c (cd /usr/share/man && (echo ".pl
1100i"; /usr/b
3634 pts/3 S+
0:00 sh -c (cd /usr/share/man && (echo ".pl
1100i"; /usr/b
3641 pts/3 S+
0:00 /usr/bin/less -is
3764 pts/4 Ss+ 0:00 /bin/bash
3837 pts/2 R+
0:00 ps -S
All system processes
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
[umar@dexter ~]$ ps -A S
PID TTY STAT TIME COMMAND
1?
S 0:10 init [5]
2?
SN 0:00 [ksoftirqd/0]
3?
S 0:00 [watchdog/0]
4?
S< 0:00 [events/0]
5?
S< 0:00 [khelper]
6?
S< 0:00 [kthread]
8?
S< 0:00 [kacpid]
99 ?
S< 0:00 [kblockd/0]
148 ?
S 0:00 [pdflush]
149 ?
S 0:00 [pdflush]
151 ?
S< 0:00 [aio/0]
150 ?
S 0:00 [kswapd0]
102 ?
S 0:00 [khubd]
238 ?
S 0:00 [kseriod]
459 ?
S 0:00 [kjournald]
988 ?
S<s 0:05 udevd
1382 ?
S< 0:00 [khsfd/modem]
1602 ?
S< 0:00 /usr/bin/perl /usr/sbin/hsfdcpd 0
1612 ?
S 0:00 [shpchpd_event]
Process Control Block (PCB)
Information associated with each
process
• Process state
• Process number
• Program counter
• CPU registers
• CPU scheduling information
• Memory-management
information
• Accounting information
• I/O status information
Top command
[umar@dexter ~]$ top
top - 19:52:13 up 54 min, 5 users, load average: 0.36, 0.44, 0.41
Tasks: 96 total, 1 running, 95 sleeping, 0 stopped, 0 zombie
Cpu(s): 2.0% us, 0.7% sy, 0.0% ni, 96.7% id, 0.0% wa, 0.7% hi, 0.0% si
Mem: 450176k total, 385664k used, 64512k free, 19508k buffers
Swap: 554200k total,
0k used, 554200k free, 211736k cached
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
3060 root 15 0 94996 16m 2428 S 1.3 3.7 6:00.22 X
3360 slk
15 0 33564 17m 13m S 0.3 4.1 0:05.87 konsole
3485 slk
15 0 289m 106m 46m S 0.3 24.3 4:24.84 soffice.bin
4135 slk
16 0 2020 984 784 R 0.3 0.2 0:00.24 top
1 root 16 0 1748 568 492 S 0.0 0.1 0:01.07 init
2 root 34 19 0 0 0 S 0.0 0.0 0:00.00 ksoftirqd/0
3 root RT 0 0 0 0 S 0.0 0.0 0:00.00 watchdog/0
4 root 10 -5 0 0 0 S 0.0 0.0 0:00.06 events/0
5 root 11 -5 0 0 0 S 0.0 0.0 0:00.02 khelper
6 root 10 -5 0 0 0 S 0.0 0.0 0:00.00 kthread
CPU Switch From Process to Process
•
•
•
When CPU switches
to another process,
the system must
save the state of the
old process and
load the saved state
for the new process
Context-switch time
is overhead; the
system does no
useful work while
switching
Time dependent on
hardware support
Process Scheduling
Course: Operating Systems
Instructor: Umar Kalim
NUST Institute of Information Technology, Pakistan
http://www.niit.edu.pk
Process Scheduling Queues
•
Multiprogramming ~ Process scheduler
•
Usually implemented as linked lists
Job queue – set of all processes in the system
• Ready queue – set of all processes residing in main
memory, ready and waiting to execute
• Device queues – set of processes waiting for an I/O
device
•
•
Processes migrate among the various queues
Ready Queue And Various I/O Device Queues
Representation of Process Scheduling
Schedulers
•
A process migrates between various scheduling queues
throughout its lifetime
−
•
Long-term scheduler (or job scheduler) – selects which
processes should be brought into the ready queue
−
•
The OS must select processes from these queues in some
fashion
Long-term scheduler is invoked very infrequently
(seconds, minutes)  (may be slow) ~ when process exits
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)
Schedulers (Cont.)
•
•
The long-term scheduler controls the degree of
multiprogramming
Processes can be described as either:
−
−
•
I/O-bound process – spends more time doing I/O than
computations, many short CPU bursts
CPU-bound process – spends more time doing computations;
few very long CPU bursts
Long-term scheduler should select a good process mix
of IO bound and CPU bound processes
−
−
If all processes are IO bound, the ready queue will almost
always be empty, short term scheduler will have little to do
If all processes are CPU bound, the IO waiting queue will
almost always be empty, devices will go unused
Addition of Medium Term Scheduling
•
Medium term scheduler
−
−
Removes processes form memory (and active
CPU contention) (Swapping)
Reduces the degree of multiprogramming
Operations on Processes
Course: Operating Systems
Instructor: Umar Kalim
NUST Institute of Information Technology, Pakistan
http://www.niit.edu.pk
Process Creation
•
•
Parent process create children processes, which, in turn
create other processes, forming a tree of processes
Resource sharing
Parent and children share all resources
− Children share subset of parent’s resources
− Parent and child share no resources
−
•
•
Restricting a child process to a subset of the parent’s
resources prevents any process from overloading the
system by creating many sub-processes
Execution
Parent and children execute concurrently
− Parent waits until children terminate
−
Process Creation (Cont.)
•
Address space
Child duplicate of parent
− Child has a program loaded into it
−
•
UNIX examples
fork system call creates new process
− exec system call used after a fork to replace the process’
memory space with a new program
−
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);
}
}
A tree of processes on a typical Solaris
Process Termination
•
Process executes last statement and asks the operating
system to delete it (exit)
Output data from child to parent (via wait)
− Process’ resources are deallocated by operating system
−
•
Parent may terminate execution of children processes
(abort)
Child has exceeded allocated resources
− Task assigned to child is no longer required
− If parent is exiting
−
•
Some operating system do not allow child to continue if its
parent terminates
−
All children terminated - cascading termination
Inter-process Communication
Course: Operating Systems
Instructor: Umar Kalim
NUST Institute of Information Technology, Pakistan
http://www.niit.edu.pk
Cooperating Processes
•
•
•
Independent process cannot affect or be affected by the
execution of another process
Cooperating process can affect or be affected by the
execution of another process
Advantages of process cooperation
Information sharing
− Computation speed-up
− Modularity
−
•
Convenience
Communications Models
Producer-Consumer Problem
•
One method could be to use shared memory
•
Paradigm for cooperating processes, producer process
produces information that is consumed by a consumer
process
unbounded-buffer places no practical limit on the size of
the buffer
− bounded-buffer assumes that there is a fixed buffer size
−
Bounded-Buffer – Shared-Memory Solution
•
Shared data
#define BUFFER_SIZE 10
typedef struct {
. . .
} item;
item buffer[BUFFER_SIZE];
int in = 0; /*next free location*/
int out = 0; /*first full location*/
•
Solution is correct, but can only use BUFFER_SIZE-1
elements
Bounded-Buffer – Insert() Method
while (true) {
/* Produce an item */
while (((in = (in + 1) % BUFFER
SIZE count) == out)
; /* do nothing –
no free buffers */
buffer[in] = item;
in = (in + 1) % BUFFER SIZE;
}
Bounded Buffer – Remove() Method
while (true) {
while (in == out)
; // do nothing –
nothing to consume
// remove an item from the buffer
item = buffer[out];
out = (out + 1) % BUFFER SIZE;
return item;
}
Communications Models
Inter-process Communication (IPC)
Mechanism for processes to communicate and to
synchronize their actions
• Message system – processes communicate with each
other without resorting to shared variables
• IPC facility provides two operations:
•
send(message) – message size fixed or variable
− receive(message)
−
•
If P and Q wish to communicate, they need to:
establish a communication link between them
− exchange messages via send/receive
−
•
Implementation of communication link
physical (e.g., shared memory, hardware bus)
− logical (e.g., logical properties)
−
Implementation Questions
How are links established?
• Can a link be associated with more than two processes?
• How many links can there be between every pair of
communicating processes?
• What is the capacity of a link?
• Is the size of a message that the link can accommodate
fixed or variable?
• Is a link unidirectional or bi-directional?
•
Direct Communication ~ Naming
•
Processes must name each other explicitly:
send (P, message) – send a message to process P
− receive(Q, message) – receive a message from process Q
−
•
Properties of communication link
Links are established automatically
− A link is associated with exactly one pair of
communicating processes
− Between each pair there exists exactly one link
− The link may be unidirectional, but is usually bidirectional
−
Indirect Communication
•
Messages are directed and received from mailboxes
(also referred to as ports)
Each mailbox has a unique id
− Processes can communicate only if they share a
mailbox
−
•
Properties of communication link
Link established only if processes share a common
mailbox
− A link may be associated with many processes
− Each pair of processes may share several
communication links
− Link may be unidirectional or bi-directional
−
Indirect Communication
•
Operations
create a new mailbox
− send and receive messages through mailbox
− destroy a mailbox
−
•
Primitives are defined as:
send(A, message) – send a message to mailbox A
receive(A, message) – receive a message from
mailbox A
Indirect Communication
•
Mailbox sharing
P1, P2, and P3 share mailbox A
− P1, sends; P2 and P3 receive
− Who gets the message?
−
•
Solutions
Allow a link to be associated with at most two processes
− Allow only one process at a time to execute a receive
operation
− Allow the system to select arbitrarily the receiver. Sender
is notified who the receiver was.
−
Synchronization
•
•
Message passing may be either blocking or nonblocking
Blocking is considered synchronous
Blocking send has the sender block until the message is
received
− Blocking receive has the receiver block until a message is
available
−
•
Non-blocking is considered asynchronous
Non-blocking send has the sender send the message and
continue
− Non-blocking receive has the receiver receive a valid
message or null
−
Buffering
•
Queue of messages attached to the link; implemented in
one of three ways
1. Zero capacity – 0 messages
Sender must wait for receiver (rendezvous)
2. Bounded capacity – finite length of n messages
Sender must wait if link full
3. Unbounded capacity – infinite length
Sender never waits
•
Recommended Reading:
− Book ~ 102 - 108
− OSRC
• http://www.nondot.org/sabre/os/articles
− C. A. R. Hoare, " Communicating Sequential Processes ," Communications of
the ACM, Vol. 21, No. 8, August 1978, pp. 666-677.
• http://www.csie.fju.edu.tw/~yeh/research/papers/os-reading-list/hoarecacm78-csp.pdf
− B. N. Bershad, et. al., " User-level Interprocess Communication for Shared
Memory Multiprocessors ," ACM Transactions on Computer Systems, Vol. 9,
No. 2, May 1991, pp. 175-198.
• http://www.csie.fju.edu.tw/~yeh/research/papers/os-reading-list/bershadtocs91-uipc.pdf
Questions?
Course: Operating Systems
Instructor: Umar Kalim
NUST Institute of Information Technology, Pakistan
http://www.niit.edu.pk
All system processes
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
1709 ?
1716 ?
1759 ?
1773 ?
2062 ?
2321 ?
2323 ?
2333 ?
2351 ?
2366 ?
2370 ?
2394 ?
2407 ?
2411 ?
2430 ?
2562 ?
2601 ?
2614 ?
2646 ?
S 0:00 [pccardd]
S 0:00 [pccardd]
S 0:00 [khpsbpkt]
S 0:00 [knodemgrd_0]
Ss 0:00 /sbin/cardmgr
Ss 0:00 syslogd -m 0
Ss 0:00 klogd -x
Ss 0:00 portmap
Ss 0:00 rpc.statd
S<sl 0:00 auditd
S< 0:00 [kauditd]
Ss 0:00 rpc.idmapd
Ss 0:00 hcid: processing events
Ss 0:00 sdpd
S< 0:00 [krfcommd]
Ss 0:00 /usr/sbin/automount --timeout=60 /misc file /etc/auto.misc
Ss 0:00 /usr/sbin/automount --timeout=60 /net program /etc/auto.net
Ss 0:01 nifd -n
Ssl 0:00 mDNSResponder
All system processes
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
2655 ?
2683 ?
2731 ?
2748 ?
2754 ?
2763 ?
2771 ?
2792 ?
2800 ?
2807 ?
2815 ?
2826 ?
2835 ?
2840 ?
2852 ?
Ss 0:00 /usr/sbin/acpid
Ss 0:00 cupsd
Ss 0:00 /usr/sbin/sshd
Ss 0:00 sendmail: accepting connections
Ss 0:00 sendmail: Queue runner@01:00:00 for /var/spool/clientmqueue
Ss 0:00 gpm -m /dev/input/mice -t imps2
Ss 0:00 crond
Ss 0:00 xfs -droppriv -daemon
SNs 0:00 anacron -s
Ss 0:00 /usr/sbin/atd
Ss 0:00 dbus-daemon --system
Ss 0:00 cups-config-daemon
Ss 0:00 hald --retain-privileges
S
0:00 hald-addon-acpi
S
0:00 hald-addon-storage
All system processes
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
2867 tty1 Ss+ 0:00 /sbin/mingetty tty1
2868 tty2 Ss+ 0:00 /sbin/mingetty tty2
2869 tty3 Ss+ 0:00 /sbin/mingetty tty3
2870 tty4 Ss+ 0:00 /sbin/mingetty tty4
2871 tty5 Ss+ 0:00 /sbin/mingetty tty5
2872 tty6 Ss+ 0:00 /sbin/mingetty tty6
2873 ?
Ss 0:00 /bin/sh /etc/X11/prefdm -nodaemon
3016 ?
S 0:00 /usr/bin/gdm-binary -nodaemon
3055 ?
S 0:00 /usr/bin/gdm-binary -nodaemon
3060 ?
S 3:59 /usr/X11R6/bin/X :0 -audit 0 -auth /var/gdm/:0.Xauth -nolisten tcp vt7
3128 ?
Ss 0:00 /bin/sh /usr/bin/startkde
3173 ?
Ss 0:00 /usr/bin/ssh-agent /usr/bin/dbus-launch --exit-with-session
/home/umar/.Xclients
3176 ?
S 0:00 /usr/bin/dbus-launch --exit-with-session /home/umar/.Xclients
3177 ?
Ss 0:00 dbus-daemon --fork --print-pid 8 --print-address 6 --session
3221 ?
Ss 1:04 kdeinit Running...
3224 ?
S 0:00 dcopserver [kdeinit] --nosid
3226 ?
S 0:00 klauncher [kdeinit]
All system processes
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
3229 ?
Sl 0:03 kded [kdeinit]
3231 ?
S 0:01 /usr/libexec/gam_server
3242 ?
S 0:00 /usr/bin/artsd -F 10 -S 4096 -s 60 -m artsmessage -c drkonqi -l 3 -f
3244 ?
S 0:00 kaccess [kdeinit]
3245 ?
S 0:00 kwrapper ksmserver
3247 ?
S 0:00 ksmserver [kdeinit]
3248 ?
S 0:02 kwin [kdeinit] -session
10138e4e6d1000114155882700000171980000_1141622029_439608
3250 ?
S 0:02 kdesktop [kdeinit]
3253 ?
S 0:20 kicker [kdeinit]
3259 ?
S 0:00 /usr/bin/pam-panel-icon --sm-client-id
10138e4e6d1000114155882900000171980006
3260 ?
S 0:00 /sbin/pam_timestamp_check -d root
3261 ?
S 0:00 eggcups --sm-config-prefix /eggcups-ZAA9c0/ --sm-client-id
10138e4e6d100011415588300
3263 ?
S 0:01 /usr/bin/autorun -l --interval=1000 --cdplayer=/usr/bin/kscd
3266 ?
S 0:00 /usr/libexec/gconfd-2 14
3273 ?
S 0:04 konqueror [kdeinit] -mimetype inode/directory file:///home/umar
All system processes
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
3277 ?
S
0:00 kio_file [kdeinit] file /tmp/ksocket-umar/klauncherB8ipNa.slave-socket /tmp/ksocket-s
3360 ?
S
0:03 konsole [kdeinit]
3361 pts/2 Ss 0:01 /bin/bash
3474 ?
S
0:00 /bin/sh /usr/lib/openoffice.org1.9.104/program/soffice -draw /home/umar/ch4-processes
3485 ?
Sl 2:27 /usr/lib/openoffice.org1.9.104/program/soffice.bin -draw /home/umar/ch4-processes.sxd
3611 pts/3 Ss 0:00 /bin/bash
3630 pts/3 S+ 0:00 man ps
3633 pts/3 S+ 0:00 sh -c (cd /usr/share/man && (echo ".pl 1100i"; /usr/bin/gunzip -c '/usr/share/man/ma
3634 pts/3 S+ 0:00 sh -c (cd /usr/share/man && (echo ".pl 1100i"; /usr/bin/gunzip -c '/usr/share/man/ma
3641 pts/3 S+ 0:00 /usr/bin/less -is
3657 ?
S
0:00 knotify [kdeinit]
3764 pts/4 Ss 0:00 /bin/bash
3855 pts/4 S
0:00 su
3858 pts/4 S+ 0:00 bash
3895 pts/2 R+ 0:00 ps -A S
Schedulers (Cont.)
•
•
•
•
Short-term scheduler is invoked very frequently
(milliseconds)  (must be fast)
Long-term scheduler is invoked very infrequently
(seconds, minutes)  (may be slow)
The long-term scheduler controls the degree of
multiprogramming
Processes can be described as either:
I/O-bound process – spends more time doing I/O than
computations, many short CPU bursts
− CPU-bound process – spends more time doing
computations; few very long CPU bursts
−