Split View: [운영체제] 05. CPU 스케줄링 알고리즘

[Process Execution Cycle]

CPU Burst -> I/O Burst -> CPU Burst -> I/O Burst -> ...

  |-------|          |--------|          |--|
  CPU exec          I/O wait           CPU exec
  (compute)        (disk read)        (compute)

CPU-bound process: Long CPU bursts, few I/O bursts
I/O-bound process: Short CPU bursts, many I/O bursts

[FCFS Example]

Process  Arrival  CPU Burst
  P1        0         24
  P2        0          3
  P3        0          3

Execution order: P1 -> P2 -> P3

Gantt Chart:
|----P1----|--P2--|--P3--|
0         24    27     30

Waiting time: P1=0, P2=24, P3=27
Average waiting time: (0+24+27)/3 = 17

What if the order were P2, P3, P1?
|P2|P3|----P1----|
0  3  6         30

Waiting time: P1=6, P2=0, P3=3
Average waiting time: (6+0+3)/3 = 3  (huge difference!)

[SJF Example - Non-preemptive]

Process  Arrival  CPU Burst
  P1        0         6
  P2        2         8
  P3        4         7
  P4        5         3

Gantt Chart:
|--P1--|P4|---P3---|----P2----|
0      6  9      16         24

Waiting time: P1=0, P2=16, P3=5, P4=1
Average waiting time: (0+16+5+1)/4 = 5.5

[SRTF (Shortest Remaining Time First) - Preemptive SJF]

Process  Arrival  CPU Burst
  P1        0         6
  P2        2         8
  P3        4         7
  P4        5         3

Time 0: P1 starts (remaining: 6)
Time 2: P2 arrives (remaining: 8) -> P1 continues (remaining: 4)
Time 4: P3 arrives (remaining: 7) -> P1 continues (remaining: 2)
Time 5: P4 arrives (remaining: 3) -> P1 continues (remaining: 1)
Time 6: P1 completes -> P4 starts (remaining: 3)
Time 9: P4 completes -> P3 starts (remaining: 7)
Time 16: P3 completes -> P2 starts (remaining: 8)
Time 24: P2 completes

Gantt Chart:
|--P1--|P4|---P3---|----P2----|
0      6  9      16         24

Next prediction = alpha * recent actual + (1 - alpha) * previous prediction

alpha = 0: Ignore recent value (use only previous prediction)
alpha = 1: Ignore previous prediction (use only recent actual)
Typically alpha = 0.5

[Priority Scheduling Example] (lower number = higher priority)

Process  CPU Burst  Priority
  P1        10         3
  P2         1         1
  P3         2         4
  P4         1         5
  P5         5         2

Execution order: P2 -> P5 -> P1 -> P3 -> P4

Gantt Chart:
|P2|--P5--|----P1----|P3|P4|
0  1      6        16 18 19

Average waiting time: (6+0+16+18+1)/5 = 8.2

[Round Robin Example] (time quantum = 4)

Process  CPU Burst
  P1        24
  P2         3
  P3         3

Gantt Chart:
|P1|P2|P3|P1|P1|P1|P1|P1|
0  4  7 10 14 18 22 26 30

P1: Runs 4 units -> back of ready queue
P2: Runs 3 units (complete)
P3: Runs 3 units (complete)
P1: Remaining 20 units run in chunks of 4

Waiting time: P1=6, P2=4, P3=7
Average waiting time: (6+4+7)/3 = 5.67

[Multilevel Queue Scheduling]

High Priority
+------------------------------------------+
| System Processes      | FCFS              |
+------------------------------------------+
| Interactive Processes | RR (q=8)          |
+------------------------------------------+
| Interactive Editing   | RR (q=16)         |
+------------------------------------------+
| Batch Processes       | FCFS              |
+------------------------------------------+
| Student Processes     | FCFS              |
+------------------------------------------+
Low Priority

Upper queues must be empty before lower queues execute (fixed priority)
Or time allocation between queues (e.g., 80% interactive, 20% batch)

[Multilevel Feedback Queue]

Queue 0: RR (q=8)   <--- New processes enter here
  |
  | If not complete within q=8, move to Queue 1
  v
Queue 1: RR (q=16)
  |
  | If not complete within q=16, move to Queue 2
  v
Queue 2: FCFS

Operation example:
- Short CPU burst process: Completes in Queue 0 (fast response)
- CPU-bound process: Moves down Queue 0 -> Queue 1 -> Queue 2
- Process returning after I/O completion: Moves back up to Queue 0

Result: I/O-bound + interactive processes get high priority
        CPU-bound processes get long time allocation in lower queues

// Setting processor affinity in Linux
#define _GNU_SOURCE
#include <sched.h>

void set_cpu_affinity(int cpu_id) {
    cpu_set_t cpuset;
    CPU_ZERO(&cpuset);
    CPU_SET(cpu_id, &cpuset);

    // Bind current thread to a specific CPU
    sched_setaffinity(0, sizeof(cpuset), &cpuset);
}

[CFS Operating Principle]

Tracks each process's vruntime
Runs the process with the smallest vruntime next

vruntime increase rate = actual runtime / weight (based on nice value)

Process with low nice value (high priority):
  -> Large weight -> vruntime increases slowly -> Scheduled more often

Process with high nice value (low priority):
  -> Small weight -> vruntime increases quickly -> Scheduled less often

[CFS Red-Black Tree]

         Sorted by vruntime

              (P3: 50)
             /        \
        (P1: 30)    (P5: 70)
        /    \          \
   (P2: 20) (P4: 40)  (P6: 80)

Leftmost node (P2, vruntime=20) is the next to execute

Insert/Delete/Search: O(log N) guaranteed

// Selecting the next process to run in CFS (conceptual code)
struct task_struct *pick_next_task_fair(struct rq *rq) {
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct rb_node *left;

    // Select the leftmost node in the Red-Black tree
    // = process with the smallest vruntime
    left = rb_first_cached(&cfs_rq->tasks_timeline);
    if (!left)
        return NULL;

    struct sched_entity *se = rb_entry(left,
                                        struct sched_entity,
                                        run_node);
    return container_of(se, struct task_struct, se);
}

Example: Target latency = 20ms, runnable processes = 4

With equal priority, each process gets 5ms
If there are too many processes, a minimum granularity is guaranteed

[Scheduling Algorithm Comparison]

Algorithm        Preempt Starv  Advantage           Disadvantage
---------        ------- -----  ---------           ------------
FCFS             X       X      Simple              Convoy effect
SJF              X       O      Optimal wait time   Burst prediction hard
SRTF             O       O      Better than SJF     Burst prediction hard
Priority         Both    O      Flexible            Starvation (aging needed)
Round Robin      O       X      Fair, good response q selection critical
Multilevel Queue O       O      Differentiated svc  No inter-queue movement
MLF Queue        O       Poss.  Most flexible       Complex parameter tuning
CFS              O       X      Fair CPU allocation Complex implementation