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

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 #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