2LFIG 2015-2016 Correction série N° 2

This document presents a series of exercises on process scheduling algorithms and performance evaluation in operating systems. The assessment tests understanding of scheduling policies, calculation of waiting and execution times, and comparison of different algorithms such as FIFO, Priority, Round Robin, and Shortest Remaining Time Next.

I.a

Task: Calculate the processor time consumed (Temps processeur consommé) by each process using the formula:

Processor time consumed = Number of queues consumed (threads traversed if the system applies recycling)

Given processes P1, P2, P3, P4, P5, and P6, the times are:

• TC1 = 0Q
• TC2 = 3Q
• TC3 = 2Q
• TC4 = < 1Q
• TC5 = 2Q
• TC6 = 1Q

Answer: The processor times consumed by processes P1 to P6 are respectively 0Q, 3Q, 2Q, less than 1Q, 2Q, and 1Q.

I.b

Task: Calculate the waiting time (Temps d’attente) for each process, defined as the time before the process becomes active on the processor.

The timeline of process activity by quantum (Q) is given as:

• < Q: P4 active
• 1Q: P1 active
• 2Q to 3Q: P4 and P6 active
• 4Q: P1 active
• 5Q: P3 active
• 6Q: P5 active
• 7Q: P6 active
• 8Q: P4 active
• 9Q: P1 active
• 10Q: P2 active

From this, the waiting times are:

• TA1 = < Q (between 0 and 1Q)
• TA2 = 9Q
• TA3 = 4Q
• TA4 = 0Q
• TA5 = 5Q
• TA6 = 1Q

Answer: The waiting times for processes P1 to P6 are respectively less than 1Q, 9Q, 4Q, 0Q, 5Q, and 1Q.

I.c

Task: Describe the state of the system after 2 quanta (2Q) with recycling of processes.

After 2Q, the process queues and processor are as follows:

• Recycling queue: P2, P5, P3, P1, P4
• First priority queues: FP4, FP3, FP3, FP2, FP1
• Processor: P6
• Entry queue: (not specified)

Answer: After 2Q, the processor runs P6, while processes P2, P5, P3, P1, and P4 are in the recycling queue and priority queues as listed.

I.d

Task: Distinguish between two scheduling configurations based on preemption policy.

Case 1: Non-preemptive policy

This policy respects the full quantum time allocated to each process. The system state is:

• Recycling queue: P2, P5, P3, P1, P4
• Priority queues: FP4, FP3, FP2, FP1
• Processor: P6
• Entry queue: P7

Case 2: Preemptive policy

Here, processes do not necessarily respect their full quantum Q. The creation of process P7 causes a preemption: P6 is moved to the FP1 queue and the processor is given to P7, indicating P7 has higher priority.

• Recycling queue: P2, P5, P3, P1, P4
• Priority queues: FP4, FP3, FP2, FP1
• Entry queue: P6

Answer: The non-preemptive policy allows processes to complete their quantum uninterrupted, while the preemptive policy interrupts processes when a higher priority process (P7) arrives.

II.a

Task: Calculate execution times and average execution time for three processes under different scheduling algorithms: FIFO, Priority Queue, Round Robin, and Shortest Remaining Time Next.

Definitions:

• Waiting time = Start time of execution - Submission time
• Execution time = Calculation time + Waiting time
• Average execution time = Sum of execution times / Number of processes

FIFO Algorithm

• TEp1 = 3 + 0 = 3
• TEp2 = 4 + 4 = 8
• TEp3 = 2 + 2 = 4

Average execution time:

TME = (3 + 8 + 4) / 3 = 15 / 3 = 5

Priority Queue Algorithm

• TEp1 = 7 + 2 = 9
• TEp2 = 0 + 4 = 4
• TEp3 = 3 + 3 = 6

Average execution time:

TME = (9 + 4 + 6) / 3 = 19 / 3 ≈ 6.3

Round Robin Algorithm

• TEp1 = 3 + 2 = 5
• TEp2 = 3 + 4 = 7
• TEp3 = 2 + 3 = 5

Average execution time:

TME = (5 + 7 + 5) / 3 = 17 / 3 ≈ 5.7

Shortest Remaining Time Next Algorithm

• TEp1 = 1 + 2 = 3
• TEp2 = 3 + 4 = 7
• TEp3 = 1 + 3 = 4

Average execution time:

TME = (3 + 7 + 4) / 3 = 14 / 3 ≈ 4.7

Answer: The average execution times for FIFO, Priority, Round Robin, and Shortest Remaining Time Next are 5, 6.3, 5.7, and 4.7 respectively, with Shortest Remaining Time Next being the most efficient in this case.

II.b

Task: Calculate the average waiting time for the three processes under the same scheduling algorithms.

FIFO Algorithm

• TAp1 = 0
• TAp2 = 3
• TAp3 = 2

Average waiting time:

TMA = (0 + 3 + 2) / 3 = 5 / 3 ≈ 1.7

Priority Queue Algorithm

• TAp1 = 0
• TAp2 = 0
• TAp3 = 0

Average waiting time:

TMA = (0 + 0 + 0) / 3 = 0

Round Robin Algorithm

• TAp1 = 0
• TAp2 = 1
• TAp3 = 1

Average waiting time:

TMA = (0 + 1 + 1) / 3 = 2 / 3 ≈ 0.7

Shortest Remaining Time Next Algorithm

• TAp1 = 0
• TAp2 = 3
• TAp3 = 2

Average waiting time:

TMA = (0 + 3 + 2) / 3 = 5 / 3 ≈ 1.7

Answer: The average waiting times are 1.7 (FIFO), 0 (Priority), 0.7 (Round Robin), and 1.7 (Shortest Remaining Time Next), with Priority scheduling minimizing waiting time.

II.2

Task: Given four processes with tuples (submission time, execution time, priority) as:

• P1 = (1, 2, 2)
• P2 = (0, 5, 4)
• P3 = (2, 4, 5)
• P4 = (3, 10, 1)

Calculate execution and waiting times for each process under different algorithms, noting that the imposed order is P1, P2, P3, P4.

FIFO Algorithm

Although the natural FIFO order would be P2, P1, P3, P4, the imposed order is P1, P2, P3, P4.

• TEp1 = 2
• TEp2 = 8
• TEp3 = 10
• TEp4 = 19

• TAp1 = 0
• TAp2 = 3
• TAp3 = 6
• TAp4 = 9

Average execution time:

TME = (2 + 8 + 10 + 19) / 4 = 39 / 4 = 9.75

Average waiting time:

TMA = (0 + 3 + 6 + 9) / 4 = 18 / 4 = 4.5

Shortest Remaining Time Next Algorithm

• TEp1 = 6
• TEp2 = 5
• TEp3 = 9
• TEp4 = 18

• TAp1 = 4
• TAp2 = 0
• TAp3 = 5
• TAp4 = 8

Average execution time:

TME = (6 + 5 + 9 + 18) / 4 = 38 / 4 = 9.5

Average waiting time:

TMA = (4 + 0 + 5 + 8) / 4 = 17 / 4 = 4.25

Round Robin Algorithm (Quantum = 1)

• TEp1 = 6
• TEp2 = 13
• TEp3 = 12
• TEp4 = 18

• TAp1 = 1
• TAp2 = 0
• TAp3 = 1
• TAp4 = 1

Average execution time:

TME = (6 + 13 + 12 + 18) / 4 = 49 / 4 = 12.25

Average waiting time:

TMA = (1 + 0 + 1 + 1) / 4 = 3 / 4 = 0.75

Priority Queue Algorithm (Quantum = 1)

• TEp1 = 10
• TEp2 = 5
• TEp3 = 7
• TEp4 = 18

• TAp1 = 8
• TAp2 = 0
• TAp3 = 3
• TAp4 = 8

Average execution time:

TME = (10 + 5 + 7 + 18) / 4 = 40 / 4 = 10

Average waiting time:

TMA = (8 + 0 + 3 + 8) / 4 = 19 / 4 = 4.75

Answer: Among these algorithms, Shortest Remaining Time Next yields the lowest average execution and waiting times (9.5 and 4.25), while Round Robin has the highest average execution time (12.25) but lowest waiting time (0.75).

III.a

Task: Calculate the average execution time for four processes with given execution times:

• TEp1 = 230
• TEp2 = 300
• TEp3 = 280
• TEp4 = 340

Average execution time:

TME = (230 + 300 + 280 + 340) / 4 = 1150 / 4 = 287.5

Answer: The average execution time is 287.5.

III.b

Task: Calculate the average waiting time for the same four processes with given waiting times:

• TAp1 = 0
• TAp2 = 40
• TAp3 = 70
• TAp4 = 140

Average waiting time:

TMA = (0 + 40 + 70 + 140) / 4 = 250 / 4 = 62.5

Answer: The average waiting time is 62.5.

IV.a

Task: Identify the scheduling algorithm and I/O device assignment.

Answer: FIFO scheduling with each process assigned to its own I/O peripheral device.

IV.b

Task: Identify the scheduling algorithm and I/O device assignment.

Answer: Round Robin scheduling with quantum Q=5, each process assigned to its own I/O peripheral device.

IV.c

Task: Identify the scheduling algorithm and I/O device assignment.

Answer: Round Robin scheduling with quantum Q=5, all processes sharing the same I/O peripheral device.

Method

This paper rewards clear understanding and application of scheduling algorithms, precise calculation of waiting and execution times, and correct interpretation of process states and priorities. It emphasizes step-by-step reasoning, careful use of formulas, and attention to the imposed order of processes when specified. Mistakes are penalized when calculations are done without showing intermediate steps, when assumptions contradict given data, or when the scheduling policy is misunderstood (e.g., confusing preemptive and non-preemptive behavior). Correctly distinguishing between waiting time and execution time, and accurately averaging these over processes, is crucial. The paper also tests the ability to analyze the impact of quantum size and I/O device assignment on scheduling outcomes.