Given. P starts at 0 when a process enters the multiprogramming mix and is incremented every $T$ units in every PCB (the rule is not restricted to ready processes), plus a uniform $+K$ added to every PCB every $50T$ units; the scheduler re-decides only when the running process blocks for I/O or completes, scans the whole Process Table from the top, and picks the ready process with the smallest P.
Find. As many distinct design defects as can be identified.
Approach. Track what P actually measures for a population of processes created at different times, since the scheduling rule ("pick smallest P") only makes sense if P encodes something the designer intended it to encode — typically wait time, for fairness/aging.
Defect 1 — P measures elapsed time since creation, not time spent waiting. Because the "$+1$ every $T$" increment is applied to every PCB regardless of its state (ready, running, or blocked), two processes both currently ready but created at different times will always differ in P by exactly the gap between their creation times — P never distinguishes "time actually spent waiting in the ready queue" from "time spent running or blocked." An intended aging/fairness field should track wait time specifically.
Defect 2 — selecting the smallest P is backwards for fairness and causes starvation of older processes. Since every active PCB's P increases in lockstep at the same rate, the ready process with the smallest P is always the most recently created one, not the one that has waited longest. This is effectively a last-in behaviour among ready processes: a steady stream of newly created processes can perpetually have smaller P than an older process that has been sitting in the ready queue, so that older process may never be selected — indefinite starvation of exactly the processes an aging scheme is normally meant to protect.
Defect 3 — the "every 50T, add K to every PCB" rule has no effect on any scheduling decision. Because the same constant $K$ is added simultaneously to every PCB's P, it shifts every process's value by the same amount and can never change which process has the smallest P (confirmed algebraically and by simulation: the ranking before and after the boost is identical). As stated, this rule is a dead provision — if it was intended as a periodic priority boost for waiting processes specifically, it fails to achieve that because it is not restricted to the ready state.
Defect 4 — the scheduler is non-preemptive despite maintaining a priority-like field. A new scheduling decision is made only when the running process blocks or terminates; a CPU-bound process that never blocks can therefore monopolize the CPU indefinitely no matter how small any other process's P becomes — the classic convoy/monopolization defect, and it makes P's aging behaviour moot for as long as the current process keeps running.
Defect 5 — every decision is a linear scan of the entire Process Table. The scheduler examines every PCB from the top, including blocked processes that can never be chosen, so each decision costs $O(N)$ in the total number of processes rather than using a ready queue ordered by P. Ties on the smallest P are resolved only implicitly, by table position (the first match found from the top wins), which systematically favours processes that happen to occupy low table slots.
Defect 6 — P grows without bound. P is incremented forever (plus $K$ every $50T$), so a long-lived process's counter can overflow its fixed-width field; on wrap-around the oldest process suddenly shows the smallest P, making the selection erratic.
Final Results – Question 3(a)
#
Defect
1
P tracks time-since-creation for every PCB state, not time spent waiting
Uniform "+K every 50T" never changes the ranking → has zero scheduling effect
4
Non-preemptive design → a non-blocking process can monopolize the CPU indefinitely
5
O(N) scan of the whole table (incl. blocked PCBs) each decision; ties resolved by table position
6
Unbounded P → counter overflow/wrap-around
(b) Deadlock vs. starvation, and monitors.Deadlock is a state in which a set of processes are each waiting for a resource held by another process in that same set, forming a cycle, so that none of them can ever proceed — the blocking is mutual and permanent regardless of scheduling. Starvation (indefinite postponement) is different: a single process is repeatedly denied a resource because the resource-management/scheduling policy keeps favouring other processes — there is no cycle, and the resource genuinely becomes available at times, but the unlucky process's requests are never the one selected.
Can starvation occur if the critical section is protected by a monitor? Yes, it can — a monitor by itself only guarantees mutual exclusion (at most one process/thread active inside at a time); it says nothing about the order in which processes queued at the entry gate or blocked on a condition variable are subsequently admitted. If the underlying implementation resolves that queue in FIFO order, starvation cannot occur; but if it uses an unfair, priority-based, or arbitrary selection (e.g. "signal" waking an arbitrary waiter, or new callers being allowed to "barge in" ahead of those already waiting), a specific process can in principle be passed over indefinitely even though the monitor correctly serializes access.
(c) Effective memory access time / maximum page-fault rate
Given. Memory access time $ma=100$ ns; page-fault service time $=40$ ms if the replaced page is modified, $20$ ms otherwise (empty frame available, or replaced page unmodified); 45% of page faults require replacement of a modified page (the remaining 55% cost 20 ms). Target: effective access time (EAT) $\le 200$ ns.
Find. Maximum acceptable page fault rate $p$.
Approach. Because the page map table is held in associative registers, a page hit costs one memory access only (no separate page-table read; the associative lookup time is not given and is taken as negligible). Blend the two page-fault service-time cases into one average service time, then solve the standard EAT equation for $p$.
Average page-fault service time.
$$\overline{t_{pf}} = 0.45(40\text{ ms}) + 0.55(20\text{ ms}) = 18\text{ ms}+11\text{ ms}=29\text{ ms}$$
