Algorithm Evaluation
How do we select a CPU-scheduling algorithm?
1. Define desired criteria
E.g., maximize CPU utilization with the constraint that max response time < 1 second
2. Evaluate algorithms under consideration
Four algorithm evaluation methods:
1. Deterministic modeling
2. Queuing models
3. Simulations
4. Implementation
Deterministic Modeling
Take a predetermined workload and determine the performance of each algorithm for that workload
Simple and fast
Results only valid for specific workloadnot useful
Queuing Models
The computer system contains a number of servers, each has a queue of waiting processes.
E.g., CPU with ready queue, I/O device with device queue
Queuing- network analysis: given distribution of process arrival and distribution of service time, we can compute utilization, average queue length, average waiting time, etc.
Require inaccurate/unrealistic assumptions for numerical solutionsresults may not be accurate
E.g. assume process arrival follows Poisson distribution, service time follows exponential distribution, processes are independent
Simulations
Write a simulator to simulate the activities in the system
Gather statistics of the algorithm performance as the simulation executes
Two ways to generate the data to drive the simulation:
1. Generate workload according to certain probability distribution
2. Use the sequence of actual events in the real system (recorded on a trace tape)
Advantage: results are accurate
Drawback:
Non-trivial to design, code, and debug a simulator
Simulations are time consuming
Implementation
Implement the scheduling algorithm in a real system
Cost is tremendous: coding algorithm, modifying kernel data structures, system must be taken down
Ideally, we want flexible scheduling algorithms
During OS build-time, boot time, or run time, variables used by the scheduler can be changed by system manager or by user
Scheduling in Practice
Solaris 2
Windows 2000
Linux
Solaris 2 Scheduling
Priority based, preemptive scheduling
Four scheduling classes, each includes a set of priorities:
Time sharing: default class for a process
Use multilevel feedback queue with time slicing in each queue
The higher the priority, the smaller the time slice
Interactive processes have higher prioritygood response time
CPU-bound processes have lower prioritygood throughput
Interactive:
Same scheduling policy as time sharing class
Give a priority boost to the task in the active window
System: for system threads
Threads have fixed priority
No time-slicing: thread runs until it blocks or is preempted by a higher
priority thread
Real-time: for processes that require immediate system access
Threads have fixed priority
Time slicing among threads with the same priority.
Windows 2000 Scheduling
Priority-based, preemptive scheduling
32 priority levels, large integer = high priority
One queue for each priority, RR scheduling in each queue
Six priority classes: real-time, high, above normal, normal, below normal, idle
Seven levels of relative priority per class
An integer priority is assigned to a thread based on the (class, relative priority) pair
For processes not in the real-time priority class, relative priority may be raised or lowered
Lowered when a thread’s time quantum runs outlimit CPU consumption of CPU-bound threads
Increased when a thread is released from a wait operation
give good response time to interactive threads
When a process moves into the foreground (i.e., currently selected on screen), increase time quantum by some factor (typically by 3)
Windows 2000 Priorities
Linux Scheduling
Two scheduling classes: time-sharing and real-time
Real-time class has priority over time-sharing class
Only processes running in user mode may be preempted
Time-sharing scheduling
Each process has a priority and a certain number of credits
Scheduler chooses the process with the most credits
Running process loses 1 credit when a timer interrupt occurs
Running process is suspended when its credits becomes 0
If all processes in ready queue have no credit, perform a recrediting operation
For every process, credits = credits/2 + priority (large integer =high priority)
The crediting system automatically gives high priority to interactive or I/O bound processes
Linux Scheduling
Real-time scheduling
Two scheduling classes
FCFS (no preemption)
RR (preemption when time-slice expires)
Each process has a priority and belongs to one scheduling class
Scheduler always runs the process with the highest priority.
Among processes of equal priority, use FCFS or RR
Process Creation
A process (parent) may create new processes (children) during execution
Resource sharing
Child obtains resources from OS
Parent and child share resources (such as memory or files)
Execution
Parent and children execute concurrently.
Parent waits until some or all children have terminated
Address space
Child is a duplicate of parent.
Child has a program loaded into it.
Process Creation in UNIX
int fork() : create a child process identical to parent
Child process has a copy of the address space of the parent process
On success:
Both parent and child continue execution at the instruction after fork
For parent: return code is the process ID (PID) of child
For child: return code is 0
On failure:
Child not created
Return code is –1 for parent
Waiting for Process Termination in UNIX
int wait(int *status) //wait for any child to terminate
int waitpid(int pid, int *status, int options) //wait for the specified child to terminate
If status is not NULL, status information of child is stored in the location pointed to by status.
Options: 0 - wait until child has exited
WNOHANG - return immediately if no child has exited
Return value: the process ID of the child which exited, or zero if
WNOHANG was used and no child was available, or -1 on error
If a child terminates before parent calls wait:
When parent calls wait, it returns immediately and child’s PCB is deallocated.
Loading Programs in UNIX
int execl(const char *path, const char *arg, ...);
int execlp(const char *file, const char *arg, ...);
int execv(const char *path, char *const argv[]);
int execvp(const char *file, char *const argv[]);
Used after a fork to replace a process’ memory space with a new program.
Does not return on success, return –1 on error
Second parameter:
l - list of arguments
v – array of arguments
Both list and array must be terminated by a NULL pointer
First parameter:
empty – full path of executable
p – name of executable, will search the search path for executable
Process Termination in UNIX
A process terminates when it makes the exit system call.
May return data to parent, parent can collect the data using wait.
Resources deallocated by operating system.
If a parent terminates without waiting for its children:
The init process becomes the children’s parent
The init process will wait for the children to terminate
Cooperating Processes
Independent process - cannot affect or be affected by
the execution of another process
Do not share data with any other process
Cooperating process - can affect or be affected by the
execution of another process
Share data with other processes
Concurrent execution of cooperating processes requires
mechanisms for process communication and
synchronization
Producer-Consumer Problem
A common paradigm for cooperating processes
A producer process produces information that is consumed by a consumer process.
Have a buffer of items filled by the producer and emptied by the consumer
unbounded-buffer - no limit on the size of the buffer
bounded-buffer - assume a fixed buffer size
Producer and consumer run concurrently and must be synchronized
Bounded-Buffer Shared-Memory Solution
Shared data
#define BUFFER_SIZE 10
typedef struct {
. . .
} item;
item buffer[BUFFER_SIZE];
int in = 0; //next free position in buffer
int out = 0; //first full position in buffer
Shared buffer implemented as a circular array
Buffer empty when in == out
Buffer full when (in+1) % BUFFER_SIZE == out
Allow at most BUFFER_SIZE-1 items in buffer
Producer Process
item nextProduced;
while (1) {
while (((in + 1) % BUFFER_SIZE) == out)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
}
Consumer Process
item nextConsumed;
while (1) {
while (in == out)
; /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
}
Interprocess Communication (IPC)
Allow processes to communicate and to synchronize their actions without sharing the same address space
Message-Passing System:
IPC facility provides two operations:
send(message)
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
UNIX pipes, sockets
Direct Communication
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
A link is established automatically between a pair of processes that want to communicate.
A link is associated with exactly two processes.
Between each pair there exists exactly one link.
The link may be unidirectional, but is usually bi-directional.
Indirect Communication
Messages are sent to and received from mailboxes (or ports).
Processes can communicate only if they share a mailbox.
Primitives:
send(A, message) – send a message to mailbox A
receive(A, message) – receive a message from mailbox A
Properties of communication link
A link is established between a pair of processes only if they
have a shared mailbox
A link may be associated with more than two processes.
Multiple links may exist between a pair of processes, each
link corresponds to one mailbox.
A link may be unidirectional or bi-directional.
Synchronization
Message passing may be either blocking or nonblocking (also knows as synchronous and
asynchronous)
Blocking send: sending process is blocked until the message is received by the receiving process or by the mailbox
Nonblocking send: sending process continues execution after sending a message
Blocking receive: receiver blocks until a message is available
Nonblocking receive: receiver gets (immediately) either a valid message or a null.
Buffering
Messages exchanged by communicating processes reside in a queue implemented in one of three ways.
1. Zero capacity: queue has maximum length 0
Link cannot have a message waiting
Sender must block until recipient receives message
2. Bounded capacity: queue has finite length n
A link can have at most n messages waiting.
Sender blocks if queue is full.
3. Unbounded capacity: queue has infinite length
No bound on number of waiting messages
Sender never blocks.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment