Practice · CPU Scheduling II: Multicore, Real-Time and Linux

Q1

What is the main disadvantage of a single global run queue shared by all cores?

A It needs load balancing. B It cannot run more than one task. C All cores contend for the queue's lock, and tasks move between cores, losing cache warmth. D Cores can never be idle.

Q2

An idle core takes a waiting task from a busy core's run queue. This is…

A gang scheduling B pull migration C priority inversion D push migration

Q3

Why does a scheduler prefer to keep a task on the core where it last ran (soft affinity)?

A It reduces the task's priority. B Migration is forbidden by the hardware. C The core's caches still contain the task's data (warm cache), so it runs faster. D Other cores cannot run that task.

Q4

Cores have loads core0 = 80, core1 = 10, core2 = 30, core3 = 0. After perfect balancing, what should each core's load be?

A 20 B 120 C 30 D 40

Q5

In a two-socket NUMA server, why should the scheduler keep a task on the socket where its memory is allocated?

A Remote memory accesses across sockets are slower than local ones. B The other socket has no cores. C NUMA forbids migration. D It increases the task's priority.

Q6

A laptop reports 8 logical CPUs from 4 physical cores with SMT (Hyper-Threading). Two CPU-heavy threads run on the two logical CPUs of the same core. What is typical?

A Each runs exactly as fast as on its own core. B Only one of them can run. C They run twice as fast. D They share the core's execution units, so each usually runs slower than it would on a separate core.

Q7

Why is gang scheduling useful for parallel scientific programs?

A It gives all threads the lowest priority. B It prevents the use of multiple cores. C It runs one thread at a time to save energy. D Threads that communicate often run simultaneously, so they do not wait for partners that are not running.

Q8

On a phone with big and little cores, where should the OS usually run a background photo-backup task?

A It cannot run on a phone B On a little (efficiency) core, saving energy for work the user is waiting for C On a big core at maximum frequency D On all cores at once

Q9

Which Linux scheduling class is checked first (highest precedence)?

A SCHED_IDLE B SCHED_NORMAL C SCHED_DEADLINE D SCHED_BATCH

Q10

How does CFS decide which task runs next?

A The task that arrived first B The task with the largest nice value C The task with the smallest virtual runtime (vruntime) D A random task

Q11

A nice-5 task (weight 335) runs for 3 ms under CFS. By how much does its vruntime increase?

A 3 ms B About 9.17 ms C 335 ms D About 0.98 ms

Q12

Two CPU-bound tasks share one core: nice 0 (weight 1024) and nice 10 (weight 110). What share does the nice-0 task get?

A 90.3% B 75.3% C 100% D 50%

Q13

What replaced CFS as Linux's default fair scheduler in kernel 6.6 (2023)?

A EEVDF (Earliest Eligible Virtual Deadline First) B FCFS C Round Robin D The O(1) scheduler

Q14

A periodic task needs C = 2 ms every T = 8 ms. What is its utilization?

A 16 B 0.4 C 4 D 0.25

Q15

Under rate-monotonic scheduling, which task gets the highest priority?

A The task with the longest period B The task with the shortest period C The task with the largest C D The task that arrived first

Q16

What is the Liu–Layland utilization bound for 3 tasks under RM?

A 0.780 B 0.828 C 0.693 D 1.000

Q17

Tasks T1 (C=1, T=4), T2 (2, 6), T3 (3, 12) have U = 0.833, above the 3-task bound 0.780. What can you conclude from the bound alone?

A The set is schedulable by RM. B The set is not schedulable by any algorithm. C Nothing definite: the bound is sufficient but not necessary; an exact test is needed. D The set is certainly not schedulable by RM.

Q18

Tasks T1 (C=2, T=5) and T2 (C=4, T=7). Response-time analysis for T2 gives R = 4 → 6 → 8. What does this mean?

A T2 misses its deadline under RM, because 8 > 7. B The analysis failed. C T2 meets its deadline. D T1 misses its deadline.

Q19

Can the same task set (U = 0.9714) be scheduled without deadline misses by EDF on one CPU?

A Only with two CPUs. B Yes, because EDF schedules any set with U ≤ 1 (deadlines = periods, preemptive, one CPU). C No, because it fails under RM. D Only if the periods are equal.

Q20

What caused the repeated resets of Mars Pathfinder in 1997?

A A disk failure B A virus uploaded from Earth C Running out of memory D Priority inversion: a high-priority task waited for a lock held by a low-priority task that was preempted by a medium-priority task

Q21

How does priority inheritance prevent priority inversion?

A It runs all tasks at the same priority. B A task holding a lock needed by a higher-priority task temporarily inherits that higher priority, so medium-priority tasks cannot preempt it. C It lowers the priority of the waiting high-priority task. D It removes all locks.

Q22

If dynamic power grows about with f³, what happens to the dynamic energy of a fixed task when the frequency is halved?

A It falls to about one quarter (energy ∝ W·f²), while the task takes twice as long. B It falls to one eighth and the task takes the same time. C It doubles. D It stays the same.

Q23

Why is "race to idle" (run fast, then sleep) sometimes more energy-efficient than running slowly?

A It is never more efficient. B Because static (leakage) and platform power are paid for the whole time the chip is active; finishing early lets it enter a deep sleep state. C Because fast CPUs have no power consumption. D Because frequency does not affect power.

Q24

A set of periodic tasks has total utilization U = 1.15 on one CPU. What is true?

A EDF can still schedule it without misses. B RM can schedule it if priorities are chosen well. C It is schedulable because 1.15 is close to 1. D No scheduling algorithm can meet all deadlines on one CPU; some jobs must miss or be dropped.

Q25

Under SCHED_FIFO, a real-time task never blocks. What happens to normal (SCHED_NORMAL) tasks on the same core?

A They are starved (apart from a small safety margin Linux reserves by default), because real-time classes take precedence. B They share the CPU equally with it. C The kernel converts the FIFO task to a normal task after 1 second. D They run first because they are older.

Q26

Which Linux command runs a program restricted to cores 0 and 1?

A nice -n 0,1 program B chmod 01 program C kill -0 program D taskset -c 0,1 program

Q27 Short answer

Apply rate-monotonic analysis to three periodic tasks: A (C = 1, T = 4), B (C = 1, T = 5), C (C = 2, T = 10). Compute U, compare with the Liu–Layland bound, and compute the response time of each task.

Q28 Short answer

Explain priority inversion with the Mars Pathfinder example, naming the three tasks' roles, and explain how priority inheritance solves it. Why was a watchdog timer involved?

Q29 Short answer

An EdgeCampus phone must run a 1.2 × 10⁹-cycle AR recognition task within 1 s and a 0.5 × 10⁹-cycle photo-backup task within 1 s. The big core runs at 2 GHz using 2.0 W; the little core at 1 GHz using 0.4 W. For each task, compute time and energy on each core and choose the best core that meets the deadline.

Q30 Short answer

Compare RM and EDF: priority type, optimality, schedulability test, behaviour under overload, and implementation. When would you choose each for an EdgeCampus sensor controller?