Interrupts and Scheduling Algorithms

Question 1

What is an interrupt?

Answer 1

Interrupts are signals generated by software or hardware to indicate to the processor that a process needs attention.

Question 2

Different types of interrupts have different…

Answer 2

priorities and how urgent they are must be taken into account by the operating system when allocating processor time.

Question 3

How are interrupts evaluated?

Answer 3

Interrupts are stored in order of their priority within an abstract data structure called a priority queue in a special register known as an interrupt register. It is the job of the operating system to ensure interrupts are serviced fairly by the processor through the Interrupt Service Routine (ISR).

Question 4

Describe the mechanics of the Interrupt Service Routine.

Answer 4

The processor checks the contents of the interrupt register at the end of each Fetch-Decode-Execute cycle. If an interrupt exists that is of a higher priority to the process being executed, the current contents of the special purpose registers in the CPU are temporarily transferred into a stack. The processor then responds to the interrupt by loading the appropriate ISR into RAM. A flag is set to signal the ISR has begun. Once the interrupt has been serviced, the flag is reset. The interrupt queue is checked again for further interrupts of a higher priority to the process that was originally being executed.

Question 5

What does ISR stands for?

Answer 5

Interrupt Service Routine

Question 6

How does the OS manages the execution of different programs?

Answer 6

The OS implements various scheduling algorithms that, albeit working in different ways, ensure all sections of programs being run (known as ‘jobs’) receive a fair amount of processing time.

Question 7

What are the 2 types of scheduling algorithms?

Answer 7

Pre-emptive and non pre-emptive algorithms

Question 8

What are some examples of pre-emptive algorithms?

Answer 8

Multilevel Feedback Queues, Shortest Remaining Time, Round Robin

Question 9

What are some examples of non pre-emptive algorithms?

Answer 9

First Come First Served, Shortest
Job First

Question 10

What are the characteristics of pre-emptive algorithms?

Answer 10

Jobs are actively made to start and stop by the OS.

Question 11

What are the characteristics of non pre-emptive algorithms?

Answer 11

Once a job is started, it is left alone until it is completed.

Question 12

Describe the mechanics of the Round robin algorithm.

Answer 12

Each job is given a fixed section of processor time - known as a time slice - within which it is allowed to execute. Once each job in the queue has used its first time slice, the operating system again grants each job an equal slice of processor time. This continues until a job has been completed, at which point it is removed from the queue.

Question 13

What are the advantages of the Round Robin algorithm?

Answer 13

Round Robin ensures each job is seen to.

Question 14

What are the disadvantages of the Round Robin algorithm?

Answer 14

1. Longer jobs will take a much longer time for completion due to their execution being inefficiently split up into multiple cycles.
2. This algorithm also does not take into account job priority

Question 15

Describe the mechanics of First come first served algorithm.

Answer 15

Jobs are processed in chronological order by which they entered the queue.

Question 16

What are the advantages of the First come first served algorithm?

Answer 16

It is straightforward to implement.

Question 17

What are the disadvantages of the First come first served algorithm?

Answer 17

Does not allocate processor time based on priority.

Question 18

Describe the mechanics of Multilevel feedback queues algorithm.

Answer 18

This makes use of multiple queues of different priority levels, each which is ordered based on a different priority.

Question 19

What are the advantages of the Multilevel feedback queues algorithm?

Answer 19

Takes into account priority of jobs to be executed.

Question 20

What are the disadvantages of the Multilevel feedback queues algorithm?

Answer 20

This can be difficult to implement due to deciding which job to prioritize based on a combination of priorities.

Question 21

What is processor starvation?

Answer 21

When a particular process does not receive enough time in order to be executed and completed.

Question 22

Describe the mechanics of the Shortest job first algorithm

Answer 22

The queue storing jobs to be processed is ordered according to the time required for completion, with the longest jobs being serviced at the end. The time of completion is measured in FDE cycles

Question 23

What are the advantages of the Shortest job first algorithm?

Answer 23

This type of scheduling is most suited to batch systems, where shorter jobs are given preference to minimise waiting time.

Question 24

What are the disadvantages of the Shortest job first algorithm?

Answer 24

1. It requires the processor to know or calculate how long each job will take and this is not always possible.
2. There is also a risk of processor starvation if short jobs continue being added to the job queue.

Question 25

Describe the mechanics of the Shortest remaining time algorithm.

Answer 25

The queue storing jobs to be processed is ordered according to the time left for completion, with the jobs with the least time to completion being serviced first. If a job with a smaller time to completion is added while a job is being completed, the scheduler is switched to that one.

Question 26

What are the disadvantages of using the shortest remaining time algorithm?

Answer 26

There is a risk of processor starvation for longer jobs if short jobs are added to the job queue.

Question 27

What are the advantages of using the shortest remaining time algorithm?

Answer 27

The priority of jobs is taken into account.

Question 28

What is a scheduler?

Answer 28

A scheduler is part of the OS that uses a scheduling algorithm to determine how to share processor time

Question 29

The data structure used to handle interrupts is a:

Answer 29

stack