University of Houston

COSC MISC

apter 2: Processes:
When processes are not enough:• Single threaded
server:– Processes one request at a time for (;;)
{receive(&client, request); process_request(...); send
(client, reply);
} // for
What does a server do when it does not
process client requests?: – Nothing– It waits for client
requests– It sleeps• Blocked state is sometimes called
the sleep state
The problem:• Most client requests involve disk
accesses– File servers– Authentications servers• When
this happens, the server remains in the BLOCKED state–
Cannot handle other customers’ requests
An analogy:• In most fast-food restaurants, counter
employees process customer orders one order at a
time.• Not be possible in a traditional restaurant– A
waitperson that would only be able to wait on one table
at a time would be idle most of the time.
A first solution:int pid; for (;;) {receive(&client, request);
if ((pid = fork())== 0) { process_request(...); send (client,
reply);
_exit(0); // done} // if } // for
The good news:– Server can now handle several user
requestsin parallel• The bad news:– fork() is a very
expensive system call
A better solution:• Provide a faster mechanism for
creating cheaper processes:– Lightweight processes–
Threads
How?:• Lightweight processes and threads share the
address space of their parent– No need to create a new
address space• Most expensive step of fork() system call
Is it not dangerous?• To some extent because– No
memory protection inside an address space– Lightweight
processes can now interfere with each other• But– All
lightweight process code is written by the
same team
General Concept (I):• A thread or lightweight process–
Does not have its own address space– Shares it with its
parent and other peer threads in the same address space
(task)• Each thread has a program counter, a set of
registers and its own stack.– Everything else is shared
General Concept (II):• A regular process
(single-threaded)-One winding arrow • A process
containing several threads-Two winding arrows
Implementation:• Thread and LWPs can either be• Kernel
supported:–Mach, Linux, Windows NT and after• Userlevel:–Pthread library, …
Kernel-Supported Threads (I):• Managed by the kernel
through system calls• One process table entry per
thread• This is the best solution for multiprocessor
architectures– Kernel can allocate several processors to a
single multithreaded task
Kernel-Supported Threads (II): • Supported by Mach,
Linux, Windows NT and more recent systems•
Performance Issue: Switching between two threads in the
same task involves a system call– Results in two context
switches
Linux Threads (I):• Created through: clone (fn, stack,
flags) where– fn specifies function to be executed by the
new thread or process – stack points to the stack it will
use– flags is a set of flags specifying various options
( CLONE_VM for threads)
Linux Threads (II):• If the CLONE_VM flag is missing,
Linux creates a regular process with its own address
space
User-Level Threads (I):• User-level threads are managed
by procedures within the task address space– The thread
library• One process table entry per task/address space –
Kernel is not even aware that process is multithreaded
User-Level Threads (II):• Can be retrofitted into an OS
lacking thread support– Portable thread libraries• No
performance penalty: Switching between two threads of
the same task is done cheaply within the task– Same
cost as a procedure call
User-Level Threads (III):• Programming issue:– Each time
a thread does a blocking system call, kernel will move
the whole process to the blocked state• It does not know
better– Programmer must use non-blocking system calls•
Can be nasty
User-Level Threads (IV):sleep(5); Kernel
Process wants to sleep for 5 seconds: Let us move it to
the blocked state
Comparing the approaches:Portability(User-Level thread)
Multiprocessing(Kernel threads) Overhead(User-level
thread) Ease of use(Kernel Threads)
Conclusion• No clear winner between kernel-supported
and user-level threads• Solaris (from Sun, now taken
over by Oracle) – Supports both user-level threads and
kernel
threads– Lets programmers combine them as they need
Chapter 3: Scheduling
Non-preemptive policies: FCFS, SJF Preemptive policies:
round robin, multilevel queues w/feedback, guaranteed
scheduling Ex. UNIX, Linux, Windows NT and after
The scheduler: part of OS that decides how to allocate
the CPU & main memory to processes. Will focus here on
the CPU scheduler: decides which ready process should
get CPU; also called short-term scheduler
Objectives: a good scheduler should -minimize user
response times of all interactive processes (major
objective today); maximize system throughput; be fair;
avoid starvation
Starvation: happens when some ready processes never
get CPU time: typical of schedulers using priorities
(lowest-priority processes keep getting set aside).
Remedy is to increase the priorities of processes that
have waited too long
Fairness: ensuring fairness more difficult than avoiding
starvation (give fresh v bad food, no one starves)
Non-preemptive scheduler: will never remove the CPU
from a running process. Will wait until the process
releases the CPU b/c: it issues a system call; it
terminates. Now obsolete
Examples: First Come First Served (FCFS): simplest &
easiest to implement -uses FIFO queue. Seems good butprocesses requiring a few ms of CPU time have to wait
behind processes that make much bigger demands;
Unrealistic. Shortest Job First (SJF): gives CPU to process
requesting least amount of CPU time -will reduce avg
wait; must know ahead of time how much CPU time each
process needs (impossible); still lets processes
monopolize CPU
Preemptive schedulers: can temporarily return a running
process to the ready queue whenever another process
requires that CPU in a more urgent fashion-has been
waiting too long; has higher priority. Sole acceptable
solution
Preemptive scheduler types: PS w/o priorities: all
processes have the same priority. Ready queue is FIFO PS
w/priorities: use multiple queues. Differ in the way they
adjust process priorities
Round Robin: assumes all processes have same priority
-guaranteed to be starvation-free. Similar to FCFS but
processes only get the CPU for fixed amount of time TCPU
-time slice/time quantum. Processes that exceed their
time slice return to end of ready queue
Finding right time slice: small time slice means good
response time -no process will ever have to wait more
than (nready_queue+1) x TCPU time units where nready_queue is
number of processes already in ready queue. Large time
slice means better throughput -less context switches
Problem: Want to adjust time slice to guarantee
maximum waiting time in ready queue TCPU = TMAX/
(nready_queue+1) -works well as long as sys is lightly loaded;
produces small time slices when sys is loaded (too much
context switch overhead)
Observation: throughput of sys using RR scheduler
actually decreases when its workload exceeds some
threshold. Rare among physical systems. Frequent
among sys experiencing congestion -Freeway throughput
decreases when load exceeds threshold
Solution(I): add priorities. Distinguish among –interactive
processes; I/O-bound processes (require small amounts
of CPU time); CPU-bound processes (require large
amounts of CPU time, i.e. number crunching)
Solution(II): assign –high priorities to interactive
processes; med priorities to I/O-bound procs; low
priorities to CPU-bound proc
Solution(III): assign –smallest time slices to interactive
proc; med TS to I/O-bound proc; biggest TS to CPU-bound
proc. Allow higher priority processes to take CPU away
from lower priority processes
Outcome: interactive processes will get good response
times. CPU-bound processes will get the CPU -less
frequently than with RR; for longer periods of time;
resulting in less context switch overhead
2 Problems: How to assign priority to processes? Process
behaviors may cha