Week 3 and 4

Question 1

What is “Test And Set - Bounded Wait”?

Answer 1

• pass the key approach
• whenexiting the critical section, don’t release the lock, pass the lock to someone who is already waiting
• pass the lock in increasing process id order (with wrap around)
• only one process leaves critical section and gets back to entry point before a context switch, must wait for all other processes that are waiting
• if wiating, each other process can only execute critical section once `

Question 2

Def: Semaphore

Answer 2

Prevents multiple processes entering their critical sections at the same time. - a variable or abstract data type used to control access to a common resource by multiple processes in a concurrent system. - they bracket critical sections

Question 3

Def: mutex

Answer 3

a program object that is created so that multiple program threads can take turns sharing the same resource, such as access to a file

Question 4

What is the critical region?

Answer 4

a high level language construct that implements a critical section

Question 5

Def: Monitors

Answer 5

High level synchronization construct - allows safe sharing of an abstract data type
- prioritized waiting

Question 6

When a process executes x.signal() and another process is waiting on condition X, what happens?

Answer 6

Several case

• first process (signaller) goes to sleep until second process exits (releases lock) or waits on another condition
• first process continues until it leaves or waits on a condition and then signalled process continues

Question 7

What are the two meanings of wait and signal? (semaphores vs monitor condition)

Answer 7

Semaphores (integer cariable, user visable value influences operation) - wait in a semaphore may go right through (value > 0)

Monitor Condition (Queue variable, no user visible value) - wait in a monitor always means stop

Question 8

What are Java synchronized methods vs java synchronized blocks?

Answer 8

methods - similar to monitors

blocks - similar to critical regions

Question 9

What is the goal of scheduling?

Answer 9

Maximum CPU utilization (gives CPU to another process while other is waiting I/O)

Question 10

When does the CPU select processes from ready queue and allocates to CPU?

Answer 10

1. Processes goes to wait state (I/O, event wait, etc.) (nonpreemptive)
2. Process is interrupted
3. Process goes from wait to ready
4. Process terminates (nonpreemptive)

Question 11

What is the Dispatcher?

Answer 11

The part of the scheduler responsible for performing the context switch and resuming the process

Question 12

What is Dispatch Latency?

Answer 12

Time for dispatcher to run

Question 13

What are the 5 Scheduling criteria?

Answer 13

1. CPU utilization (keep CPU as busy as possible)
2. Throughput (# of jobs done per time unit)
3. Turnaround Time (Time of submission to Time of completion)
4. Waiting Time (amount of time in ready queue)
5. Response time (submit time to time of first output request)

Question 14

What is the convoy effect?

Answer 14

All I/O jobs end up behind CPU jobs which hog the CPU

Question 15

What is non-preemptive scheduling?

Answer 15

When a task runs until it stops (voluntarily or it finishes)

Question 16

What is preemptive scheduling?

Answer 16

task can be forcibly suspended by CPU interrupt

Question 17

What is the one problem with SJR?

Answer 17

How do you know how long the next burst will be?

Question 18

What is priority scheduling? problem?

Answer 18

Ready queue is sorted based on priority and CPU goes to process with highest priority

prob: processes change behavior over time - how do you assign priority?

Question 19

What is quantum?

Answer 19

maximum time process gets to run

Question 20

How long should the quantum be?

Answer 20

The quantum should be 80% the time it takes a process in the CPU

Question 21

In round robin scheduling with a quanta of 1/10 second is it possible that more than 10 processes can execute a burst in a given second? why?

Answer 21

yes, just because quanta is 1/10 seconds doesn’t mean CPU has to take 1/10 of a second

Question 22

What is Deadlock?

Answer 22

Set of process’s each holding a resource that another process in the set needs

Question 23

What are the 4 conditions of deadlock?

Answer 23

1. mutual exclusion - only limited number (usually one) process at a time can use a resource
2. hold and wait - a process has (at least) one resource and is waiting for another
3. no preemption - we can’t take a resource away from a process
4. circular wait - P0 waits for a resource held by P1….

Question 24

What can we do about deadlock?

Answer 24

prevention - ensure one of the 4 conditions never happens
Avoidance - extra information before allocating an available resource
Recovery - enter deadlock state and recover
Ignore - hope it never happens, handle it manually

Question 25

How can you prevent Deadlock?

Answer 25

a. Mutual exclusion – create a spooler device (for things like printers if there shared)
b. Hold and wait – have to reserve all the resources you need at once (allocate all resources you want at the same time or give up resources before you can get more)
c. Circular wat – always request the resources in the same order
d. Pre-emption – processes have to have rollback points to a previous stage in its computation before it has those resources

Question 26

What is resource allocation state?

Answer 26

number of available and allocated resources and the a priori known maximum resources

Question 27

What is safe state?

Answer 27

System is safe if there is some order we can allocate the resources and not produce a deadlock

Question 28

What is resource preemption?

Answer 28

Take away resources from other processes - process must be rolled back

Question 29

What are the three criteria for a critical section?

Answer 29

1. Mutual Exclusion: only one process in critical section at a time
2. Bounded waiting: once a process is waiting, the other processes can only enter and leave a bounded number of times (no starvation)
3. Progress: If there is no process in a critical section, and more than one process wants to enter their critical section, then the selection of a process cannot be postponed indefinitely