Schemaläggningsalgoritmer

Question 1

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.

Answer 1

First In, First Out (FIFO)

Question 2

If jobs come it at the same time it is the most optimal scheduling algorithm for turnaround time. It is non preemptive.

Answer 2

Shortest Job First (SJF)

Question 3

If a new job arrives this scheduler determines which of the remaining jobs has the least time left and completes that one first.

Answer 3

Shortest Time To Completion First (STCF)

Question 4

Problems with SJF

Answer 4

It is non-preemptive so a convoy effect can happen where short jobs can be scheduled behind longer jobs. Jobs run to completion.

Question 5

What is turnaround time?

Answer 5

Time of completion - Time of arrival. It is a performance metric.

Question 6

What is response time?

Answer 6

Time of first run - Time of arrial. How long it takes for a new job to run.

Question 7

Name three perfomance metrics

Answer 7

Turnaround time, Fairness, Response time

Question 8

What is a preemptive scheduler, name an example?

Answer 8

A preemptive scheduler can perform a context switch, stopping one running process temporarily and resuming another. Shortest time to completion first.

Question 9

What is a non-preemptive scheduler, name an example?

Answer 9

Each job will run to completion before considering if to run a new job. Shortest job first.

Question 10

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?

Answer 10

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.

Question 11

What is amortization? When it is commonly used?

Answer 11

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.

Question 12

Name a couple of fair schedulers?

Answer 12

Round robin,

Question 13

How to maximize the utilization of systems when performing disk I/O.

Answer 13

Overlap. Letting another job run while the issuing job waits for I/O to complete

Question 14

What happens to a job when it issues a I/O request?

Answer 14

It gets blocked

Question 15

What happens when a I/O request completes?

Answer 15

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.

Question 16

Problems MLFQ tries to solve.

Answer 16

Optimize turnaround time and minimize response time while not knowing how long it will take for a job to complete.

Question 17

How does the MLFQ work?

Answer 17

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.

Question 18

Where is a job with higher priority placed on which type of queue, higher or lower?

Answer 18

Higher

Question 19

How does MLFQ decide which job to run with the same priority?

Answer 19

Run the jobs in a round robin fashion.

Question 20

Which jobs does MLFQ treats as higher priority?

Answer 20

Responsive jobs, which issues many I/O.

Question 21

How does MLFQ change priority and approximates SJF?

Answer 21

If a job runs it entire timeslice it priority will be lowered. Jobs first entering have high priority. A move down the queues.

Question 22

How does MLFQ deal with starvation?

Answer 22

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.

Question 23

How does MLFQ deal with gameing?

Answer 23

Scheduler keep track once a process has used its allotment, it is demoted to the next priority queue.

Question 24

What is gameing?

Answer 24

A job relinquishing the CPU right before the time slices expires.

Question 25

How does MLFQ very time-slice length across the queues?

Answer 25

High priority queues are given short time slices, low priority queues have longer time slices.

Question 26

State the 5 rules of MLFQ

Answer 26

Rule 1: If priority(A) > Priority(B), A runs
Rule 2: If priority(A) = Priority(B), A & B run in RR
Rule 3: When a job enters the system, it is placed at the highest priority, top most queue.
Rule 4: Once a job uses up its time alotment its priority level is decease.
Rule 5: After time S, move all the jobs in the system to the topmost queue.

Question 27

How does the lottery scheduling work?

Answer 27

A process gets a percantage of the total tickets. The schedular know how many total tickets there are, the scheduler then picks a random winning ticket. It is probalistic.

Question 28

When do we want to use a lottery scheduling algorithm?

Answer 28

When we want each process to run at the CPU a percantage of time.

Question 29

When a process temporarily hand off its tickets to another process.

Answer 29

Ticket transfer

Question 30

A process can temporarily raise or lower the number of tickets it owns.

Answer 30

Ticket inflation.

Question 31

When doesnt ticket inflation make sense?

Answer 31

When the processes does not trust eachother.

Question 32

Advantages of lottery scheduling:

Answer 32

Simplicity of its implementation, no global state.

Question 33

How do we make two jobs finnish at the same time using lottery scheduling?

Answer 33

We use unfairness metric.

Question 34

Metric of which is simple the time the first job completes divided by the time that the second job completes.

Answer 34

Unfairness metric, U.

Question 35

Name a deterministic fair-share scheduler

Answer 35

Stride scheduling

Question 36

Explain stride scheduling

Answer 36

Every process has a stride length (highnumber / tickets). And it has a counter to track its global progress (pass value). Scheduler then uses the stride and pss to determine which process should run next. The scheduler will pick the process with the lowest passvalue to run.