Scheduling

Question 1

What is CPU scheduling?

Answer 1

Determine which process to run next

Question 3

Types of Scheduling

Answer 3

• Short Term Scheduling
• Medium Term Scheduling
• Long Term Scheduling

Question 4

What is short term scheduling?

Answer 4

== dispatcher
* Determine which process to execute next
* Invoked after
– clock interrupt
– system calls and traps to kernel
– signals

Question 5

What is medium term scheduling?

Answer 5

• Swapping decisions
• Memory management unit in kernel

Question 6

What is long term scheduling?

Answer 6

• Determine which programs are admitted
• Control degree of multiprogramming
• If more processes are admitted
  – Less likely that all are blocked
  – Each process has a smaller fraction of the CPU
• Could mix CPU bound and I/O bound

Question 7

When does CPU scheduling happen?

Answer 7

when processes:
1.switches from running to waiting state
2.switches from running to ready state
3.switches from waiting to ready
4.terminates

• These are non-preemptive any other time is preemptive (interrupt)

Question 8

Types of CPU scheduler

Answer 8

• Long-term scheduler (or job scheduler)
• Short-term scheduler (or CPU scheduler)

Question 9

What does a long-term scheduler do?

Answer 9

Selects which processes should be brought into the ready
queue

Question 12

What are CPU scheduling algorithims based on?

Answer 12

• CPU Utilization
• Throughput
• Turnaround Time
• Waiting Time
• Response Time

Question 13

What is CPU utilization when it comes to CPU scheduling criteria?

Answer 13

Need to keep the CPU as busy as
possible ranging from 0 to 100%. In real systems it should
range from 40% (lightly loaded) to 90% (heavily used) system

Question 14

What is throughput when it comes to CPU scheduling criteria?

Answer 14

Measure of the number of processes completed per unit time. E.g. a long processes this rate may be 1 process per hour, for short transactions can be 10 processes per second

Question 15

What is turnaround time when it comes to CPU scheduling criteria?

Answer 15

This is the sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU and doing the IO

Question 16

What is waiting time when it comes to CPU scheduling criteria?

Answer 16

This is the total time a process waits in the ready queue

Question 17

What is response time when it comes to CPU scheduling criteria?

Answer 17

Time from the submission of a request until the 1st response is produced, but not the time taken to output that response

Question 18

List Short Term Scheduling Algorithms

Answer 18

• First Come, First Served (FCFS)
• Round Robin (RR)
• Shortest Process Next (SPN)
• Pre-emptive Shortest Process Next (PSPN)
• Highest Response Ratio Next (HRRN)
• Multiple-Level Feedback (FB)
• Selfish Round Robin (SRR)

Question 19

Define Response Time (T)

Answer 19

This is a measure from the time a process arrives till it completes, so all the waiting time is included

Question 20

Define Response Time when it is measured

Answer 20

T: time that process p is present;
finish time – start time

Question 21

Define Wasted Time (W)

Answer 21

waiting time,
(completion time – arrival time) – processor run time

Question 22

Define Wasted Time when it is measured

Answer 22

W: Response Time (T) – time for execution (t)

Question 23

Define Penalty Ratio (P)

Answer 23

Is the inverse of response ratio so a penalty ratio of 1 is perfect which subsequently rises upwards

Question 24

Define Penalty Ratio when it is measured

Answer 24

P: Response Time (T)/time for execution (t)

Question 25

Define Response Ratio (R)

Answer 25

Represents the fraction of the time that the process is receiving service e.g. if the response ratio R is 1 then the process never sits in the ready queue I.e. its always in the running state.

Question 26

Define Response Ratio when it is measured

Answer 26

R: time for execution (t)/Response Time (T)

Question 27

What is First Come, First Served (FCFS)?

Answer 27

The process that have been waiting the longest will be served 1st. This is a non pre-emptive method.

Question 28

What are the drawbacks to First Come, First Served (FCFS)?

Answer 28

The processes that don't performing I/O will monopolise the CPU This algorithim favours CPU bound processes so: * I/O bound have to wait until CPU bound completes * May wait after I/O completed (poor device utilisation) * Could give priority to I/O bound processes

Question 29

What is Round Robin (RR)?

Answer 29

A scheduling algorithim that tries to provide good response ratios for both short and long processes, it also sets q (quantum) so that the CPU is fairly shared and there is not to much swapping

Question 30

How long does a process last when using the round robin algorithim?

Answer 30

The round robin policy services a process only for a single quantum q of time Typical values of q range between 1/60 and 1 second.

Question 31

What happens in a round robin if a process is interrupted?

Answer 31

If a new process hasn’t finished within its quantum it is interrupted at the end of the quantum and placed at the end of the of the wait queue and wait for its turn to run for another quantum, this continues until the process completes

Question 32

Why do we define q in round robin?

Answer 32

We define q ( no. of execution units) so that once a process finishes its allotted q time then its placed at the back of the queue New processes are placed at the back of the queue and the process at the front of the queue is executed next

Question 33

What is Shortest Process Next (SPN)?

Answer 33

An algorithim that requires explicit information on the service time required for each process It simply selects from the ready list the process with the shortest service time to run next This as a result will favour processes with a short service time This is a non pre-emptive method

Question 34

What is Preemptive Shortest Process Next (PSPN)?

Answer 34

When the current process is swapped when another process arrives with a total service time less than the remaining service time of the running process

Question 35

What is Highest Response Ratio Next (HRRN)?

Answer 35

Where w = time spent on system so far, waiting and executing s = total service time is required by the process including the time spent executing This a non-preemptive method

Question 36

What is the equation used for each process in Highest Response Ratio Next (HRRN)?

Answer 36

max((w+s)/s)

Question 37

What is the problem with Highest Response Ratio Next (HRRN)?

Answer 37

The overhead can be high as we need to calculate for each process on the queue the selection function

Question 38

What is Multiple Level Feedback (FB)?

Answer 38

This method splits the ready list into a number of queues: queue 0, queue 1, queue 2 and so on Where the lower numbered queues have the highest priority hen the current process is interrupted at the end of its quanta A new process is selected from the front of the lowest numbered queue

Question 39

What is Selfish Round Robin (SRR)?

Answer 39

A method that gives beter service to processes that have been executing for a while Processes in the ready list are split into two lists new and accepted New processes wait while accepted processes are serviced When the priority of a new process reaches that of an accepted process that new process becomes accepted

Question 40

Explain rates in SRR?

Answer 40

The priority of a new process will increase by at a rate a The priority of an accepted process will increase by a rate b Both a and b are parameters and can be adjusted to tune the method

Question 41

How can CPU scheduling become more complex?

Answer 41

when multiple CPUs are available such as: * Homogeneous processors * Symmetric multiproccessing – load sharing * Asymmetric multiprocessing – only one processor accesses system data structures, no need for data sharing