process ( tasks, jobs ) ~ program in execution + stack, registers + temporary data ( such as return addresses, subroutine parameters ) + program counter + other activities
process &ne program
process states
process table ( PT ) saves
When a process creates a new process, two possibilities exist in terms of execution
- The parent continues to execute concurrently with its children
- The parent waits until some or all of its children have terminated
There are two possiblilities in terms of the address space of the new process
- the child process is a duplicate of the parent
- the child process has a program loaded into it
process tree
In Unix, a new process is started with the fork() command. It starts a new process running in the same program, starting at the statement immediately following the fork() call. After the call, both the parent (the process that called fork()) and the child are both executing at the same point in the program. The child is given its own memory space, which is initialized with an exactly copy of the memory space (globals, stack, heap objects) of the parent. Thus the child looks like an exact clone of the parent, and indeed, it's hard to tell them apart. The only difference is that fork() returns 0 in the child , but returns a non-zero value in the parent.
Example
#include <iostream>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <stdlib.h>
void main()
{
int pid; //process id
pid = fork(); //create another process
if ( pid < 0 ) { //fail
cout << "\nFork failed" << endl;
exit ( -1 );
} else if ( pid == 0 ) { //child
execlp ( "/bin/ls", "ls", "-l", NULL ); //execute ls
} else { //parent
wait ( NULL ); //wait for child
cout << "\nchild complete" << endl;
exit ( 0 );
}
}
|
OS makes two related kinds of decisions about resources:
Processes may be in any one of three general scheduling states:
There are two parts to CPU scheduling:
This is an example of policy/mechanism separation.
Goals for Scheduling Disciplines
Algorithms:
- In the simplest case this means uniprogramming.
- Usually, "finished" means "blocked". One process can use CPU while another waits for an event. Go to back of run queue when ready.
- need an FIFO queue
- Problem: one process can monopolize CPU; waiting could be long
- similar to FCFS but preemption is added to swith between processes
- run process for one time slice ( quantum ), then move to back of queue ( context switch ).
- Each process gets equal share of the CPU. Most systems use some
variant of this; time quantum ~ 10 - 100 ms
-
if quantum = 20 ms
switching time = 5 ms
% of CPU time 'wasted' = 5 / ( 20 + 5 ) = 20%
if quantum = 500 ms, waste < 1%
faster CPU can increase efficiency
- Attach priority to each process ( e.g. faculty processes has higher priorites of students )
- In general, give newly runnable process a high priority and a very short time slice. If process uses up the time slice without blocking then decrease priority by 1 and double time slice for next time.
- A process running too long may have priority adjusted.
- Techniques like this one are called adaptive. They are common in interactive systems.
- The CTSS system (MIT, early 1960's) was the first to use exponential queues.
- shortest time to completion first. This minimizes the average response time.
- SJF works quite nicely; unfortunately, it requires knowledge of the future. Instead, we can use past performance to predict future performance.
Example:
| Process | burst time | |
|---|---|---|
| P1 | 6 | |
| P2 | 8 | |
| P3 | 7 | |
| P4 | 3 |
SJF:
| P4 | P1 | P3 | P2 | |
| 0 | 3 | 9 | 16 | 24 |
Average Turnaround time = ( 3 + 9 + 16 + 24 ) / 4 = 13
SJF is optimal
| first job burst time: | a |
| second job burst time: | b |
| third job burst time: | c |
| fourth job burst time: | d |
mean turnaround time
T = ( a + ( a + b ) + ( a + b + c ) + ( a + b + c + d )) /4
= ( 4a + 3b + 2c + d ) / 4
To minimize T, we need a ≤ b ≤ c ≤ d
For interactive jobs, we can regard execution of each command as a job.
For a certain terminal
-
T -- predicted time
t -- measured time
-
Tn+1 =
tn + ( 1 - ) Tn
if
= 1, Tn+1 = tn, only most recent history matters
if
= 0, Tn+1 = Tn = Tn-1 = ... = T0
recent history has no effect
= 1 / 2
| Tn+1 | = | tn / 2 + Tn / 2 |
| T1 | = | t0 / 2 + T0 / 2 |
| T2 | = | t1 / 2 + ( T0 / 2 + T1/2 ) / 2 |
| = | t1 / 2 + t0 / 4 + T0 / 4 | |
| T3 | = | t2/2 + t1 / 4 + t0 / 8 + T0 / 8 |
SJF can be preemptive or nonemptive
-
nonpreemptive -- when shortest job comes in, it has to wait
until the currently-executed job has finished
preemptive -- when shortest job comes in,
currently-executed job will be suspended
then, shortest-remaining-time-first
Example
| Process | Arrival time | Predicted time to finish |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
nonpremptive : P1, P2, P4, P3,
Average waiting time = ( 0 + 7 + 9 + 15 ) /4 = 7.75
preemptive
| P1 | P2 | P4 | P1 | P3 | |
| 0 | 1 | 5 | 10 | 17 | 18 |
Average waiting time = ( 0 + ( 5 - 3 ) + ( 10 - 1 ) + ( 17 - 2 ) ) / 4 = 26 /4 = 6.5
if insufficient main memory, some processes are kept in disk
| Processes in main memory |
Processes in disk |
|---|---|
| a b
c d |
e f
g h |
| e f
g h |
a b
c d |
| b c
f g |
a d
e h |
level 1 scheduler -- schedule process in main memory
level 2 scheduler -- shuffle process between memory and disk
asymmetric multiporcessing -- has master-slave relation; master server does the scheduling
symmetric multiprocessing:
- one common ready queue
- each processor is self-scheduling
- each processor examines the common ready queue and selects a process to execute
in hard real time systems, critical tasks are guanranteed, i.e. to be completed within a time limit:
- a process is submitted along with a statement -- time to finish
- scheduler either admits or rejects the process
in soft real-time system, critical processes receive higher priority
dispatcher -- context switch
dispatch latency -- time to switch context
In UNIX and many OS, to do context switch, it needs to wait for a system call to complete or wait for an I/O block → latency can be long
to keep dispatch latency low, need to allow system calls preemptive:
- check at premptive points to see if requests are of higher priority
or
- make the entire kernel preemptive -- in this case, all kernel
data must be protected
if the high-priority process needs to read or modify kernel data that are currently accessed by another lower-priority process, → priority inversion; chain of processes --> priority-inheritance protocol
See Introduction to Priority Inversion
e.g. Mars Pathfinder ( robot rover ) in 1997
process ~ program in execution + resources needed
A thread ( light weight process ( LWP ) ) is a basic unit of CPU utilization ~ PC + registers + stack space
a thread shares with peer threads its coded section, data section, and OS resources ( such as open files and signals ) ~ task
traditionally heavy weight process = thread + task
CPU switching much easier
-
no memory-management related work need to be done
Also, some systems implement user-level threads in user-level libraries,
rather than via system calls, so thread switching does not need to call
the OS and to cause an interrupt to the kernel. This makes the switching to
be done quickly.
Thus, blocking a thread and switching to another thread is a reasonable
solution to the problem of how a server can handle many requests efficiently.
Examples:
- Typical uses of threads
- Task switching
Comparison of multiple-thread and multiple-process control:
| multiple processes | multiple threads |
|---|---|
| has states new, ready, running, blocked, terminated | like a process, a thread has states new, ready, running, blocked, terminated |
| processes can create child processes | threads can create child threads |
| each process operates independently of the others, has its own PC, stack pointer and address space | threads are not independent of each other; threads can read or write over any other's stack |
Creating Java Thread
public class MyThread extends Thread {
public void run() {
doWork();
}
}
Thread t = new MyThread();
t.start();
In Java, there is no thread exit function, the only way to exit is to return from run() method.
Even run()
( old version Thread.stop() method is not recommended )
write a class that implements the Runnable interface, defining a run() method in it
public class MyRunnable implements Runnable {
public void run() {
doWork();
}
}
Runnable r = new MyRunnable();
Thread t = new Thread( r );
t.start();
Second method is recommended because:
- We are not changing the nature of thread itself, we are only changing run().
- If we implement Runnable interface, its possible to subclass something else more useful
SetPriority ( int priority );
Thread.MIN_PRIORITY 1 Thread.MAX_PRIORITY 10 Thread.NORM_PRIORITY 5
Example: