cse4600 Exam 2 Flashcards
What does PF stand for and what does it do?
Priority Function; The decision for which process will be allowed to execute
What does AR stand for and what does it do?
Arbitration Function; When two processes with equal priority are too be scheduled
What does DM stand for and what does it do?
Dynamic priority Measures; Parameters that change over time
Name some system measures that may determine priority level
external priority total service time deadline real-time in the system memory requirements
What is turnaround time
Total time between the submission of the process for execution and the return of the complete output
What is waiting time
amount of time a job is sitting ideal before the process is used
First in First out - Pros and Cons
Pro - Easy to implement - Ignores service time Cons - Not a great performer
First in First out PF
P = r, where r is the amount of real time
First in First out DM
Non - Preemptive
First in First out AR
random choice among processes arriving at exactly the same time
Shortest Job First PF
P = -t, where t is the total service time
Shortest Job First DM
Non - Preemptive
Shortest Job First AR
either chronological or random among processes with same service time
Shortest Remaining Time PF
P = - (t - a), where t-a is the remaining time
Shortest Remaining Time DM
Preemptive
Shortest Remaining Time AR
chronological or random among processes with same service time
Round Robin PF
P = 0, all processes have the same priority
Round Robin DM
preemptive quantum oriented
Round Robin AR
cyclic
Multilevel Priority PF
P = e
Multilevel Priority DM
preemptive if newly arriving process has a higher priority
within each priority queue, scheduling may be preemptive RR or non-preemptive FIFO
Multilevel Priority AR
cyclic if RR, random/chronological if FIFO
Multilevel Feedback PF
function of attained service time with different implementations possible
Multilevel Feedback DM
preemptive or non-preemptive; processes in the same level may use RR or FIFO
Multilevel Feedback AR
cyclic or random/chronological
Rate Monotonic PF
P = -d, where d is a fixed period of time that process needs to use the cpu
Rate Monotonic DM
preemptive
Rate Monotonic AR
random or chronological
Earliest Deadline First PF
P = -(d-r%d), where
r is the time since process first entered the system
d is its period
Earliest Deadline First DM
preemptive and dynamic
Earliest Deadline First AR
random or chronological
What is a time quantum
amount of timeshare (timeslice) given to each process, interrupting the job if it is not completed by then
What is throughput
the number of processes that are completed per time unit
What is response time
the time it takes to start responding, from the submission of the request until the first response is produced
What is turnaround time
from the time of submission of a process to the time of completion
What is waiting time
the sum of the periods spent waiting in the ready queue
What is burst time
the amount of time the process uses the processor before it is no longer ready
What is priority inversion
when a low priority process blocks a high priority process from executing because the low priority process is being preempted by a medium process
Shortest Job First - Pro
provably optimal, results in minimum average waiting time
Round Robin - Pro and Con
Pro
- better response than SJF
Con
- higher average turnaround
What is the equation for schedulability
n ( 2^1/n - 1 )
Primary use for Earliest Deadline First?
For real-time systems
When is a schedule feasible?
When all deadlines are satisfied
What is a method optimal?
If it always produces a feasible schedule if one exists
Rate Monotonic - Pros
- Simpler implementation
- Predicability for the highest priority
Earliest Deadline First - Pros
- Full processor utilizaiton
- Misbehavior during overload conditions
For Eventcount, what does await(E, v) do?
suspends the calling process if E < v; otherwise it allows the process to proceed
For Eventcount, what does advance(E) do?
eventcount value E is incremented and next process is admitted for service
For Eventcount, what does read(E) do?
inspects the current value of E
What does a monitors condition variable wait() do?
causes the executing process to be suspended on the queue
What does a monitors condition variable signal() do?
wakes up a process thats waiting on CV
What does a monitors condition variable queue() do?
true if queue is not empty, false if no process is waiting in the queue
For Mesa Semantics the thread that signals
keeps the lock
For Mesa Semantics the waiting thread
waits for the lock
For Hoare Semantics the thread that signals
gives up the lock and the waiting thread gets the lock
T/F: Hoare uses if rather than while
True
T/F: Mesa uses if rather than while
False
T/F: Monitors provide mutual exclusion between all procedures between shared data
True
For a producer/consumer problem why is
P(mutex)
P(full)
incorrect?
Because it will set Full variable and mutex variable to -1 and both Producer and Consumer will wait
What is a weak reader
an arriving writer waits until there are no more active readers
What is a strong reader
waiting reader has priority over a waiting writer
What is writer priority?
an arriving reader waits until there are no more active or waiting writers
Counting semaphores are used
to manage limited resources and corresponding access to them
Binary semaphores are usually used
to facilitate mutual exclusion
P(s) =
wait(s) = down(s)
V(s) =
signal(s) = up(s)
