Week 5 Flashcards
What questions do scheduling have to deal with.
Which process should run?
How long should it run?
How do we allocate memory?
Should one process get more memory than another?
What is the workload in the scheduling process?
The workload is the set of processes running on the system.
How is effectiveness is scheduling measured?
It can mean both performance as measured by turn around time, and fairness as measured by Jain’s fairness index.
What is FIFO? What are the pros? What are cons?
The first in first out policy states that the first jo to arrive is the first job to run.
Pros: simple to implement.
Cons: Suffers from the convoy effect, wherein short running jobs get stuck behind a single long running job.
What is the equation for turnaround time?
Turnaround = Tcompletion - Tarrival
What is the policy of shortest job first? What are some pros? What are some cons?
The shortest job first policy dictates that the job with the shortest duration should run next.
Pros: assuming that all jobs arrive at the same time, solves the convey efffect problem from the previous example.
Cons: If the jobs don’t arrive at the same time, the convoy effect is still an issue.
What is a preemptive scheduler?
A scheduler is preemptive if it can stop one process to run a different process.
We can leverage context switching mechanisms.
How does the OS regain control from a process?
Use a cooperative approach: wat for a process to voluntarily give up control.
Use a non cooperative approach: set a hardware timer interrupt that will regularly give control back to the OS.
What is the shortest time to completion (STCF) policy? What are pros, and what are cons?
It is similar to SJF but incorporates preemption.
STCF says that the job that has the least amount of time remaining should be scheduled, preempting any runnning jobs.
Pros: The convoy effect is no longer an issue.
Cons: We don’t always know how long a job will take. Also not great for response time.
What is the equation for response time?
Tresponse = Tfirstrun - Tarrival
What is the round robin policy? What are some pros and cons.
The RR policy requires that each job be run for a fixed duration of time before switching to the next job.
The amount of time each job runs is called a time slice.
Pros: Good for workloads where response time is important. It is fair, meaning that all jobs receive a proportional share of execution time.
Cons: Context switching has overhead. The smaller the time slice, the more time that is spent context switching and the less spent on job execution.
What are Multi-level feedback queues?
The MLFQ places jobs into queues and each queue is assigned a priority level.
Short running jobs will have a higher priority than the long running CPU jobs.
We will observe how much its time slice a job uses to estimate the job type.
What are the pros of a multilevel feedback queue? What are some cons?
Pros: Good for mixed workloads.
Cons: What if the job’s behaviour changes over time? What if the system has alot of short running jobs and one long job.
(The solution to this is priortity boost).
What is the basic idea behind the proportional share scheduler? What is an example of a proportional share scheduler?
Instead of optimizing for turnaround time or response time, a proportional share scheduler attempts to give every job a fair share of resources.
An example of a proportional share scheulder is lottery scheduling.
What is lottery scheduling?
Is a type of proportional share scheduling where the scheduler assigns lottery tickets to jobs and a job is scheduled when it wins the lottery.
The more tickets a job has, the more chances it has to win.
