Process Scheduling

Question 1

Processor manager

Answer 1

Uses one or more scheduling algorithms to dispatch processes.

Question 2

Non-preemptive scheduling

Answer 2

Process stays on the CPU until it terminates or blocks for I/O, implements multiprogramming.

Question 3

Preemptive scheduling

Answer 3

Implements multitasking and can be interrupted and replaced with another process.

Question 4

Processor Manager Objectives

Answer 4

Maximise throughput
Minimise turnaround time
Minimise waiting time
Maximise CPU efficiency
Minimise latency
Its not possible to have all of these criteria fulfilled at once as they clash with one another, therefore the processor manager tries to ensure fairness.

Question 5

Burst Time

Answer 5

Time a process takes on the CPU before it blocks or terminates.

Question 6

Arrival Time

Answer 6

Time a process is first put into the ready state.

Question 7

First Come First Served

Answer 7

Deals with processes according to their arrival time.
Uses a FIFO order to store ready processes.
When a new process is added, its PCD is added to the back of the ready queue.

Question 8

FCFS Average Wait Time

Answer 8

The time can change if the biggest one is last, as the biggest time is not considered as part of the equation.

Question 9

FCFS Advantages and Disadvantages

Answer 9

Advantages:
- Very simply implementation.
- Scheduling overhead is minimal during content switch, since you just get the next one in the ready queue that the pointer points to.
- No starvation of processes, which means they will run eventually.
Disadvantages:
- Throughput can be low due to long processes staying on CPU.
- Average wait time is not minimal.
- Turnaround time and latency are therefore hard to predict.
- No ability to prioritise processes.
If bigger processes went last, speed would increase.

Question 10

Shortest Job First

Answer 10

When the CPU becomes free, the scheduler will choose the process with the shortest burst time. If two are the same, we just choose by arrival time. Similar to FCFS, it stays there until terminated.

Question 11

SJF Average Wait Time

Answer 11

The average wait time will be shorter than FCFS, because it does the minimal one first.

Question 12

SJF Advantages and Disadvantages

Answer 12

Advantages:
- Reduces overall average wait time.
- Probably optimal in giving AWT for given (average wait time) processes.
Disadvantages:
- Can lead to process starvation, could lead to starving the OS.
- Difficult to estimate burst times for new processes, since it relies on prior history.

Question 13

Shortest Remaining Time First

Answer 13

Instead of looking at burst time, it simply just looks at how long it has left to process. So whatever is on the CPU can be taken off before it finishes, and whatever has a shorter remaining time until it terminates or it is blocked. This is very hard to calculate, and therefore it is hard to draw a Gaant chart for.

Question 14

SRTF Advantages and Disadvantages

Answer 14

Advantages:
- Short processes are handled very quickly.
- Gives maximum throughput in most situations.
- Requires little overhead during context switch.
Disadvantages:
- Starvation is still possible.
- Introduces extra context switches.
- Waiting time can increase for longer processes.

Question 15

Throughput

Answer 15

-> get through x amount of processes in y amount of time.

Question 16

Minimise Turnaround Time

Answer 16

-> minimise time taken for processes to complete.

Question 17

Minimise waiting time

Answer 17

-> reduce time processes spend in ready state.

Question 18

Maximise CPU efficiency

Answer 18

-> keep CPU constantly busy.

Question 19

Minimise latency

Answer 19

-> reduce time taken between request and response.

Question 20

Priority Scheduling

Answer 20

A preemptive algorithm that gives preferential treatment to important processes; each process has priority assigned to it, with the highest priority getting onto the CPU first.
Equal priority just uses FCFS, and if a new process arrives with a higher priority arrives than the current priority, it interrupts it and places itself on the CPU.
Priorities can depend on things like memory usage, I/O throughput, total CPU time and time already elapsed.

Question 21

Priority Scheduling Average Wait Time

Answer 21

Add up priorities in terms of their wait time (ms).

Question 22

Priority Scheduling Advantages

Answer 22

• Smaller wait time and latency for higher priority.
• Important priorities are dealt with quickly.

Question 23

Priority Scheduling Disadvantages

Answer 23

• Bigger wait times and latency for lower priority.
• Starvation is possible.

Question 24

Round Robin Scheduling

Answer 24

Preemptive, and uses time slice (quantum; typically between 10ms and 100ms) to give a set amount of CPU time to each process.
Similar to FCFS but can be interrupted before they terminate or block.
The ready state is similar to a circular FIFO queue:
- New processes arrive back of queue.
- Scheduler takes next process from front.
- Process runs for set amount of time.
- Context switch moves current process to back of queue and dispatches next in line.
- This repeats.
If the burst time is less than the quantum time, the process will terminate or block for I/O, and will immediately take next process from queue and place on CPU. If quantum time < burst time, it will be interrupted and context switch will happen (preempted).
If quantum is too big, similar to FCFS.
If quantum is too small, similar to SJF.

Question 25

Round Robin Turnaround and Wait Time

Answer 25

To calculate AWT, we use turnaround time and wait time.

Turnaround -> time when it was terminated - when it arrived
Equations = wait time + burst time
or
Completion time - arrival time

Wait -> turnaround - burst.

Question 26

Round Robin Advantages

Answer 26

• Easy to implement as queue.
• No guessing times.
• Response time based upon number of processes, not burst time.
• No starvation
• Balanced throughput

Question 27

Round Robin Disadvantages

Answer 27

• Depends on selecting good quantum times
• Extensive overhead if quantum is too short.