This is the html version of the file http://www.eng.tau.ac.il/~isp/lectures/lecture2.ppt.
G o o g l e automatically generates html versions of documents as we crawl the web.
To link to or bookmark this page, use the following url: http://www.google.com/search?q=cache:ABdS4gqGsgQC:www.eng.tau.ac.il/~isp/lectures/lecture2.ppt+CreateProcess+simple+example&hl=en&ie=UTF-8
Google is not affiliated with the authors of this page nor responsible for its content.
These search terms have been highlighted: createprocess simple example
Avishai Wool
lecture 2 1
Introduction to Systems Programming
Lecture 2
Processes & Scheduling
Avishai Wool
lecture 2
Categories of System Calls
System calls provide API: language spoken by the virtual machines (processes) applications run on.
Process management: creation, destruction, contents
I/O devices management:
File system: file creation/deletion, reading/writing, access rights
Network devices: opening/closing, reading/writing, standing by
Virtual memory management
Inter-process communication
Avishai Wool
lecture 2
Why Multiple Processes?
Tool for parallelism: e.g., read input while producing output
Better utilization of resources
Concurrent independent programs
Modularity
Many users can share the system
Avishai Wool
lecture 2 4
Which processes are running?
Unix: the ps command shows the active processes. To see all processes type ?ps ?aux? (linux) or ?ps ?ef? (Sun)
Lots of output so use ?ps ?aux | more?
Alternative: the ?top? command
Windows 2000 / XP:
Alt+Ctrl+Del ? Task Manager
Windows 98:
Alt+Ctrl+Del
Start ? Programs ? Accessories ? System Tools ? System Monitor
Avishai Wool
lecture 2 5
How is a process realized?
Process Control Block (PCB): a data structure in OS.
CPU state: registers
Memory maps
Static info: PID, owner, file?
Resources in use (devices, files)
Accounting (CPU usage, memory usage...)
Avishai Wool
lecture 2 6
process table
Why so?
Allow preemption and resumption
Enforce security policy
Resources are used only via handles
check once, save credentials for later
handles can?t be used by another process
pid
resource
struct
process
OS
Avishai Wool
lecture 2
Process Management System Calls
Create a process
allocate initial memory
allocate process ID
loads initial binary image
optionally: send arguments to process
Destroy a process
terminate the process
free resources associated with it
optionally: return value
Wait for a process: block until specified process terminates, optionally obtain returned value
Avishai Wool
lecture 2 8
Unix Processes
Parent process creates children processes (recursively: get a tree of processes)
Resource sharing
Parent and children usually share some resources
Execution
Parent and children execute concurrently.
Parent waits until children terminate.
Avishai Wool
lecture 2 9
Unix Process Creation
Address space
Child duplicate of parent.
Child has a program loaded into it.
Two system calls needed
fork system call creates new process
exec system calls replaces process? memory space with a new program.
Near one-to-one relationship between system call and C library function that issues the system call.
Avishai Wool
lecture 2
Unix Process Management
fork: (return TWICE if successful)
Create a copy of the current process
Return 0 to the ?child? process
Return child?s pid to the ?parent? process
execv(file,argv): (NEVER return if successful)
Make current process run file with given arguments argv
exit(code): (NEVER return if successful)
Terminate current process with given return code (0 means OK)
waitpid(pid, &code, options): (return only when appropriate)
Block until child exits
Return exit code of dead process.
Avishai Wool
lecture 2
Simple Example
int pid, ret_val;
char* args[10];
// ...
if ((pid = fork()) == 0) { // child process args[0] = ?17?; args[1] = ?Moshe?;
args[2] = (char*) 0; // end of args execv(?a.out?, args);
}
// only parent reaches here
if (waitpid(-1, &ret_val, 0) == pid) //...
Avishai Wool
lecture 2 12
Fork Example: Chain
#include
void main(void)
{
int i;
for (i = 0; i < 6; i++)
{
if (fork() != 0)
break; // parent exits the loop
}
fprintf(stderr,
?Process: %ld Parent: %ld\n",
(long)getpid(), (long)getppid());
}
Avishai Wool
lecture 2 13
Fork Example: Fan
void main(void)
{
int i;
pid_t childpid;
for (i = 0; i < 6; i++)
{
if ((childpid = fork()) <= 0)
break; // child exits the loop
}
fprintf(stderr,
?Process: %ld Parent: %ld\n",
(long)getpid(), (long)getppid());
sleep(1);
}
Avishai Wool
lecture 2 14
Win32 API Process Management
In Windows there is a huge library of ?system? functions called the Win32 API.
Not all functions result in system calls.
CreateProcess() ? Create a new process (fork+execve)
ExitProcess() ? Terminate Execution
WaitForSingleObject() ? Wait for termination
Can wait for many other events
There is no separation into fork and execv in Win32
No Parent-Child relationship.
Avishai Wool
lecture 2
event: an interrupt or a signal from another process
Process Life Cycle
new
ready
running
terminated
waiting
admitted
interrupt/yield
scheduled
wait for event
event
occurrence
exit, kill
Avishai Wool
lecture 2
OS maintains lists of processes.
current process runs, until either
an interrupt occurs, or
it makes a system call, or
it runs for too long (interrupt: timer expired)
OS gets control, handles the interrupt/syscall
OS places current process in appropriate list
Dispatcher/scheduler (a part of the OS):
chooses new ?current process? from the ready list
loads registers from PCB ? activates the process
Process Scheduling Basics
context switch
Avishai Wool
lecture 2 17
Schematic Scheduling
Avishai Wool
lecture 2 18
CPU scheduling by OS
CPU scheduling decisions when a process:
1. Switches from running to waiting state. (syscall)
2. Switches from running to ready state. (interrupt)
3. Switches from waiting to ready. (interrupt)
Terminates. (syscall)
Dispatcher: Module in OS to execute scheduling decisions. This is done by:
switching context
switching to user mode
jumping to the proper location in the user program to restart that program
Avishai Wool
lecture 2 19
To Preempt or not to Preempt?
Preemptive: A Process can be suspended and resumed
Non-preemptive: A process runs until it voluntarily gives up the CPU (wait for event or terminate).
Most modern OSs use preemptive CPU scheduling, implemented via timer interrupt.
Non-preemptive is used when suspending a process is impossible or very expensive: e.g., can?t ?replace? a flight crew in middle of flight.
Avishai Wool
lecture 2 20
Typical CPU burst distribution
Avishai Wool
lecture 2 21
Scheduling Criteria
Abstract scheduling terminology
CPU == Server
CPU burst == job
System view:
Utilization: percentage of the time server is busy
Throughput: number of jobs done per time unit
Individual job view:
Turnaround time: how long does it take for a job to finish
Waiting time: turnaround time minus ?solo? execution time
Avishai Wool
lecture 2 22
Example: FCFS Scheduling
First Come, First Served. Natural, fair, simple to implement
Assume non-preemptive version
Example: Jobs are P1 (duration: 24 units); P2 (3); and P3 (3), arriving in this order at time 0
Gantt Chart for FCFS schedule:
Average waiting time: (0 + 24 + 27)/3 = 17
P1
P2
P3
24
27
30
0
Avishai Wool
lecture 2 23
FCFS: continued
What if arrival order is P2 , P3 , P1 ?
Gantt chart:
Average waiting time: (6 + 0 + 3)/3 = 3
Much better!
Convoy effect: many short jobs stuck behind one long job
P1
P3
P2
6
3
30
0
Avishai Wool
lecture 2 24
Scheduling policy: SJF
?Shortest Job First?:
Assume each job has a known execution time
Schedule the shortest job first
Can prove: SJF ensures least average waiting time!
In pure form, mostly theoretical:
OS does not know in advance how long the next CPU burst will last
Avishai Wool
lecture 2 25
Preemptive Scheduling: Round Robin
Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.
If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units.
Performance
q ?too? large ? FCFS
But q must be large with respect to context switch, otherwise overhead is too high.
Avishai Wool
lecture 2 26
Round Robin: Example
Process Burst Time
P1 53
P2 17
P3 68
P4 24
Gantt chart for time quantum 20:
Typically, higher average turnaround than SJF, but better response.
P1
P2
P3
P4
P1
P3
P4
P1
P3
P3
0
20
37
57
77
97
117
121
134
154
162
Avishai Wool
lecture 2 27
SJF in CPU scheduling
Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time.
Two alternatives:
Non-preemptive ? once CPU given to the process it cannot be preempted until completes its CPU burst.
Preemptive ? if a new process arrives with CPU burst length less than remaining time of current executing process, preempt. Aka Shortest-Remaining-Time-First (SRTF).
But: OS does not know length of next CPU burst!
Avishai Wool
lecture 2 28
Estimating length of CPU burst
Idea: use length of previous CPU bursts
Heuristic: use exponential averaging (aging).
Avishai Wool
lecture 2 29
Exponential Averaging
Expanding the formula, we get:
?n+1 = ? tn+(1 - ?) ? tn-1 + ?
+(1 - ? )j ? tn-j + ?
+(1 - ? )n ?0
Since both ? and (1 - ?) are less than or equal to 1, each successive term has less weight than its predecessor.
? =0
?n+1 = ?n = ? = ?0
Recent history does not count.
? =1
?n+1 = tn
Only the actual last CPU burst counts.
Avishai Wool
lecture 2 30
Exponential Averaging: Example
?=0.5
Avishai Wool
lecture 2 31
Priority Scheduling
Idea: Jobs are assigned priorities.
Always, the job with the highest
priority runs.
Note: All scheduling policies are
priority scheduling!
Question: How to assign priorities?
priority 1
priority 2
priority M
Avishai Wool
lecture 2 32
Example for Priorities
Static priorities can lead to starvation!
Avishai Wool
lecture 2 33
Dynamic Priorities
Example: multilevel feedback
Avishai Wool
lecture 2 34
Dynamic Priorities: Unix
Initially: base priority (kernel/user)
While waiting: fixed
Count running time (clock interrupts, PCB)
Priority of a process is lowered if its CPU usage is high
CPU counter is reduced by ? every second
User can lower priority by calling ?nice?