Week 3 and 4 Flashcards
What is “Test And Set - Bounded Wait”?
- 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 `
Def: Semaphore
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
Def: mutex
a program object that is created so that multiple program threads can take turns sharing the same resource, such as access to a file
What is the critical region?
a high level language construct that implements a critical section
Def: Monitors
High level synchronization construct - allows safe sharing of an abstract data type
- prioritized waiting
When a process executes x.signal() and another process is waiting on condition X, what happens?
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
What are the two meanings of wait and signal? (semaphores vs monitor condition)
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
What are Java synchronized methods vs java synchronized blocks?
methods - similar to monitors
blocks - similar to critical regions
What is the goal of scheduling?
Maximum CPU utilization (gives CPU to another process while other is waiting I/O)
When does the CPU select processes from ready queue and allocates to CPU?
- Processes goes to wait state (I/O, event wait, etc.) (nonpreemptive)
- Process is interrupted
- Process goes from wait to ready
- Process terminates (nonpreemptive)
What is the Dispatcher?
The part of the scheduler responsible for performing the context switch and resuming the process
What is Dispatch Latency?
Time for dispatcher to run
What are the 5 Scheduling criteria?
- CPU utilization (keep CPU as busy as possible)
- Throughput (# of jobs done per time unit)
- Turnaround Time (Time of submission to Time of completion)
- Waiting Time (amount of time in ready queue)
- Response time (submit time to time of first output request)
What is the convoy effect?
All I/O jobs end up behind CPU jobs which hog the CPU
What is non-preemptive scheduling?
When a task runs until it stops (voluntarily or it finishes)
What is preemptive scheduling?
task can be forcibly suspended by CPU interrupt
What is the one problem with SJR?
How do you know how long the next burst will be?
What is priority scheduling? problem?
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?
What is quantum?
maximum time process gets to run
How long should the quantum be?
The quantum should be 80% the time it takes a process in the CPU
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?
yes, just because quanta is 1/10 seconds doesn’t mean CPU has to take 1/10 of a second
What is Deadlock?
Set of process’s each holding a resource that another process in the set needs
What are the 4 conditions of deadlock?
- mutual exclusion - only limited number (usually one) process at a time can use a resource
- hold and wait - a process has (at least) one resource and is waiting for another
- no preemption - we can’t take a resource away from a process
- circular wait - P0 waits for a resource held by P1….
What can we do about deadlock?
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
How can you prevent Deadlock?
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
What is resource allocation state?
number of available and allocated resources and the a priori known maximum resources
What is safe state?
System is safe if there is some order we can allocate the resources and not produce a deadlock
What is resource preemption?
Take away resources from other processes - process must be rolled back
What are the three criteria for a critical section?
- Mutual Exclusion: only one process in critical section at a time
- Bounded waiting: once a process is waiting, the other processes can only enter and leave a bounded number of times (no starvation)
- 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
