A computer has two processors, M₁ and M₂. Four processes P₁, P₂, P₃, P₄ with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows:
M₁ uses priority of execution for the processes as, P₁ > P₃ > P₂ > P₄.
M₂ uses priority of execution for the processes as, P₂ > P₃ > P₄ > P₁.
A process Pᵢ is scheduled to a processor Mₖ, if the processor is free and no other process Pⱼ is waiting with higher priority. Ignore the context switch time. What will be the average waiting time of the processes in milliseconds?
✅ Final Answer:
The correct answer is option (A) 9.00.
🔹 Short Answer:
At time t=0, P₁ (highest priority for M₁) takes M₁ and P₂ (highest priority for M₂) takes M₂. Their waiting times are 0. M₂ becomes free at t=16, and P₃ (next highest priority for M₂) is scheduled. P₃'s waiting time is 16 ms. M₁ becomes free at t=20, and the only remaining process, P₄, is scheduled. P₄'s waiting time is 20 ms. The average waiting time is (0 + 0 + 16 + 20) / 4 = 36 / 4 = 9.00 ms.
🔸 Long Answer:
This question requires a step-by-step simulation of a non-preemptive priority scheduling algorithm on a multi-processor system. Each processor has its own priority list.
Initial State (t=0)
Processes Ready: {P₁, P₂, P₃, P₄}
Processors Free: {M₁, M₂}
Priorities M₁: P₁ > P₃ > P₂ > P₄
Priorities M₂: P₂ > P₃ > P₄ > P₁
Scheduling at t=0
Processor M₁: It is free. Among the ready processes, P₁ has the highest priority for M₁. So, P₁ is scheduled on M₁. It will run for 20 ms.
Waiting Time (P₁) = 0 ms
Processor M₂: It is free. Among the remaining ready processes {P₂, P₃, P₄}, P₂ has the highest priority for M₂. So, P₂ is scheduled on M₂. It will run for 16 ms.
Waiting Time (P₂) = 0 ms
Processes Waiting: {P₃, P₄}
Gantt Chart (Initial)
Subsequent Scheduling
The first processor to become free is M₂ at t=16 ms.
At t = 16 ms:
Processor M₂ becomes free.
Processes Waiting: {P₃, P₄}
We check the priority list for M₂: P₂ > P₃ > P₄ > P₁. Between P₃ and P₄, P₃ has higher priority.
So, P₃ is scheduled on M₂. It starts at t=16 and will run for 25 ms.
Waiting Time (P₃) = 16 ms
At t = 20 ms:
Processor M₁ becomes free.
Processes Waiting: {P₄}
As P₄ is the only process waiting, P₄ is scheduled on M₁. It starts at t=20 and will run for 10 ms.
Waiting Time (P₄) = 20 ms
Final Gantt Chart
Calculate Average Waiting Time
Process
Burst Time (ms)
Start Time (ms)
Waiting Time (ms)
P₁
20
0
0
P₂
16
0
0
P₃
25
16
16
P₄
10
20
20
Total Waiting Time
36
Average Waiting Time = Total Waiting Time / Number of Processes
Average Waiting Time = (0 + 0 + 16 + 20) / 4 = 36 / 4 = 9.00 ms
Bibliography:
- Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts. Wiley. (Chapter 6: CPU Scheduling).
Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.
Get link
Facebook
X
Pinterest
Email
Other Apps
Comments
Popular posts from this blog
GATE 2025 CS/IT Question 1 GATE2025_CS1_Q1 Question: Ravi had ____ younger brother who taught at ____ university. He was widely regarded as ____ honorable man. Select the option with the correct sequence of articles to fill in the blanks. A. a; a; an B. the; an; a C. a; an; a D. an; an; a 👁️ View Full Answer ✅ Final Answer: The correct sequence of articles is (a; a; an) , which corresponds to option (A) . 🔹 Short Answer: The selection of the indefinite article ('a' or 'an') is based on the initial sound of the word that follows. 'a' is used before consonant sounds, and 'an' is used before vowel sounds. 1. " a younger brother" - 'younger' starts with a consonant sound (/j/). 2. " a university" - 'university' starts with a consonant sound (/juː/). 3. " an honorable man"...
GATE 2025 CS/IT Question 64 GATE2025_CS1_Q64 The maximum value of x such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is ______. (answer in integer) Check Answer 👁️ View Full Answer ✅ Final Answer: The correct answer is 5 . 🔹 Short Answer: For edge (B,C) to be in *every* MST, its weight 'x' must be strictly less than the bottleneck (heaviest edge) of any alternative path between B and C. The alternative paths and their bottlenecks are: B-A-C (bottleneck 7), B-D-C (bottleneck 8), and B-D-A-C (bottleneck 6). To satisfy all conditions, 'x' must be less than the minimum of these bottlenecks, so `x 🔸 Long Answer: Graph for MST Question A B C D 7 6 x ...
GATE 2025 CS/IT Question 65 GATE2025_CS1_Q65 In a double hashing scheme, h₁(k) = k mod 11 and h₂(k) = 1 + (k mod 7) are the auxiliary hash functions. The size m of the hash table is 11. The hash function for the i-th probe in the open address table is [h₁(k) + i h₂(k)] mod m. The following keys are inserted in the given order: 63, 50, 25, 79, 67, 24. The slot at which key 24 gets stored is ______. (Answer in integer) Check Answer 👁️ View Full Answer ✅ Final Answer: The correct answer is 10 . 🔹 Short Answer: To find the slot for key 24, we calculate its hash values: h₁(24) = 24 mod 11 = 2 and h₂(24) = 1 + (24 mod 7) = 1 + 3 = 4. We then probe the hash table. Probe 0: `(2 + 0*4) mod 11 = 2` (collision). Probe 1: `(2 + 1*4) mod 11 = 6` (collision). Probe 2: `(2 + 2*4) mod 11 = 10` (empty). Key 24 is placed in slot 10. 🔸 Long Answer: This problem requi...
Comments
Post a Comment
Ask you doubt here