Identify OS component causing process starvation
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
Quick Answer: This question evaluates understanding of process scheduling, kernel-level resource allocation, and starvation-related concurrency issues within the operating systems domain.
Constraints
- 0 <= len(processes) <= 2000
- 1 <= cores <= 30
- Each pid is unique
- state is either 'RUNNABLE' or 'BLOCKED'; priority, affinity_mask, and runtime are non-negative integers
Examples
Input: ([(1, 'RUNNABLE', 5, 3, 10), (2, 'RUNNABLE', 5, 3, 10), (3, 'RUNNABLE', 5, 3, 10), (4, 'RUNNABLE', 5, 3, 10), (5, 'RUNNABLE', 5, 3, 0)], 2)
Expected Output: [(5, 'scheduler', 'fairness')]
Explanation: Process 5 is runnable and can run on both cores, but it got no runtime while identical peers did. No higher-priority process explains the starvation, so this points to scheduler fairness or run-queue behavior.
Input: ([(1, 'RUNNABLE', 9, 1, 15), (2, 'RUNNABLE', 8, 2, 15), (3, 'RUNNABLE', 7, 3, 15), (4, 'RUNNABLE', 5, 3, 0)], 2)
Expected Output: [(4, 'scheduler', 'priority')]
Explanation: Process 4 can use both cores, but higher-priority runnable processes with positive runtime cover both cores and are numerous enough to keep it from running.
Input: ([(1, 'RUNNABLE', 5, 1, 10), (2, 'RUNNABLE', 5, 2, 10), (3, 'RUNNABLE', 5, 4, 0)], 2)
Expected Output: [(3, 'scheduler', 'affinity')]
Explanation: On a 2-core system, affinity bit 4 refers to a non-existent core. After masking invalid bits, process 3 has no real CPU it can run on.
Input: ([(10, 'RUNNABLE', 5, 3, 12), (11, 'RUNNABLE', 5, 3, 12), (12, 'RUNNABLE', 5, 3, 0), (13, 'RUNNABLE', 1, 4, 0)], 2)
Expected Output: [(12, 'scheduler', 'fairness'), (13, 'scheduler', 'affinity')]
Explanation: Process 12 is runnable with valid affinity but got no time despite equal-priority peers running, so it is a fairness issue. Process 13 has no valid core after masking, so it is an affinity issue.
Input: ([(1, 'RUNNABLE', 5, 3, 10), (2, 'BLOCKED', 5, 3, 0)], 2)
Expected Output: []
Explanation: The zero-runtime process is BLOCKED, not RUNNABLE, so it is not considered starvation in this model.
Input: ([(1, 'RUNNABLE', 5, 1, 0)], 1)
Expected Output: []
Explanation: With only one runnable process and no other process receiving CPU time, there is no evidence of starvation.
Solution
def solution(processes, cores):
if not processes or cores <= 0:
return []
valid_bits = (1 << cores) - 1
normalized = []
for pid, state, priority, affinity_mask, runtime in processes:
valid_mask = affinity_mask & valid_bits
normalized.append((pid, state, priority, valid_mask, runtime))
active = []
for pid, state, priority, valid_mask, runtime in normalized:
if state == 'RUNNABLE' and valid_mask != 0 and runtime > 0:
active.append((pid, priority, valid_mask))
if not active:
return []
result = []
for pid, state, priority, valid_mask, runtime in normalized:
if state != 'RUNNABLE' or runtime != 0:
continue
if valid_mask == 0:
result.append((pid, 'scheduler', 'affinity'))
continue
higher_count = 0
coverage = 0
for other_pid, other_priority, other_mask in active:
if other_pid == pid:
continue
overlap = other_mask & valid_mask
if other_priority > priority and overlap:
higher_count += 1
coverage |= overlap
needed = min(cores, bin(valid_mask).count('1'))
if higher_count >= needed and coverage == valid_mask:
result.append((pid, 'scheduler', 'priority'))
else:
result.append((pid, 'scheduler', 'fairness'))
result.sort(key=lambda x: x[0])
return result
Time complexity: O(n^2). Space complexity: O(n).
Hints
- Mask every affinity with (1 << cores) - 1 first, so invalid core bits disappear.
- Precompute the RUNNABLE processes that actually got CPU time; then compare each zero-runtime RUNNABLE process against that active set.