Test 2

Question 1

Multi threaded architecture

Answer 1

Most modern applications are multithreaded
Process creation is heavy-weight while thread creation is light-weight

Benefits
Responsiveness – may allow continued execution if part of process is blocked, especially important for user interfaces
Resource Sharing – threads share resources of process, easier than shared memory or message passing
Economy – cheaper than process creation, thread switching lower overhead than context switching
Scalability – process can take advantage of multiprocessor architectures

Question 2

Multicore programming

Answer 2

Multicore or multiprocessor systems putting pressure on programmers, challenges include:
Dividing activities
Balance
Data splitting
Data dependency
Testing and debugging
Parallelism implies a system can perform more than one task simultaneously
Concurrency supports more than one task making progress
Single processor / core, scheduler providing concurrency

Question 3

Parallelism

Answer 3

Multicore programming:
Types of parallelism
Data parallelism – distributes subsets of the same data across multiple cores, same operation on each
Task parallelism – distributing threads across cores, each thread performing unique operation
As # of threads grows, so does architectural support for threading
CPUs have cores as well as hardware threads
Consider Oracle SPARC T4 with 8 cores, and 8 hardware threads per core

Question 4

Items Shared/Not Shared by Threads

Answer 4

Shared by all threads in a process
Address space
Global variables
Static variables
Open files
Accounting information

Per thread items:
Program counter
Registers
Stack
State

Question 5

Amdahl’s Law

Answer 5

LECTURE 9
Identifies performance gains from adding additional cores to an application that has both serial and parallel components
S is serial portion
N processing cores

That is, if application is 75% parallel / 25% serial, moving from 1 to 2 cores results in speedup of 1.6 times
As N approaches infinity, speedup approaches 1 / S

Serial portion of an application has disproportionate effect on performance gained by adding additional cores

Question 6

User Threads and Kernel Threads

Answer 6

User threads - management done by user-level threads library
Three primary thread libraries:
 POSIX Pthreads
 Windows threads
 Java threads
Kernel threads - Supported by the Kernel
Examples – virtually all general purpose operating systems, including:
Windows 
Solaris
Linux
Tru64 UNIX
Mac OS X

Question 7

Many-to-One- multithreading models

Answer 7

Many user-level threads mapped to single kernel thread
One thread blocking causes all to block
Multiple threads may not run in parallel on muticore system because only one may be in kernel at a time
Few systems currently use this model
Examples:
Solaris Green Threads
GNU Portable Threads

Question 8

ONe-to-ONe- multithreading models

Answer 8

Each user-level thread maps to kernel thread
Creating a user-level thread creates a kernel thread
More concurrency than many-to-one
Number of threads per process sometimes restricted due to overhead
Examples
Windows
Linux
Solaris 9 and later

Question 9

Many-to-many multithreading models

Answer 9

Allows many user level threads to be mapped to many kernel threads
Allows the operating system to create a sufficient number of kernel threads
Solaris prior to version 9
Windows with the ThreadFiber package

Question 10

two level model multithreading models

Answer 10

Similar to M:M, except that it allows a user thread to be bound to kernel thread
Examples
IRIX
HP-UX
Tru64 UNIX
Solaris 8 and earlier

Question 11

thread library

Answer 11

Thread library provides programmer with API for creating and managing threads
Two primary ways of implementing
Library entirely in user space
Kernel-level library supported by the OS

Question 12

pthreads

Answer 12

May be provided either as user-level or kernel-level
A POSIX standard (IEEE 1003.1c) API for thread creation and synchronization
Specification, not implementation
API specifies behavior of the thread library, implementation is up to development of the library
Common in UNIX operating systems (Solaris, Linux, Mac OS X)

Question 13

java threads

Answer 13

Java threads are managed by the JVM
Typically implemented using the threads model provided by underlying OS
Java threads may be created by:

public interface Runnable() {
public abstract void run();
}

Extending Thread class
Implementing the Runnable interface

Question 14

implicit threading

Answer 14

Growing in popularity as numbers of threads increase, program correctness more difficult with explicit threads
Creation and management of threads done by compilers and run-time libraries rather than programmers
Three methods explored
Thread Pools
OpenMP
Grand Central Dispatch
Other methods include Microsoft Threading Building Blocks (TBB), java.util.concurrent package

Question 15

thread pools

Answer 15

Create a number of threads in a pool where they await work
Advantages:
Usually slightly faster to service a request with an existing thread than create a new thread
Allows the number of threads in the application(s) to be bound to the size of the pool
Separating task to be performed from mechanics of creating task allows different strategies for running task
i.e.Tasks could be scheduled to run periodically
Windows API supports thread pools:

Question 16

threading issues

Answer 16

Semantics of fork() and exec() system calls
Signal handling
-Synchronous and asynchronous
Thread cancellation of target thread
-Asynchronous or deferred
Thread-local storage
Scheduler Activations

Question 17

semantics of fork() and exec()

Answer 17

Does fork()duplicate only the calling thread or all threads?
Some UNIXes have two versions of fork
exec() usually works as normal – replace the running process including all threads

Question 18

signal handling

Answer 18

Signals are used in UNIX systems to notify a process that a particular event has occurred.
A signal handler is used to process signals
Signal is generated by particular event
Signal is delivered to a process
Signal is handled by one of two signal handlers:
default
user-defined
Every signal has default handler that kernel runs when handling signal
User-defined signal handler can override default
For single-threaded, signal delivered to process

Where should a signal be delivered for multi-threaded?
Deliver the signal to the thread to which the signal applies
Deliver the signal to every thread in the process
Deliver the signal to certain threads in the process
Assign a specific thread to receive all signals for the process

■ The method for delivering a signal depends on the type of signal
● Synchronous signals need to be delivered to the thread causing the signal, not other threads
● Terminating a process signal should be sent to all threads within the process

Question 19

thread cancellation

Answer 19

Terminating a thread before it has finished
Thread to be canceled is target thread
Two general approaches:
Asynchronous cancellation terminates the target thread immediately
Deferred cancellation allows the target thread to periodically check if it should be cancelled
Pthread code to create and cancel a thread:

pthread_t tid;

pthread. create(&tid, 0, worker, NULL);
pthread. cancel(tid);

Invoking thread cancellation requests cancellation, but actual cancellation depends on thread state

If thread has cancellation disabled, cancellation remains pending until thread enables it
Default type is deferred
Cancellation only occurs when thread reaches cancellation point
I.e. pthread_testcancel()
Then cleanup handler is invoked
On Linux systems, thread cancellation is handled through signals

Question 20

thread local storage

Answer 20

Thread-local storage (TLS) allows each thread to have its own copy of data
Useful when you do not have control over the thread creation process (i.e., when using a thread pool)
Different from local variables
Local variables visible only during single function invocation
TLS visible across function invocations
Similar to static data
TLS is unique to each thread

Question 21

windows threads

Answer 21

Windows implements the Windows API – primary API for Win 98, Win NT, Win 2000, Win XP, and Win 7
Implements the one-to-one mapping, kernel-level
Each thread contains
A thread id
Register set representing state of processor
Separate user and kernel stacks for when thread runs in user mode or kernel mode
Private data storage area used by run-time libraries and dynamic link libraries (DLLs)
The register set, stacks, and private storage area are known as the context of the thread

Question 22

linux threads

Answer 22

Linux refers to them as tasks rather than threads
Thread creation is done through clone() system call
clone() allows a child task to share the address space of the parent task (process)
Flags control behavior

struct task_struct points to process data structures (shared or unique)

Question 23

process synchronization background

Answer 23

Processes can execute concurrently
May be interrupted at any time, partially completing execution
Concurrent access to shared data may result in data inconsistency
Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes
Illustration of the problem:
Suppose that we wanted to provide a solution to the consumer-producer problem that fills all the buffers. We can do so by having an integer counter that keeps track of the number of full buffers. Initially, counter is set to 0. It is incremented by the producer after it produces a new buffer and is decremented by the consumer after it consumes a buffer.

Question 24

race condition

Answer 24

counter++ could be implemented as

 register1 = counter
 register1 = register1 + 1
 counter = register1 counter-- could be implemented as

 register2 = counter
 register2 = register2 - 1
 counter = register2

Consider this execution interleaving with “count = 5” initially:
S0: producer execute register1 = counter {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = counter {register2 = 5}
S3: consumer execute register2 = register2 – 1 {register2 = 4}
S4: producer execute counter = register1 {counter = 6 }
S5: consumer execute counter = register2 {counter = 4}

Question 25

critical section problem

Answer 25

Consider system of n processes {p0, p1, … pn-1}
Each process has critical section segment of code
Process may be changing common variables, updating table, writing file, etc
When one process in critical section, no other may be in its critical section
Critical section problem is to design protocol to solve this
Each process must ask permission to enter critical section in entry section, may follow critical section with exit section, then remainder section

Question 26

critical section solution and handling in OS

Answer 26

1. Mutual Exclusion - If process Pi is executing in its critical section, then no other processes can be executing in their critical sections
2. Progress - If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the process that will enter the critical section next cannot be postponed indefinitely
3. Bounded Waiting - A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted
   Assume that each process executes at a nonzero speed
   No assumption concerning relative speed of the n processes

handling in OS
Two approaches depending on if kernel is preemptive or non- preemptive
Preemptive – allows preemption of process when running in kernel mode
Non-preemptive – runs until exits kernel mode, blocks, or voluntarily yields CPU
Essentially free of race conditions in kernel mode

Question 27

peterson’s solution and algorithm

Answer 27

Good algorithmic description of solving the problem
Two process solution
Assume that the load and store machine-language instructions are atomic; that is, cannot be interrupted
The two processes share two variables:
int turn;
Boolean flag[2]

The variable turn indicates whose turn it is to enter the critical section
The flag array is used to indicate if a process is ready to enter the critical section. flag[i] = true implies that process Pi is ready!

algorithm
	do { 
		flag[i] = true;
		turn = j;
		while (flag[j] && turn = = j); 
			critical section 
		flag[i] = false; 
			remainder section 
	 } while (true); 

Provable that the three CS requirement are met:
1. Mutual exclusion is preserved
Pi enters CS only if:
either flag[j] = false or turn = i
2. Progress requirement is satisfied
3. Bounded-waiting requirement is met

Question 28

synchronization hardware

Answer 28

Many systems provide hardware support for implementing the critical section code.
All solutions below based on idea of locking
Protecting critical regions via locks
Uniprocessors – could disable interrupts
Currently running code would execute without preemption
Generally too inefficient on multiprocessor systems
Operating systems using this not broadly scalable
Modern machines provide special atomic hardware instructions
Atomic = non-interruptible
Either test memory word and set value
Or swap contents of two memory words

Question 29

solution to critical section problem using locks

Answer 29

do { 
		acquire lock 
			critical section 
		release lock 
			remainder section 
	} while (TRUE);

Question 30

test_and_set instruction

Answer 30

Definition:
       boolean test_and_set (boolean *target)
          {
               boolean rv = *target;
               *target = TRUE;
               return rv:
          }

Executed atomically
Returns the original value of passed parameter
Set the new value of passed parameter to “TRUE”.

solution using test and set:
Shared Boolean variable lock, initialized to FALSE
Solution:
       do {
          while (test_and_set(&lock)) 
             ; /* do nothing */ 
                 /* critical section */ 
          lock = false; 
                 /* remainder section */ 
       } while (true);

Question 31

compare_and_swap instruction

Answer 31

Definition:
int compare _and_swap(int *value, int expected, int new_value) {
int temp = *value;

     if (*value == expected) 
        *value = new_value; 
  return temp; 
 }  Executed atomically Returns the original value of passed parameter “value” Set  the variable “value”  the value of the passed parameter “new_value” but only if “value” ==“expected”. That is, the swap takes place only under this condition.

Question 32

mutex locks

Answer 32

Previous solutions are complicated and generally inaccessible to application programmers
OS designers build software tools to solve critical section problem
Simplest is mutex lock
Protect a critical section by first acquire() a lock then release() the lock
Boolean variable indicating if lock is available or not
Calls to acquire() and release() must be atomic
Usually implemented via hardware atomic instructions
But this solution requires busy waiting
This lock therefore called a spinlock

acquire and release

   acquire() {
       while (!available) 
          ; /* busy wait */ 
       available = false; 
    } 
   release() { 
       available = true; 
    } 
   do { 
    acquire lock
       critical section
    release lock 
      remainder section 
 } while (true);

Question 33

semaphore

Answer 33

Synchronization tool that provides more sophisticated ways (than Mutex locks)  for processes to synchronize their activities.
Semaphore S – integer variable
Can only be accessed via two indivisible (atomic) operations
wait() and signal()
Originally called P() and V()
Definition of  the wait() operation
wait(S) { 
    while (S <= 0)
       ; // busy wait
    S--;
}
Definition of  the signal() operation
signal(S) { 
    S++;
}

semaphore usage:
Counting semaphore – integer value can range over an unrestricted domain
Binary semaphore – integer value can range only between 0 and 1
Same as a mutex lock
Can solve various synchronization problems
Consider P1 and P2 that require S1 to happen before S2
Create a semaphore “synch” initialized to 0
P1:
S1;
signal(synch);
P2:
wait(synch);
S2;
Can implement a counting semaphore S as a binary semaphore

Question 34

semaphore implementation (with and without busy waiting)

Answer 34

Must guarantee that no two processes can execute the wait() and signal() on the same semaphore at the same time
Thus, the implementation becomes the critical section problem where the wait and signal code are placed in the critical section
Could now have busy waiting in critical section implementation
But implementation code is short
Little busy waiting if critical section rarely occupied
Note that applications may spend lots of time in critical sections and therefore this is not a good solution

with no busy waiting
With each semaphore there is an associated waiting queue
Each entry in a waiting queue has two data items:
value (of type integer)
pointer to next record in the list
Two operations:
block – place the process invoking the operation on the appropriate waiting queue
wakeup – remove one of the processes in the waiting queue and place it in the ready queue
typedef struct{
int value;
struct process *list;
} semaphore;

implementation of no busy waiting
wait(semaphore *S) { 
   S->value--; 
   if (S->value < 0) {
      add this process to S->list; 
      block(); 
   } 
}

signal(semaphore *S) { 
   S->value++; 
   if (S->value <= 0) {
      remove a process P from S->list; 
      wakeup(P); 
   } 
}

Question 35

deadlock

Answer 35

Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes
Let S and Q be two semaphores initialized to 1
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
… …
signal(S); signal(Q);
signal(Q); signal(S);

Question 36

starvation

Answer 36

Starvation – indefinite blocking
A process may never be removed from the semaphore queue in which it is suspended
Priority Inversion – Scheduling problem when lower-priority process holds a lock needed by higher-priority process
Solved via priority-inheritance protocol

Question 37

classical problems of synchronization

Answer 37

Classical problems used to test newly-proposed synchronization schemes
Bounded-Buffer Problem
Readers and Writers Problem
Dining-Philosophers Problem

Question 38

bounded-buffer problem of synch

Answer 38

n buffers, each can hold one item
Semaphore mutex initialized to the value 1
Semaphore full initialized to the value 0
Semaphore empty initialized to the value n

The structure of the producer process

     do { 
          ...
        /* produce an item in next_produced */ 
          ... 
        wait(empty); 
        wait(mutex); 
           ...
        /* add next produced to the buffer */ 
           ... 
        signal(mutex); 
        signal(full); 
     } while (true);

he structure of the consumer process

     Do { 
        wait(full); 
        wait(mutex); 
           ...
        /* remove an item from buffer to next_consumed */ 
           ... 
        signal(mutex); 
        signal(empty); 
           ...
        /* consume the item in next consumed */ 
           ...
     } while (true);

Question 39

readers and writers problem

Answer 39

A data set is shared among a number of concurrent processes
Readers – only read the data set; they do not perform any updates
Writers – can both read and write
Problem – allow multiple readers to read at the same time
Only one single writer can access the shared data at the same time
Several variations of how readers and writers are considered – all involve some form of priorities
Shared Data
Data set
Semaphore rw_mutex initialized to 1
Semaphore mutex initialized to 1
Integer read_count initialized to 0

The structure of a writer process

       do {
          wait(rw_mutex); 
               ...
          /* writing is performed */ 
               ... 
          signal(rw_mutex); 
     } while (true);

The structure of a reader process
       do {
        wait(mutex);
        read_count++;
        if (read_count == 1) 
              wait(rw_mutex); 
           signal(mutex); 
           ...
        /* reading is performed */ 
           ... 
           wait(mutex);
        read_count--;
        if (read_count == 0) 
              signal(rw_mutex); 
           signal(mutex); 
       } while (true);

Question 40

the dining philosophers problem

Answer 40

Philosophers spend their lives alternating thinking and eating
Don’t interact with their neighbors, occasionally try to pick up 2 chopsticks (one at a time) to eat from bowl
Need both to eat, then release both when done
In the case of 5 philosophers
Shared data
Bowl of rice (data set)
Semaphore chopstick [5] initialized to 1

The structure of Philosopher i:
do {
wait (chopstick[i] );
wait (chopStick[ (i + 1) % 5] );

             //  eat

  signal (chopstick[i] );
  signal (chopstick[ (i + 1) % 5] );

             //  think

} while (TRUE);
What is the problem with this algorithm?
(deadlock!)

Deadlock handling
Allow at most 4 philosophers to be sitting simultaneously at the table.
Allow a philosopher to pick up the forks only if both are available (picking must be done in a critical section.
Use an asymmetric solution – an odd-numbered philosopher picks up first the left chopstick and then the right chopstick. Even-numbered philosopher picks up first the right chopstick and then the left chopstick.

Question 41

problems with semaphores

Answer 41

Incorrect use of semaphore operations:

signal (mutex) …. wait (mutex)

wait (mutex) … wait (mutex)

Omitting of wait (mutex) or signal (mutex) (or both)

Deadlock and starvation are possible.

Question 42

monitors

Answer 42

A high-level abstraction that provides a convenient and effective mechanism for process synchronization
Abstract data type, internal variables only accessible by code within the procedure
Only one process may be active within the monitor at a time
But not powerful enough to model some synchronization schemes

monitor monitor-name
{
	// shared variable declarations
	procedure P1 (…) { …. }

procedure Pn (…) {……}

    Initialization code (…) { … }
	}
}

condition variables:
condition x, y;
Two operations are allowed on a condition variable:
x.wait() – a process that invokes the operation is suspended until x.signal()
x.signal() – resumes one of processes (if any) that invoked x.wait()
If no x.wait() on the variable, then it has no effect on the variable

condition variables choices:
If process P invokes x.signal(), and process Q is suspended in x.wait(), what should happen next?
Both Q and P cannot execute in paralel. If Q is resumed, then P must wait
Options include
Signal and wait – P waits until Q either leaves the monitor or it waits for another condition
Signal and continue – Q waits until P either leaves the monitor or it waits for another condition
Both have pros and cons – language implementer can decide
Monitors implemented in Concurrent Pascal compromise
P executing signal immediately leaves the monitor, Q is resumed
Implemented in other languages including Mesa, C#, Java

Question 43

monitor solution to dining philosophers

Answer 43

monitor DiningPhilosophers
{
enum { THINKING; HUNGRY, EATING) state [5] ;
condition self [5];

	void pickup (int i) { 
	       state[i] = HUNGRY;
	       test(i);
	       if (state[i] != EATING) self[i].wait;
}

   void putdown (int i) { 
	       state[i] = THINKING;
                   // test left and right neighbors
	        test((i + 4) % 5);
	        test((i + 1) % 5);
}

	void test (int i) { 
	        if ((state[(i + 4) % 5] != EATING) &&
	        (state[i] == HUNGRY) &&
	        (state[(i + 1) % 5] != EATING) ) { 
	             state[i] = EATING ;
		    self[i].signal () ;
	        }
   }

       initialization_code() { 
	       for (int i = 0; i < 5; i++)
	       state[i] = THINKING;
	     }
}

Each philosopher i invokes the operations pickup() and putdown() in the following sequence:

          DiningPhilosophers.pickup(i);

               EAT

          DiningPhilosophers.putdown(i);

No deadlock, but starvation is possible

Question 44

CPU scheduling (short term scheduler and dispatcher)

Answer 44

Maximum CPU utilization obtained with multiprogramming
CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait
CPU burst followed by I/O burst
CPU burst distribution is of main concern

CPU Scheduler
Short-term scheduler selects from among the processes in ready queue, and allocates the CPU to one of them
Queue may be ordered in various ways
CPU scheduling decisions may take place when a process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
Terminates
Scheduling under 1 and 4 is nonpreemptive
All other scheduling is preemptive
Consider access to shared data
Consider preemption while in kernel mode
Consider interrupts occurring during crucial OS activities

dispatcher
Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves:
switching context
switching to user mode
jumping to the proper location in the user program to restart that program
Dispatch latency – time it takes for the dispatcher to stop one process and start another running

Question 45

CPU scheduling criteria

Answer 45

CPU utilization – keep the CPU as busy as possible
Throughput – # of processes that complete their execution per time unit
Turnaround time – amount of time to execute a particular process
Waiting time – amount of time a process has been waiting in the ready queue
Response time – amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)

algorithm optimization critiera
Max CPU utilization
Max throughput
Min turnaround time 
Min waiting time 
Min response time

Question 46

first come first serve scheduling

Answer 46

Process	Burst Time	
		 P1	24
		 P2 	3
		 P3	 3 
Suppose that the processes arrive in the order: P1 , P2 , P3  
The Gantt Chart for the schedule is:

Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17

Suppose that the processes arrive in the order:
P2 , P3 , P1
The Gantt chart for the schedule is:

Waiting time for P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)/3 = 3
Much better than previous case
Convoy effect - short process behind long process
Consider one CPU-bound and many I/O-bound processes

Question 47

shortest job first (SJF) Scheduling

Answer 47

Associate with each process the length of its next CPU burst
Use these lengths to schedule the process with the shortest time
SJF is optimal – gives minimum average waiting time for a given set of processes
The difficulty is knowing the length of the next CPU request
Could ask the user

Question 48

priority scheduling

Answer 48

A priority number (integer) is associated with each process

The CPU is allocated to the process with the highest priority (smallest integer ≡ highest priority)
Preemptive
Nonpreemptive

SJF is priority scheduling where priority is the inverse of predicted next CPU burst time

Problem ≡ Starvation – low priority processes may never execute

Solution ≡ Aging – as time progresses increase the priority of the process

Question 49

round robin scheduling

Answer 49

Each process gets a small unit of CPU time (time quantum q), 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.
Timer interrupts every quantum to schedule next process
Performance
q large ⇒ FIFO
q small ⇒ q must be large with respect to context switch, otherwise overhead is too high

Typically, higher average turnaround than SJF, but better response
q should be large compared to context switch time
q usually 10ms to 100ms, context switch < 10 usec
80% of CPU bursts should be shorter than q

Question 50

multilevel queue

Answer 50

Ready queue is partitioned into separate queues, eg:
foreground (interactive)
background (batch)
Process permanently in a given queue
Each queue has its own scheduling algorithm:
foreground – RR
background – FCFS
Scheduling must be done between the queues:
Fixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of starvation.
Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes; i.e., 80% to foreground in RR
20% to background in FCFS

Question 51

multilevel feedback queue

Answer 51

multilevel feedback queue:
A process can move between the various queues; aging can be implemented this way
Multilevel-feedback-queue scheduler defined by the following parameters:
number of queues
scheduling algorithms for each queue
method used to determine when to upgrade a process
method used to determine when to demote a process
method used to determine which queue a process will enter when that process needs service

ex.
Three queues: 
Q0 – FCFS with time quantum 8 milliseconds
Q1 – FCFS time quantum 16 milliseconds
Q2 – RR

Scheduling
A new job enters queue Q0 which is served FCFS
When it gains CPU, job receives 8 milliseconds
If it does not finish in 8 milliseconds, job is moved to queue Q1
At Q1 job is again served FCFS and receives 16 additional milliseconds
If it still does not complete, it is preempted and moved to queue Q2

Question 52

thread scheduleing

Answer 52

Distinction between user-level and kernel-level threads
When threads supported, threads scheduled, not processes
Many-to-one and many-to-many models, thread library schedules user-level threads to run on LWP
Known as process-contention scope (PCS) since scheduling competition is within the process
Typically done via priority set by programmer
Kernel thread scheduled onto available CPU is system-contention scope (SCS) – competition among all threads in system

Question 53

pthread scheduling methods and API

Answer 53

include

API allows specifying either PCS or SCS during thread creation
PTHREAD_SCOPE_PROCESS schedules threads using PCS scheduling
PTHREAD_SCOPE_SYSTEM schedules threads using SCS scheduling
Can be limited by OS – Linux and Mac OS X only allow PTHREAD_SCOPE_SYSTEM

#include
#define NUM_THREADS 5
int main(int argc, char argv[]) {
int i, scope;
pthread_t tid[NUM THREADS];
pthread_attr_t attr;
/ get the default attributes /
pthread_attr_init(&attr);
/ first inquire on the current scope */
if (pthread_attr_getscope(&attr, &scope) != 0)
fprintf(stderr, “Unable to get scheduling scope\n”);
else {
if (scope == PTHREAD_SCOPE_PROCESS)
printf(“PTHREAD_SCOPE_PROCESS”);
else if (scope == PTHREAD_SCOPE_SYSTEM)
printf(“PTHREAD_SCOPE_SYSTEM”);
else
fprintf(stderr, “Illegal scope value.\n”);
}

/* set the scheduling algorithm to PCS or SCS /
pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
/ create the threads /
for (i = 0; i < NUM_THREADS; i++)
pthread_create(&tid[i],&attr,runner,NULL);
/ now join on each thread /
for (i = 0; i < NUM_THREADS; i++)
pthread_join(tid[i], NULL);
}
/ Each thread will begin control in this function */
void *runner(void param)
{
/ do some work … */
pthread_exit(0);
}

Question 54

multiple processor scheduling

Answer 54

CPU scheduling more complex when multiple CPUs are available
Homogeneous processors within a multiprocessor (same type)
Asymmetric multiprocessing – only one processor accesses the system data structures, alleviating the need for data sharing
Symmetric multiprocessing (SMP) – each processor is self-scheduling, all processes in common ready queue, or each has its own private queue of ready processes
Currently, most common
Processor affinity – process has affinity for processor on which it is currently running
soft affinity
hard affinity
Variations including processor sets

Recent trend to place multiple processor cores on same physical chip
Faster and consumes less power
Multiple threads per core also growing
Takes advantage of memory stall to make progress on another thread while memory retrieve happens

Question 55

multiple processor scheduling- load balancer

Answer 55

If SMP, need to keep all CPUs loaded for efficiency
Load balancing attempts to keep workload evenly distributed
Push migration – periodic task checks load on each processor, and if found pushes task from overloaded CPU to other CPUs
Pull migration – idle processors pulls waiting task from busy processor

Question 56

real-time CPU scheduling

Answer 56

Can present obvious challenges
Soft real-time systems – no guarantee as to when critical real-time process will be scheduled
Hard real-time systems – task must be serviced by its deadline
Two types of latencies affect performance
Interrupt latency – time from arrival of interrupt to start of routine that services interrupt
Dispatch latency – time for schedule to take current process off CPU and switch to another

Question 57

real time scheduling

Answer 57

For real-time scheduling, scheduler must support preemptive, priority-based scheduling
But only guarantees soft real-time
For hard real-time must also provide ability to meet deadlines
Processes have new characteristics: periodic ones require CPU at constant intervals
Has processing time t, deadline d, period p
0 ≤ t ≤ d ≤ p
Rate of periodic task is 1/p

Question 58

virtualization and scheduling

Answer 58

Virtualization software schedules multiple guests onto CPU(s)
Each guest doing its own scheduling
Not knowing it doesn’t own the CPUs
Can result in poor response time
Can effect time-of-day clocks in guests
Can undo good scheduling algorithm efforts of guest

Question 59

rate monotonic scheduling

Answer 59

A priority is assigned based on the inverse of its period

Shorter periods = higher priority;

Longer periods = lower priority

P1 is assigned a higher priority than P2.

Question 60

earliest deadline first (EDF) scheduling

Answer 60

Priorities are assigned according to deadlines:

the earlier the deadline, the higher the priority;
the later the deadline, the lower the priority

Question 61

proportional share scheduling

Answer 61

T shares are allocated among all processes in the system

An application receives N shares where N < T

This ensures each application will receive N / T of the total processor time

Question 62

POSIX realtime scheduling

Answer 62

The POSIX.1b standard
Defines two scheduling classes for real-time threads:
SCHED_FIFO - threads are scheduled using a FCFS strategy with a FIFO queue. There is no time-slicing for threads of equal priority
SCHED_RR - similar to SCHED_FIFO except time-slicing occurs for threads of equal priority
Defines two functions for getting and setting scheduling policy:
pthread_attr_getsched_policy(pthread_attr_t *attr, int *policy)
pthread_attr_setsched_policy(pthread_attr_t *attr, int policy)

API
#include
#include
#define NUM_THREADS 5
int main(int argc, char argv[])
{
int i, policy;
pthread_t_tid[NUM_THREADS];
pthread_attr_t attr;
/ get the default attributes /
pthread_attr_init(&attr);
/ get the current scheduling policy /
if (pthread_attr_getschedpolicy(&attr, &policy) != 0)
fprintf(stderr, “Unable to get policy.\n”);
else {
if (policy == SCHED_OTHER) printf(“SCHED_OTHER\n”);
else if (policy == SCHED_RR) printf(“SCHED_RR\n”);
else if (policy == SCHED_FIFO) printf(“SCHED_FIFO\n”);
/ set the scheduling policy - FIFO, RR, or OTHER /
if (pthread_attr_setschedpolicy(&attr, SCHED_FIFO) != 0)
fprintf(stderr, “Unable to set policy.\n”);
/ create the threads /
for (i = 0; i < NUM_THREADS; i++)
pthread_create(&tid[i],&attr,runner,NULL);
/ now join on each thread */
for (i = 0; i < NUM_THREADS; i++)
pthread_join(tid[i], NULL);
}

/* Each thread will begin control in this function */ 
void *runner(void *param)
{ 
   /* do some work ... */ 
   pthread_exit(0); 
}

Question 63

linux scheduling post 2.6.23

Answer 63

Completely Fair Scheduler (CFS)
Scheduling classes
Each has specific priority
Scheduler picks highest priority task in highest scheduling class
Rather than quantum based on fixed time allotments, based on proportion of CPU time
2 scheduling classes included, others can be added
default
real-time
Quantum calculated based on nice value from -20 to +19
Lower value is higher priority
Calculates target latency – interval of time during which task should run at least once
Target latency can increase if say number of active tasks increases
CFS scheduler maintains per task virtual run time in variable vruntime
Associated with decay factor based on priority of task – lower priority is higher decay rate
Normal default priority yields virtual run time = actual run time
To decide next task to run, scheduler picks task with lowest virtual run time

Question 64

scheduling algorithm evaluation

Answer 64

How to select CPU-scheduling algorithm for an OS?
Determine criteria, then evaluate algorithms
Deterministic modeling
Type of analytic evaluation
Takes a particular predetermined workload and defines the performance of each algorithm for that workload

deterministic evaluation:
For each algorithm, calculate minimum average waiting time
Simple and fast, but requires exact numbers for input, applies only to those inputs

Question 65

queueing models

Answer 65

Describes the arrival of processes, and CPU and I/O bursts probabilistically
Commonly exponential, and described by mean
Computes average throughput, utilization, waiting time, etc
Computer system described as network of servers, each with queue of waiting processes
Knowing arrival rates and service rates
Computes utilization, average queue length, average wait time, etc

Question 66

Little’s Formula

Answer 66

n = average queue length
W = average waiting time in queue
λ = average arrival rate into queue
Little’s law – in steady state, processes leaving queue must equal processes arriving, thus:
n = λ x W
Valid for any scheduling algorithm and arrival distribution
For example, if on average 7 processes arrive per second, and normally 14 processes in queue, then average wait time per process = 2 second

Question 67

Simulations

Answer 67

Queueing models limited
Simulations more accurate
Programmed model of computer system
Clock is a variable
Gather statistics indicating algorithm performance
Data to drive simulation gathered via
Random number generator according to probabilities
Distributions defined mathematically or empirically
Trace tapes record sequences of real events in real systems

Implementation:
Even simulations have limited accuracy
Just implement new scheduler and test in real systems
High cost, high risk
Environments vary
Most flexible schedulers can be modified per-site or per-system
Or APIs to modify priorities
But again environments vary

Question 68

system model (for deadlock)

Answer 68

System consists of resources
Resource types R1, R2, . . ., Rm
CPU cycles, memory space, I/O devices
Each resource type Ri has Wi instances.
Each process utilizes a resource as follows:
request 
use 
release

Question 69

deadlock charactization

Answer 69

Deadlock can arise if four conditions hold simultaneously.

Mutual exclusion: only one process at a time can use a resource
Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes
No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task
Circular wait: there exists a set {P0, P1, …, Pn} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.

Question 70

Resource allocation graph

Answer 70

A set of vertices V and a set of edges E.
V is partitioned into two types:
P = {P1, P2, …, Pn}, the set consisting of all the processes in the system

R = {R1, R2, …, Rm}, the set consisting of all resource types in the system

request edge – directed edge Pi → Rj

assignment edge – directed edge Rj → Pi

If graph contains no cycles ⇒ no deadlock
If graph contains a cycle ⇒
if only one instance per resource type, then deadlock
if several instances per resource type, possibility of deadlock

Question 71

methods for handling deadlocks

Answer 71

Ensure that the system will never enter a deadlock state:
Deadlock prevention:
Mutual Exclusion – not required for sharable resources (e.g., read-only files); must hold for non-sharable resources
Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold any other resources
Require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none allocated to it.
Low resource utilization; starvation possible
No Preemption –
If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released
Preempted resources are added to the list of resources for which the process is waiting
Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting
Circular Wait – impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration

Deadlock avoidance:

Allow the system to enter a deadlock state and then recover
Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX