Schemaläggningsalgoritmer Flashcards
Simple to implement, if jobs come in at a certain order it can create a convoy effect. Jobs get completed one at a time in the order they were scheduled by the time of arrival.
First In, First Out (FIFO)
If jobs come it at the same time it is the most optimal scheduling algorithm for turnaround time. It is non preemptive.
Shortest Job First (SJF)
If a new job arrives this scheduler determines which of the remaining jobs has the least time left and completes that one first.
Shortest Time To Completion First (STCF)
Problems with SJF
It is non-preemptive so a convoy effect can happen where short jobs can be scheduled behind longer jobs. Jobs run to completion.
What is turnaround time?
Time of completion - Time of arrival. It is a performance metric.
What is response time?
Time of first run - Time of arrial. How long it takes for a new job to run.
Name three perfomance metrics
Turnaround time, Fairness, Response time
What is a preemptive scheduler, name an example?
A preemptive scheduler can perform a context switch, stopping one running process temporarily and resuming another. Shortest time to completion first.
What is a non-preemptive scheduler, name an example?
Each job will run to completion before considering if to run a new job. Shortest job first.
Which type of scheduler algorithm is good for response time but horrible for turnaround time? Use terms as time slice. How long should a timeslice be?
Round robin. Is a cyclic scheduling algorithm which gives each process a timeslice. Which means a time to run on the CPU and then lets each process run its timeslice in a cyclic manner. It is fair becuase we avoid starvation.
What is amortization? When it is commonly used?
Used in systems when there is a fixed cost to some operation. Amortization is the process of making that cost occour less often, reduce the total cost of the system.
Name a couple of fair schedulers?
Round robin,
How to maximize the utilization of systems when performing disk I/O.
Overlap. Letting another job run while the issuing job waits for I/O to complete
What happens to a job when it issues a I/O request?
It gets blocked
What happens when a I/O request completes?
An interupt is raised and the OS runs and moves the process which issued the I/O from blocked to ready state. It could event decide to run the job at that point.
Problems MLFQ tries to solve.
Optimize turnaround time and minimize response time while not knowing how long it will take for a job to complete.
How does the MLFQ work?
MLFQ has a number of distinct queues, each assigned a different priority level. At a given time, a job ithat is ready to run is on a single queue. MLFQ uses priorities to decide which job should run on a given time.
Where is a job with higher priority placed on which type of queue, higher or lower?
Higher
How does MLFQ decide which job to run with the same priority?
Run the jobs in a round robin fashion.
Which jobs does MLFQ treats as higher priority?
Responsive jobs, which issues many I/O.
How does MLFQ change priority and approximates SJF?
If a job runs it entire timeslice it priority will be lowered. Jobs first entering have high priority. A move down the queues.
How does MLFQ deal with starvation?
If there are many jobs with high interactivity the lower priority longer jobs will starve. Priority boost to boost all of the jobs in the system, increasing their priority.
How does MLFQ deal with gameing?
Scheduler keep track once a process has used its allotment, it is demoted to the next priority queue.
What is gameing?
A job relinquishing the CPU right before the time slices expires.
