Basic Concept

Short-term Scheduling

• Scheduling 방식으로 3가지가 있다.

1. Short-term Scheduling : memory에 이미 올라와있는 process들 중에 하나의 process를 선택하는 것.
2. Mid-term Scheduling : Swapping. memory가 작아 모든 process를 처리하기 힘들어서 Disk에 process를 넣어 놓는 것.
3. Long-term Scheduling : Disk에 있는 program 중 어떤 program을 memory로 올릴 것인지.

Chapt 5의 CPU Scheduling은 Short-Term Scheduling에 대한 내용이다.

CPU, I/O Burst Cycle

• CPU burst : process가 처리하는 내용이 CPU 중심인 cycle (CPU 실행)
• I/O burst : process가 처리하는 내용이 I/O 중심인 cycle (I/O 대기)
• process 실행은 CPU burst와 I/O burst를 왔다갔다 하며 순환된다.
• CPU burst와 I/O burst를 왔다 갔다 할 때,
  context switching(PCB를 saving, loading)하는 과정이 생긴다.
  
  • CPU burst → I/O burst로 갈 때 : scheduling 이 일어난다.
  • I/O burst → CPU burst로 갈 때 : scheduling 이 일어난다.

CPU Scheduler

• CPU가 Idle 상태가 될 때마다,
  OS는 Ready Queue에 있는 process 중에서 하나를 선택해 실행해야 한다.
  선택은 CPU Scheduler에 의해 수행된다.
  (여기서 Ready Queue는 FIFO의 의미가 아니라, 대기하는 공간이라는 의미임을 유의하자)
• Ready Queue에 있는 record들은 일반적으로 PCB들이다.
  

  생각보다 CPU burst time이 길지 않다 == context switching이 자주 생긴다

Preemptive and Nonpreemptive Scheduling

• CPU Scheduling은 다음 4가지 상황에서 발생한다.

1. process가 running state에서 waiting state로 전환될 때. (I/O request 대기)
2. process가 running state에서 ready state로 전환될 때. (Interrupt 발생)
3. process가 waiting state에서 ready state로 전환될 때. (I/O request 완료)
4. process가 terminate될 때. (종료)

1, 4는 자발적으로 내려오는 것이다 == 비선점(nonpreemptive)방식
2, 3은 비자발적으로 내려오는 것이다 == 선점(preemptive) 방식

(3이 비자발적인 이유 : I/O request를 완료해서 ready queue 내의 process가 n개에서 n+1개로 되었기 때문에 scheduling을 해야 함.)

Dispatcher

• Dispatcher :
  CPU Scheduling 기능에 포함된 하나의 요소이다.
  Dispatcher는 Short-term Scheduler가 선택한 process에게 CPU의 제어를 부여하는 module이고, 다음과 같은 작업을 한다.
  1. 한 process에서 다른 process로 context switching
  2. user mode로 전환
  3. program를 다시 시작하기 위해 user program의 적절한 위치로 jump.
     (PCB 중에 Program Counter가 그 위치를 알고 있음)
     
     
• 어떤 process를 memory에 올릴지 판단하는 것은 Short-term Scheduler.
  정해진 두 process를 memory에서 직접 올리고 내리게 하는 것은 Dispatcher.
  • example
    Scheduler : 3번 process 내려오고, 5번 process 내려가
    Dispatcher : 3번아 PCB saving하는거 도와줄게. 5번아 PCB loading하는거 도와줄게.

Dispatch Latency

• Dispatch Latency : Dispatcher가 하나의 process를 종료하고 다른 process를 실행시키기까지 소요되는 시간.
  • example >
    1, 4 : CPU가 실제 일하는 시간
    2, 3 : context switching을 위해 Dispatcher가 PCB를 saving, loading하는 시간 (CPU는 쉬는 시간)
    

dispatch가 자주 일어남
➡️ (PCB loading, PCB saving)쌍이 많아짐.
➡️ CPU는 새로운 process를 기다리는 시간이 길어짐.
➡️ 일을 못하는 시간이 길어짐.

Scheduling Criteria

• Scheduling할 때, 기준이 있어야 한다.
  1. CPU utilization : 사용 효율. 가능한 CPU를 바쁘게 해야 한다.
  2. Throughput : 처리율. 단위 시간당 처리되는 process 수.
  3. Turnaround Time : 반환시간. process를 실행하는 데 소요된 시간.
     (진입한 시간과 완료된 시간의 차이)
  4. Waiting Time : 대기시간. ready Queue에서 대기한 시간.
  5. Response Time : 응답시간. 작업을 요청한 후, 첫번째 응답이 올 때까지의 시간.
     
     
• 1, 2는 클수록 좋다.
  3, 4, 5는 작을수록 좋다.
  

Scheduling Algorithm

• Scheduling Algorithm : Ready Queue에 있는 어느 process에게 CPU core를 할당할 것인지를 결정하는 문제를 다룬다.

• I/O request 없이 순수 명령만 있는 process들에 대해서는 burst time을 정확히 예측할 수 있다.
  따라서 앞으로 다룰 Scheduling Algorithm의 burst time은 I/O request가 없는 process라고 가정한다.

5개의 Scheduling Criteria를 모두 적용하면 좋지만,
설명을 간단히 하기 위해, Waiting Time만 고려하여 Scheduling Algorithm을 공부한다.
(더 자세한 평가 기법은 Chap 5.8...)

FCFS Scheduling(First-Come, First-Served)

• FCFS :
  가장 간단한 CPU Scheduling 알고리즘이다.
  CPU를 먼저 요청하는 process가 CPU를 먼저 할당받는다. (선착순)
  FCFS는 Nonpreemptive Scheduling 방식이다.

• example :

  • 다음의 Burst Time을 갖는 process들이 존재한다.

  • process 도착 순서가 $P_1$, $P_2$, $P_3$ 순이라면, Gantt Chart는 다음과 같다.
    

  • 각 process들의 Waiting Time :
    $P_1$ Waiting time : 0
    $P_2$ Waiting time : 24
    $P_3$ Waiting time : 27

  • Average Waiting Time : (0 + 24 + 27) / 3 = 17

FCFS 단점 : Convoy Effect

• 만약 process 도착 순서가 바뀌어 $P_2$, $P_3$, $P_1$ 순이라면, Gantt Chart는 다음과 같다.
  

  • 각 process들의 Waiting Time :
    $P_2$ Waiting time : 0
    $P_3$ Waiting time : 3
    $P_1$ Waiting time : 6

  • Average Waiting Time : (0 + 3 + 6) / 3 = 3

Convoy Effect :
burst time이 오래 걸리는 process가 CPU를 양보할 때까지 다른 모든 process가 기다리는 현상.
$P_1$이 가장 먼저 처리되었을 때는 Average Waiting Time이 17이었다.
$P_1$이 가장 나중에 처리되었을 때는 Average Waiting Time이 3이었다.

SJF Scheduling(Shortest-Job-First)

• SJF :
  최단 작업 우선 알고리즘.
  사실 Shortest-Next-CPU-burst Scheduling이라는 용어가 더 적합하지만,
  이미 많은 책에서 SJF라는 용어를 사용하므로 SJF 용어를 사용한다.
  SFJ는 Nonpreemptive 방식이거나 Preemptive 방식일 수 있다.

Nonpreemptive SJF Scheduling

• Nonpreemptive SJF : 비선점형 SJF이기 때문에.
  Shortest Job을 먼저 실행하는데, process가 끝날 때까지 CPU에서 내려오지 않는다.

• example :

  • 다음의 Burst Time을 갖는 process들이 존재한다.

  • Nonpreemptive SJF Scheduling을 이용하면, 다음과 같은 Gantt Chart를 그릴 수 있다.
    

  • 각 process들의 Waiting Time :
    $P_4$ Waiting time : 0
    $P_1$ Waiting time : 3
    $P_3$ Waiting time : 9
    $P_2$ Waiting time : 16

  • Average Waiting Time : (0 + 3 + 9 + 16) / 4 = 7

Preemptive SJF Scheduling

• Preemptive SJF : 선점형 SJF이기 때문에.
  Shortest Job을 먼저 실행하는데,
  도착시간을 부여하여 process가 새로 도착할 때와 state transition이 있을 때마다,
  Scheduling을 해서 burst time이 Shortest Job을 CPU에 올리는 방식이다.

• example :

  • 다음의 Arrival Time, Burst Time을 갖는 process들이 존재한다.

  • Preemptive SJF Scheduling을 이용하면, 다음과 같은 Gantt Chart를 그릴 수 있다.
    

  • Average Waiting Time은 다음과 같이 구할 수 있다.
    

Shortest remaining time first

• Shortest remaining time first : 최소 잔여 시간 우선 scheduling이기 때문에.
  Shortest Job을 먼저 실행하는데,
  도착시간을 부여하여 process가 새로 도착할 때와 state transition이 있을 때마다,
  Scheduling을 해서 remaining time이 Shortest인 Job을 CPU에 올리는 방식이다.

• example :

  • 다음의 Arrival Time, Burst Time을 갖는 process들이 존재한다.

  • Preemptive SJF Scheduling을 이용하면, 다음과 같은 Gantt Chart를 그릴 수 있다.
    

  • Average Waiting Time은 다음과 같이 구할 수 있다.
    

Preemtive SFJ VS Shortest remaining time first

Preemtive SFJ는 burst time 중에서 shortest job을 선택.
Shortest remaining time first는 remain time 중에서 shortest job을 선택.

Determining Length of Next CPU burst

• SJF Scheduling은 남은 CPU burst time이 가장 짧은 process에
  우선순위를 부여하는 방식으로 동작하는데,
  CPU burst time을 정확히 알기 어렵기 때문에 추정을 해야 한다.
• 다음 CPU burst time을 예측하기 위한 수식은 다음과 같다.
  
  • $t_n$ : 이전 CPU burst time 실제값.
  • $\tau_n$ : 이전 CPU burst time 추정값.
  • $\tau_{n+1}$ : 다음 CPU burst time 추정값.
  • $\alpha (0 <= \alpha <= 1)$ : 임의 상수.
• example ($\alpha$ = 0.5로 가정)
  

• $t_0 = 6, \tau_0 = 10$
  $\tau_1 = 0.5 * t_0 + 0.5 * \tau_0 = 3 + 5 = 8$
  실제값 $t_1$ = 4 (불일치)
  
  
• $t_1 = 4, \tau_1 = 8$
  $\tau_2 = 0.5 * t_1 + 0.5 * \tau_1 = 2 + 4 = 6$
  실제값 $t_2$ = 6 (일치)
  
  
• $t_2 = 6, \tau_2 = 6$
  $\tau_3 = 0.5 * t_2 + 0.5 * \tau_2 = 3 + 3 = 6$
  실제값 $t_3$ = 4 (불일치)
  
  
  ....

  이런식으로 다음 CPU burst time을 예측해보고, 실제 측정을 해본다.
  실제 측정했던 과거의 값을 근거로 update해주기 때문에
  전체적으로 봤을 때는 비슷하게 흐름을 쫓아간다.

Priority Scheduling

• Priority Scheduling :
  process에게 priorty number(integer)를 부여하여
  우선순위가 높은 것부터 scheduling한다.
  (우선순위가 0이 높은지? 9가 높은지? 는 OS마다 다르다.)
  (이 책에서는 priority integer가 작을수록 우선순위가 높다고 가정한다.)

• process를 만들 때,
  user 또는 OS가 priority number(integer)를 할당해준다.

• Starvation : 우선순위가 너무 낮아서 새로운 process에게 밀리고 밀려서 계속 실행하지 못하는 현상.

• Aging : Starvation을 해결하기 위해 대기하는 process의 우선순위를 점진적으로 증가시켜준다.

• example :

  • 다음의 Burst Time, Priority을 갖는 process들이 존재한다.
    

  • Priority Scheduling을 이용하면, 다음과 같은 Gantt Chart를 그릴 수 있다.
    

  • Average Waiting Time은 다음과 같이 구할 수 있다.
    $P_1$ waiting time : 6
    $P_2$ waiting time : 0
    $P_3$ waiting time : 16
    $P_4$ waiting time : 18
    $P_5$ waiting time : 1
    ➡️ Average Waiting Time = (6 + 0 + 16 + 18 + 1) / 5 = 8.2

RR Scheduling(Round-Robin)

• Round Robin :
  process마다 time quantum(time slice)을 할당하여
  그 시간동안만 실행할 수 있도록 한다.
  실행되었으면 다시 가장 뒤로 가야 하기 때문에 Ready Queue는 Circular Queue로 동작한다.
  (대부분)

• example : Time Quantum = 20 이라고 가정.

  • 다음의 Burst Time을 갖는 process들이 존재한다.
    
  • RR Scheduling을 이용하면, 다음과 같은 Gantt Chart를 그릴 수 있다.
    
  • Average Waiting Time은 다음과 같이 구할 수 있다.
    $P_1$ waiting time : 0 + 55 + (121 - 97) = 79
    $P_2$ waiting time : 20
    $P_3$ waiting time : 37 + (97 - 57) + (134 - 117) = 94
    $P_4$ waiting time : 57 + (117 - 77) = 97
    ➡️ Average Waiting Time = (79 + 20 + 94 + 97) / 4 = 72.5

Turnaround Time with Time Quantum

• 문제 1 : 다음과 같은 Process가 있을 때,
  Time Quantum에 따른 Turnaround Time을 구해보고,
  어떠한 Time Quantum을 사용하는 것이 좋을지 확인해보시오.
  (Turnaround time : terminate 시간 - arrival time)
  (여기서는 도착 시간을 모두 0으로 한다.)
  

  • time quantum이 커진다고 해서 좋아지고, 나빠지는 것이 아니다.
    time quantum이 작아진다고 해서 좋아지고, 나빠지는 것이 아니다.
    time quantum에 대해서 turnaround time이 변하긴 하지만,
    비례와 반비례 같은 유사관계는 없다.
  • 풀이 :
    Time Quantum = 1일 때, Average turnaround time이 가장 작으므로
    1, 2, 5 중에서는 1로 설정하는 것이 좋다.
    
    

• 문제 2 : 다음과 같은 process가 있다.
  Q=4일 때와 Q=20일 때의 average turnaround time을 비교하라.

  • 풀이 :

FCFS VS RR

다음 예제에서 FCFS도, RR도 162만큼 걸린다.

FCFS는 비효율적인 scheduling방식이었다.
하지만 실제로는 FCFS가 더 먼저 끝나고, RR이 좀 더 늦어질 것이다.
왜 그럴까?

➡️ RR은 Time Quantum마다 dispatching이 일어난다.
상대적으로 FCFS보다 dispatching이 더 많이 일어난다.
dispatch가 일어나면, dispatch latency가 더 많이 존재하기 때문에
RR이 실제로는 더 느리게 된다.

➡️ 굳이 따지자면 RR이 수치적으로 더 늦는데,
우리는 그렇게 느끼지는 않는다.
왜냐하면 RR은 Time Quantum에 따라 scheduling되기 때문에
User들은 process들이 동시에, 나란히 잘 돌아가는 것처럼 보일 것이다.
Time Quantum=1이면, 모든 process가 동시에 돌아가는 것처럼 보이지만
dispatch latency가 매우 많이 일어나기 때문에 비효율적이다.

➡️ process 수행 속도 단위와 latency 속도 단위가 비슷하다면 context switch가 늘어나는 것을 무시하지 못한다.
현재로서는 두 속도 모두 mill, micro 단위로 비슷하기 때문에 Context Switch가 많은 것을 무시할 수 없다.

➡️ 게다가 process가 너무 많아서 Swap out 되어 memory에서 HDD로 갔다가
CPU를 할당받아서 다시 memory로 올라갈 때 매우 느려진다.
(HDD는 아주 빨라야 milli 단위이다.)
따라서 RAM 용량이 작은데 process가 너무 많아서 process가 HDD로 swap out되었다면,
dispatch latency가 micro 단위에서 mill 또는 sec 단위까지도 늘어날 수 있다.

Priority Scheduling with RR

• Priority Scheduling with RR : 우선순위 대로 scheduling을 하되, 우선순위가 같은 process들끼리 RR을 적용.
  (Stravation 현상이 없도록 Aging을 적용할 수도 있다.)
  

  • Time Quantum=2, 풀이 :
    

Multilevel Queue Scheduling

• Multilevel Queue Scheduling :
  우선순위가 같은 process들끼리 queue로 묶어
  그 안에서 다른 방식의 Scheduling을 사용하는 것.
  

Multilevel Feedback Queue Scheduling

• Multilevel Feedback Queue Scheduling :
  Multilevel Queue Scheduling도 우선순위가 낮은 process들은
  Starvation 현상을 겪을 수 있다는 문제점이 발생한다.
  process가 짧은 애들이 있으면 빨리 보내줘야 공평할 수도 있으니까
  time burst가 작은 process들을
  Quantum=8인 queue에 할당.
  Quantum=8을 거쳐 남은 process들은 burst time이 큰 process들이니까
  Quantum=16 queue에 할당.
  Quantum=16을 거쳐도 남아있는 process 있다면?
  그냥 FCFS로.. (Quantum이 커진다는 의미는 FCFS와 같아진다는 의미)
  이런식으로 각각의 Level마다 각각의 기준을 부여해주는 Scheduling 방식.
  

Multi-Processor Scheduling

• 우리가 지금까지 봤던 것은 single-core processor에서의 Scheduling이었다.
  Single-core processor의 scheduling도 어렵기 때문에 일반적인 교과목에서는
  대부분 Single-core processor의 scheduling의 내용을 다룬다.

• 하지만 현재 computer는 Multi-core가 대부분이다.
  Multi processor도 있다.

• 만약 여러 개의 CPU가 사용 가능하다면, 여러 thread가 병렬로 실행될 수 있으므로 load sharing(부하 공유)가 가능하다.

• 그러나 문제는 그에 상응하여 더욱 복잡해진다.
  CPU가 2개 이상이 된다고 해도,
  system에는 bus가 하나 밖에 없어서
  생각처럼 간단히 되는 문제가 아니다.

Approaches to Multiple-Processor Scheduling

Homogeneous Processor

• Homogeneous Processor :
  같은 종류의 processor로 multi processor를 구성한다.
  우리는 앞으로 Homogeneous Processor라고 가정하고 Multi processor sheduling을 공부한다.

앞으로의 Multi Processor 내용은 Homogeneouse Processor라고 생각하면 된다.

SMP

• Multi-Processor를 갖고 Multiple Processing할 때, SMP 방식과 ASMP 방식이 있다.

• 일반적으로 Multi-Processor는 SMP 방식을 사용한다.

• SMP(Symmetric Multi-Processing) :
  각 processor는 스스로 scheduling할 수 있다.
  각 processor의 scheduler가 Ready Queue를 검사하고,
  실행할 thread를 선택하여 Scheduling이 진행된다.

  • Scheduling 대상이 되는 thread를 관리하기 위한 두 가지 전략이 있다.
  1. 모든 thread나 Common Ready Queue에 있을 수 있다.
  2. 각 processor는 자신만의 thread queue를 가질 수 있다.
     

• ASMP(Asymmetric Multi-Processing) :
  각 processor에 각각의 작업이 따로 정해져있다.

  • ASMP는 왜 만들어졌는가?
    Windows OS에서 core가 여러 개 있을 때,
    "이 core에는 이 program만 할당하겠다."라는 설정을 할 수 있다.
    SMP를 마치 ASMP처럼 사용할 수 있도록 옵션을 부여할 수도 있다.

앞으로의 Multi Processor 내용은 SMP 방식이라고 생각하면 된다.

Processor Affinity

• 한 개의 proessor에서 두 개의 process가 있다고 가정하자.
  ➡️ 한 processor 내에 process들이 존재하기 때문에
  context switching이 일어날 것이고,
  CPU는 그러한 context를 기억하고 저장할 것이다.

• 하지만 하나의 process가 다른 processor에 할당됐다가, 또 다른 processor에 할당됐다가.. 이런 식으로 scheduling이 된다면?
  context 뿐만 아니라 데이터들을 모두 옮기고 캐시도 없애야 해서 효율이 매우 떨어진다.

  • 캐시를 안쓰면 되지 않는가?
    그럴 수도 있지만 캐시는 바깥에 있는 bus를 쓰지 않도록
    processor 근처에 다음 명령어를 갖다 놓는 역할을 하니까
    캐시를 안쓰게 된다면 CPU는 매 명령마다 bus를 사용해야 되므로 효율이 매우 떨어질 것이다.

• 따라서 각각의 Processor들은 서로의 processor와 그 process들 간의Affinity(친화성)를 유지해줄 필요가 있다.
  그렇게 해서 Bus를 덜 쓰게 함으로써 효율을 높일 수 있기 때문에.
  • hard affinity : process가 특정 CPU에만 실행되도록 강제하는 방법
  • soft affinity : process가 특정 CPU에만 실행되도록 권장하는 방법

따라서 process는 되도록 하나의 CPU에서 실행되도록 해주는 Affinity가 필요하다.
하지만 특정 CPU만 바쁘게 해서는 안되고, 모든 CPU가 균등하게 바빠야 한다는 전제이다.

Load Balancing

• Multiple-Processor Scheduling의 지향점은
  특정한 processor만 바쁘고 나머지는 쉬는 것이 아니라,
  모든 processor가 골고루 Task를 나눠서 균등하게 바빠야 하는 것이다.
  이러한 개념을 Load Balancing이라고 한다.

  • network에서도 Load Balancing이라는 개념이 있다.
    Server가 DDos 공격에 대비하기 위해 Server 앞단에 Load Balancer가 있다.
    Load Balancer는 접속을 균등하게 분배해준다.

• 하나의 큰 Common Ready Queue가 있어야
  모든 CPU들이 Task들을 공유할 수 있고, Balance를 맞출 수 있다.
  

Load Balancing & Affinity

• SMP system에서 processor가 하나 이상이라는 것을 최대한 활용하려면,
  부하를 모든 processor에 균등하게 배분하는 것이 중요하다.
  Load Balancing을 위해서는 push와 pull, 두 가지 migration이 있다.

  • push migration : 주는 것.
    특정 task가 주기적으로 각 processor의 부하를 검사하고
    만일 불균형 상태로 밝혀지면 과부하인 processor에서 쉬고 있거나
    덜 바쁜 processor로 thread를 이동시킴으로써 부하를 분배.
  • pull migration : 가져오는 것.
    쉬고 있는 processor가 바쁜 processor를 기다리고 있는 process를 가져온다.

• Push와 Pull migration이 발생하는 순간
  == affinity(CPU에 있는 정보, context, cache)가 없어진다.

  Push, Pull Migration은 Load Balancing을 위해서 하는데
  Push, Pull Migration으로 인해 Affinity가 떨어진다.
  따라서 Load Balancing과 Affinity는 병립할 수 없다.

NUMA

• NUMA를 쓰는 이유
  1. CPU는 memory에서 data를 가져온다
  2. CPU는 가져온 data 분석 (명령어인지? data인지?)
     사실은 CPU는 이 data가 명령어인지 data인지 모른다.
     처음에는 명령어라고 생각하고, 그 명령어가 data를 필요로 한다면 data로 생각한다.
  3. data를 읽어오거나 그 다음 명령어를 읽거나 하기 위해 memory에 접근한다
     
     
  • CPU idling :
    memory에서 data를 읽어오는 clock은 CPU가 일하는 clock에 비해
    매우 느리기 때문에 CPU가 쉬는 시간이 생긴다.
    이렇게 main memory에서 data를 가져오는 것을 줄여보고자 cache를 썻던 것이다.
    ➡️ CPU 안(L1) 또는 CPU 밖(L1) 또는 memory 안(in-memory) 등등 여러 종류의 Cache를 만든다.

    여러 개의 CPU가 하나의 memory에 bus를 통해 액세스해야 하기 때문에
    CPU가 많으면 많을수록 bus에 병목현상이 커질 것이고, 이는 성능 손실.
    그래서 HW적 보완방법으로 NUMA 시스템이 존재

• NUMA(Non-Uniform Memory Acces) :
  CPU와 memory를 하나인 것처럼 묶어서 node 구조로 만든다.
  각각의 CPU의 자신의 local memory에 빠른 접근이 가능하다.
  또한 다른 CPU의 local memory에도 접근이 가능하지만, 일반 bus를 사용하므로 느리다.
  
  

Multicore Processors

• Multicore Processor는 앞서 살펴본 Multi-Processor와는 다르다
  하나의 CPU HW 안에 여러개의 core가 있고, core마다 쓸 수 있는 thread가 있다.

• Multicore Processor는 Multi-Processor와 달리 CPU와 하나 밖에 없으니까 HW적 구성이 단순하다.

• Multicore Processor는
  Multi-Processor보다 성능 효율은 조금 떨어지지만, 전력 효율은 높다.

Multicore Processor는 Multi Processor보다 HW 구성이 훨씬 더 간단해지고,
더 저렴하게 Multi Processor인 것처럼 사용할 수 있다.

Multithreaded Multicore System

• Singlethreaded Singlecore System
  

  • C : computing cycle = 이 시간 동안 CPU가 일 처리
  • M : memory stall cycle = memory를 쓰는 시간이라 CPU가 멈추고 기다리는 cycle
    ➡️ 위와 같이 Memory cycle에서는 CPU는 멈추고 기다리기 때문에
    Memory Stall에서는 위에서 보듯이 cache를 아무리 잘 써도 약 50%의 정도의 효율이 저하될 수 있다.

• Multithreaded Multicore System
  
  ➡️ thread 1 이 CPU쓸 때, thread 0이 Memory cycle..
  thread1, 2는 효율적으로 번갈아가며 bus를 사용한다.
  memory도 효율적으로 쓸 수 있고, CPU도 효율적으로 사용할 수 있다.

Real-Time CPU Scheduling

• Real-Time Scheduling :
  Periodic한 process들을 scheduling한다. (끝날 때 끝이 나야 한다)
  또한 우선순위 기반 Scheduling이어야 한다.

• hard real-time : deadline 안에 반드시 수행해야 하는 system

• soft real-time : deadline 안에 반드시 수행한다는 보장이 없는 system

Minimizing Latency

• Real-time Scheduling은 Latency를 최소화해야 한다.
• Real-time Scheduling을 하기 위해 고려해야 할 Latency 종류

1. Interrupt Latency :
   CPU에 interrupt가 발생한 시점부터 해당 ISR을 사용하여 interrupt를 처리하기 전에
   현재 수행 중인 process의 상태를 저장하고 context switching이 발생해야 한다.
   이러한 작업을 모두 수행하는 데 걸리는 시간.
   

2. Dispatch Latency :
   Dispatcher가 하나의 process를 block시키고 다른 process를 시작하는 데까지 걸리는 시간.
   

   • conflict 단계 :
     1. kernel에서 동작하는 process를 선점하는 데 걸린 시간
     2. 높은 우선순위의 process가 필요한 자원을 낮은 우선순위 process 자원이 방출
        (자원회수)
   • Dispatch 단계 : 우리가 알고 있는

Priority-Based Scheduling

• Real-Time System은 Periodic하다.
  

  • t : 실제 CPU를 차지하여 처리되는 시간
  • d : deadline. process가 끝나야 되는 시간.
  • p : period. period가 반복되며 process가 실행된다.
    ➡️ $0<= t <= d = p$ 이다.
    ➡️ Rate of periodic task (실행 빈도) : $1/p$

• Scheduler는 이러한 p, d, t 시간 사이의 관계를 이용하여
  deadline과 Rate of periodic process에 따라서 우선순위를 정한다.
  따라서 승인 제어(admission-control) 알고리즘을 이용해서
  Scheduler는 deadline 이내에 완수할 수 있는 process는
  실행을 허락하고 그렇지 못한 경우에는 요구를 거절한다.

Rate-Monotonic Scheduling

• Rate-Monotonic Scheduling :
  Rate($1/p$)에 비례해서 scheduling하는 기법. ($p$=period)
  • $p$가 크다 == 주기가 길다 == 급하지 않다 == $1/p$가 작다
  • $p$가 작다 == 주기가 짧다 == 급하다 == $1/p$가 크다
• Rate(1/p)가 클수록 Priority가 높다.
  

CPU Utilization에 의한 Real-Time Scheduling 충분 조건

• 필요조건 : 어떤 결과를 만족시키기 위해 반드시 충족되어야 하는 조건.

  • ex) "눈이 와야 스키를 탈 수 있다."
    ➡️ 눈이 반드시 와야 스키를 탈 수 있기 때문에, 눈은 필요조건이다.
    따라서 "눈이 온다"는 스키의 필요조건이다.

• 충분조건 : 어떤 결과를 만족시키는데 충분한 조건. 반드시 충족되어야 하는 것은 아니다.

  • ex) "고등학교를 졸업하면 대학교에 진학할 수 있다"
    ➡️ 고등학교를 졸업하면 대학교에 진할 할 수 있지만, 꼭 고등학교를 졸업해야만 대학교에 진학할 수 있는 것이 아니다.
    따라서 "고등학교 졸업"은 대학교 진학의 충분조건이다.

• CPU Utilization에 의한 Real-Time Scheduling 충분 조건 :
  

따라서 위의 식을 만족하지 않는다고 해서 Real-Time Scheduling을 할 수 없는 것이 아니라
Real-Time Scheduling을 하지 못하는 process set들은 위의 식을 만족하지 못하는 것이다.
아래의 Example 1, Example 2, Example 3을 살펴보자.

Rate-Monotonic Scheduling (cont)

• Example 1 :
  두 개의 process $P_1$, $P_2$가 있다고 하자. (n=2)
  각 process의 주기 : (50, 100)
  각 process의 수행 시간 : (20, 35)
  (각 process의 deadline은 다음 period가 시작하기 전까지이다.)
  

  • 두 process가 모두 deadline을 충족시키도록 Scheduling이 가능한가?
    ➡️ rate of period = (1/50, 1/100) 이므로 $P_1$의 우선순위가 더 높다. 0~20 : $P_1$ 실행 ➡️ (20 수행 : 수행시간 완료, $P_1$ 0 남음) ➡️
    20 ~ 50 : $P_2$ 실행 ➡️ (30 수행 : $P_1$의 period, $P_2$ 5 남음) ➡️
    50 ~ 70 : $P_1$ 실행 ➡️ (20 수행 : 수행시간 완료, $P_1$ 0 남음) ➡️
    70 ~ 75 : $P_2$ 실행 ➡️ (5 수행 수행시간 완료, $P_2$ 0 남음) ➡️
    75~100 : $P_1$, $P_2$ deadline이 지나지 않았기 때문에 대기

    Example 1은 두 process $P_1$, $P_2$가 deadline 안에 수행이 완료되었다.
    CPU Utilization : $U = \Sigma_{i=1}^{n=2} \frac{C_i}{T_i} \le n(\sqrt2 - 1)$
    $U = (\frac{20}{50} + \frac{35}{100} \le 0.828..)$ $=( 0.75 \le 0.828..)$
    CPU Utilization 충분조건을 만족하고, Real-Time Scheduling도 만족한다.

• Example 2 :
  두 개의 process $P_1$, $P_2$가 있다고 하자. (n=2)
  (Example 1에서 $P_1$의 수행 시간만 20에서 25로 변경되었다.)
  각 process의 주기 : (50, 100)
  각 process의 수행 시간 : (25, 35)
  (각 process의 deadline은 다음 period가 시작하기 전까지이다.)
  

  • 두 process가 모두 deadline을 충족시키도록 Scheduling이 가능한가?
    ➡️ rate of period = (1/50, 1/100) 이므로 $P_1$의 우선순위가 더 높다. 0~25 : $P_1$ 실행 ➡️ (25 수행 : 수행시간 완료, $P_1$ 0 남음) ➡️
    25 ~ 50 : $P_2$ 실행 ➡️ (25 수행 : $P_1$의 period, $P_2$ 10 남음) ➡️
    50 ~ 75 : $P_1$ 실행 ➡️ (25 수행 : 수행시간 완료, $P_1$ 0 남음) ➡️
    75 ~ 85 : $P_2$ 실행 ➡️ (10 수행 : 수행시간 완료, $P_2$ 0 남음) ➡️
    85~100 : $P_1$, $P_2$ deadline이 지나지 않았기 때문에 대기

    Example 1은 두 process $P_1$, $P_2$가 deadline 안에 수행이 완료되었다.
    CPU Utilization : $U = \Sigma_{i=1}^{n=2} \frac{C_i}{T_i} \le n(\sqrt2 - 1)$
    $U = (\frac{25}{50} + \frac{35}{100} \le 0.828..)$ $=( 0.85 \le 0.828..)$
    Real-Time Scheduling이 가능해서 보니까 CPU Utilization 충분조건을 만족하지 않는다.
    앞서 충분조건설명에서 말했듯이,
    CPU Utilization 충분조건을 만족하지 않았다고 해서 Real-Time Scheduling이 불가능한 것은 아니다.

• Example 3 :
  두 개의 process $P_1$, $P_2$가 있다고 하자.
  각 process의 주기 : (50, 80)
  각 process의 수행 시간 : (25, 35)
  (각 process의 deadline은 다음 period가 시작하기 전까지이다.)
  

  • 두 process가 모두 deadline을 충족시키도록 Scheduling이 가능한가?
    ➡️ rate of period = (1/50, 1/80) 이므로 $P_1$의 우선순위가 더 높다.

    0~25 : $P_1$ 실행 ➡️ (25 수행 : 수행시간 완료, $P_1$ 0 남음) ➡️
    25 ~ 50 : $P_2$ 실행 ➡️ (25 수행 : $P_1$의 period, $P_2$ 10 남음) ➡️
    50 ~ 75 : $P_1$ 실행 ➡️ (25 수행 : 수행시간 완료, $P_1$ 0 남음) ➡️
    75 ~ 80 : $P_2$ 실행 ➡️ (5 수행 : $P_2$의 deadline, $P_2$ 5 남음) ➡️
    ($P_2$는 deadline이 지났는데도 수행 시간이 5 남음 == Real-Time Scheduling 불가능)

    Example 3는 $P_2$가 deadline 안에 수행완료되지 못했으므로 Real-Time Scheduling이 불가능하다.
    CPU Utilization : $U = \Sigma_{i=1}^{n=2} \frac{C_i}{T_i} \le n(\sqrt2 - 1)$
    $U = (\frac{25}{50} + \frac{35}{80} \le 0.828..)$ $=( 0.9375 \le 0.828..)$
    Real-Time Scheduling이 불가능해서 보니까 CPU Utilization 충분조건을 만족하지 않는다.

• Example 1, Example 2, Example 3 정리

1. CPU Utilization 충분조건을 만족하지 않는다고 해서 Real-Time Scheduling이 불가능한 것이 아니다.
2. Real-Time Scheduling이 불가능하면 CPU Utilization 충분조건을 항상 만족하지 못한다.

Earliest Deadline First Scheduling (EDF)

• Example 3에서 $P_2$가 deadline 안에 자신의 수행을 끝내지 못한 이유는?
  ➡️ Rate of Period만으로
  즉, Period만을 Priority 판단 기준으로 세웠기 때문이다.

• 해결 방법은?
  ➡️ SJF에서 Shortest Remaining Time First로 보완했던 것처럼
  Earliest Deadline First Scheduling(EDF Scheduling).
  즉, deadline이 짧을수록 Priority를 높게 준다.
  deadline이 얼마 남지 않은 process를 먼저 실행시켜준다.

• Example :
  두 개의 process $P_1$, $P_2$가 있다고 하자.
  각 process의 주기 : (50, 80)
  각 process의 수행 시간 : (25, 35)
  (각 process의 deadline은 다음 period가 시작하기 전까지이다.)
  

  • EDF Scheduilng으로 변경했을 때,
    두 process가 모두 deadline을 충족시키도록 Scheduling이 가능한가?

    ($P_1$의 deadline = 50 < $P_2$의 deadline = 80 이니까 $P_1$실행.)
    ➡️ 0 ~ 25 : $P_1$ 실행. (수행 완료)
    ➡️ 25 ~ 50 : $P_2$ 실행. ($P_1$의 Period. $P_2$는 10 남음)
    ($P_1$의 deadline = 100 > $P_2$의 deadline = 80 이니까 $P_2$ 마저 실행)
    ➡️ 50 ~ 60 : $P_2$ 실행. (수행 완료)
    ➡️ 60 ~ 80 : $P_1$ 실행. ($P_2$의 Period. $P_1$는 5 남음)
    ($P_1$의 deadline = 100 < $P_2$의 deadline = 160 이니까 $P_1$ 마저 실행)
    ➡️ 80 ~ 85 : $P_1$ 실행. (수행 완료)
    ➡️ 85 ~ 100 : $P_2$ 실행. ($P_1$의 Period. $P_2$는 20 남음)
    ($P_1$의 deadline = 150 < $P_2$의 deadline = 160 이니까 $P_1$ 실행)
    ➡️ 100 ~ 125 : $P_1$ 실행. (수행 완료)
    ➡️ 125 ~ 145 : $P_2$ 실행. (수행 완료)

    ($P_1$의 deadline = 150 < $P_2$의 deadline = 160 이니까 $P_1$ 실행해야 하는데,
    150까지 시간 남으니까 기다림)

CPU Utilization이 1 이하이면 EDF Scheduling로 Real-Time Scheduling을 보장할 수 있다.

CPU Utilization : $U = \Sigma_{i=1}^{n=2} \frac{C_i}{T_i}$
$U = (\frac{25}{50} + \frac{35}{80} \le 1)$ $=( 0.9375 \le 1)$
Example에서의 CPU Utilization은 1 이하이기 때문에
EDF Scheduling으로 Real-Time을 보장할 수 있다.

---

Algorithm Evaluation

• 특정 시스템을 위한 CPU Scheduling algorithm은 어떻게 선택하는가?
  ➡️ 수많은 Scheduling Algorithm이 있으며 각각 자신의 매개변수를 갖고 있다.
  그 결과, 알고리즘을 선택하는 것은 매우 어려운 일이다.

우리가 사용할 수 있는 여러 가지 평가 방법이 있다.

1. Deterministic Modeling :
   사전에 정의된 특정한 작업 부하를 받아들여 그 작업 부하에 대한 각 알고리즘 성능을 정의하는 방법.

2. Queueing Models : Little's Law

   • $(공간 내에 머무는 개체수) = (유입량 * 머무는 시간)$ ➡️ 회전율 측정 가능
     $(동시에 처리할 수 있는 수) = (처리율 * 처리응답시간)$
   • ex)
     동시에 처리할 수 있는 수 = 14 processes
     처리율 = 7 processes/sec
     처리 응답 시간? 2 sec

3. Simulation : 가상으로 만들어서 돌려보는 것.

4. Implementation : 직접 실행해보는 것. (high cost, high risk, environment vary)