Multilevel Feedback Queue scheduling - Paper & Pencil example

Question

I cannot seem to find a good example of a multilevel feedback queue online showing what will happen. I don't necessarily need the whole question answered, just how to do a few iterations, given the following problem:

1. Process A: p nice = 2, run for 0.1s, sleep for 0.6s, run for 0.2s
2. Process B: p nice = 1, run for 0.3s, sleep for 1.0s, run for 0.3s
3. Process C: p nice = 3, run for 1.0s
4. Process D: p nice = 1, run for 0.5s

Do a pencil-and-paper scheduling using the described scheduling algorithm, and write down the name of process to be run next at each context-switch. Assume processes sleep or exit right after they are scheduled to run, (i.e if a process exits after 0.1 s, it will be scheduled twice), and processes wake up right before the context switch happens. Assume the load of the system is 0.5. Round each step of your calculation to 2 decimal places.

The scheduler assigns processes priorities that range between 0 to 127, with 0 being the highest. Kernel processes can have priority between 0-49, and user processes can use priorities 50-127. Processes that are ready for execution reside in one of the 32 run queues, with each runqueue containing processes of 4 adjacent priorities (prio/4 = run queue). Processes in a run queue are not further ordered.

At every context switch, the process at the head of the highest priority queue is chosen for execution. After each quantum (0.1s) the currently running process is context switched out. The scheduler removes the process from the head of its original queue, adjusts its prority (if needed - see below), and places it at the end of the queue that it belongs to (since its priority might have just changed). The run queues are then rescanned for the highest priority queue that contains a runnable process.

When a process is created, it starts with a base priority (for a user process, we call it PUSER set it to 50) and an estimate cpu utilization (estcpu) of 0.0. Everytime a process has executed for one quantum, its estcpu is incremented by 1. After a process has executed for 4 quanta, its priority is recalculated according to the following formula: Prio = PUSER + (estcpu/4) + 2* p_nice (Note: Prio will not become less than PUSER) where p_nice is a value that is specified when the process is created. It can range from -20 to 19, but for user processes, specifying a negative value will be ignored and default to 0.

EDIT:: Here is my answer to this problem, would anyone care to look this over?

or link: https://i.stack.imgur.com/aNmQ9.jpg

Answer 1

The first thing to do is set up the starting state and define terms of reference. P(X)_t will be the priority of process X at quantum t; E(X)_t will be the estimated CPU usage of process X at quantum t; T(X)_t will be the number of quanta left until the next state change. S(X)_t will be the process's state — R = runnable, S = sleeping, D = dead. A process X has a niceness N(X). There are multiple queues, Q_n being the queue for priorities n…n+3. We're dealing with user processes, so each process X is scheduled at priority P(X)_t = PUSER + E(X)_t/4 + 2 * N(X), and the initial estimated CPU is given by E(X)₀ = 0.

N(A) = 2; N(B) = 1; N(C) = 3; N(D) = 1.

Initially, P(A)₀ = 54 (50 + 0 + 2 * 2); P(B)₀ = 52, P(C)₀ = 56; P(D)₀ = 52. Hence, A, B and D are on Q₁₃, and C is on Q₁₄. For sake of contrariness, D is at the front of Q₁₃, followed by B, followed by A.

For the next quantum, the scheduler chooses the process at the front of Q₁₃, which is D. D runs for the quantum (and has 4 quanta left to run at the end, and E(D)₁ = 1). It is placed on the back of Q₁₃, and the next process, B, is run for a quantum (so E(B)₂ = 1, and it has 2 quanta left before it snoozes. It is placed on the back of Q₁₃, and A runs for the next quantum, and so on.

You need to devise a 'pencil and paper' notation to record what's going on.

        ---- A ----   ---- B ----   ---- C ----   ---- D ----
t   R    P  E  S  T    P  E  S  T    P  E  S  T    P  E  S  T    Q13     Q14
0   D   54  0  R  1   52  0  R  3   56  0  R 10   52  0  R  5    D,B,A   C
1   B   54  0  R  1   52  0  R  3   56  0  R 10   53  1  R  4    B,A,D   C
2   A   54  0  R  1   53  1  R  2   56  0  R 10   53  1  R  4    A,D,B   C
3   D   55  1  S  6   53  1  R  2   56  0  R 10   53  1  R  4    D,B,A   C
4   B   55  1  S  5   53  1  R  2   56  0  R 10   54  2  R  4    B,A,D   C

and so the process continues. Eventually, processes will go to sleep for a number of quanta (note that the time remaining for a sleeping process decreases on each quantum, not when it might have been scheduled), or will die (never run again), etc. You need to be careful to understand that the line records the state at the start of a quantum.