3. 운영체제 Scheduling

CPU 가상화가 뭐에 관한 거였지?

• Time sharing
• Context switching
• Scheduling policy

=> 아무튼! OS가 제어권을 유지하면서 성능이 저하되지 않도록 유지 하는 것.

 

Direct Execution

OS가 프로그램에게 제어권을 넘기면 프로세서에서 실행되는 것

프로그램이 악성이 아님이 보장되어야 함

=> 악의적 사용을 막기 위해 CPU를 Kernel mode와 User mode를 나눔. 프로세스에는 일부 권한만 주려는 의도.

 

System Calls

• 프로세스는 시스템콜을 통해 제어권을 요청할 수 있음
• OS는 trap table(syscall table)을 이용해 trap handler를 저장함 → 부팅시 생성됨
• 프로세스가 시스템콜을 사용하려면 trap 명령어를 먼저 실행해야 함

시스템콜 과정

 

System call vs Function call

생긴건 비슷하지만, 시스템콜은 trap 명령어를 포함하고 있어서 커널모드에서 실행되고 펑션콜은 유저모드에서 실행됨

 

프로세스 운영 방식

Timer Interrupt

• OS가 주기적으로 제어권을 뺏어옴
• timer interrupt발생시 중지된 프로세스 정보는 메모리(PCB)에 저장됨

Job Scheduling

• 프로세스를 job 또는 workload 라고도 부름
• 스케줄링은 "What to run next?"의 문제

Context Switching

• 스케줄링을 통해 다른 프로세스로 전환하는 것을 context switching 이라함

Timer Interrupt와 Context Switching 과정

 

---

이제부터는 스케줄링에 관한 내용이라 줄을 그었다.

 

Scheduling Metrics

• Turnaround Time : job의 완수 시간 - 도착시간
  스케줄러가 얼마나 빠르게 job을 끝낼 수 있는가
  

  

• Response Time : job의 처음 실행시간 - 도착시간
  터미널 커맨드 같은데서 더 중요한 메트릭
  

  

• 둘은 trade-off 관계

 

Scheduling Policy

1. First In First Out (FIFO)

• 먼저 도착한 job을 먼저 처리
• 만약, 모든 job들이 동시에 도착한다면?
  1) A, B, C 모두 20ms
  

  

  2) A는 80ms B,C는 20ms
  

  

  
  
  
• Convoy Effect 발생 : 짧은 job이 긴 job의 종료를 기다리는 현상

 

2. Shortest Job First (SJF)

• 짧은 job을 먼저 처리
  

  

• 하지만 여전히 Convy Effect는 남아있음
  A 80ms가 도착한 후에 B, C가 도착하는 경우
  

  

3. Shortest Time-to-Completion First (STCF)

• 남은 실행 시간이 짧은 job으로 context switching
  

  

4. Round Robin (RR)

• 하나의 job이 끝날 때까지 실행하지 않고, time slice마다 스케줄링하여 큐에 있는 다른 job으로 context switching
• response time을 줄이고, context switching시 발생하는 오버헤드를 줄이기 위한 적당한 time slice를 설정해야 함
  

  

---

그러나 실제 OS는 job들의 런타임 정보를 사전에 알 수 없다.

또한, turn-around time, response time 두 개 모두 최적화 하기에는 위의 스케줄링 방법들은 trade-off가 있다.

→ Multi Level Feedback Queue

 

Multi Level Feedback Queue

• queue가 여러개라는 의미
  • 그리고 이 큐들에는 우선순위가 있음
• 매 time slice 마다 우선순위를 통해 job을 결정
• 그 우선순위는 관측된 job의 behavior를 통해 결정됨
  • ex) 키보드 인풋을 기다리기 위해 CPU를 계속 포기하는 job은 interactive job일 것이므로 우선순위 up
  • ex) 긴 시간동안 CPU를 사용하는 job은 우선순위 down
• 단, 같은 우선순위에서는 RR!

 

Job Scheduling in MLFQ

1. 우선순위가 A>B라면, A를 run
2. 우선순위가 A=B라면, A와 B는 RR로 실행
3. 새로운 job이 들어오면, 가장 높은 우선순위로
4. job이 주어진 time slice를 소진하면 한 큐 위로
5. job이 주어진 time slice를 소진하지 않으면 현재 큐를 유지

single long-running job

long job A와 short job B

I/O intensive jobs

 

Starvation Problem

• interactive job들이 많으면, 낮은 큐에 있는 job들은 run을 할 수 없음

 

Priority Boosting

• 주기적으로 모든 job들을 가장 높은 우선순위로 옮김
• 옮겨진 후에는 RR
• boosting 주기가 길면 starvation / 짧으면 interactive가 힘듦

 

Accounting

• job이 time slice 직전에 끝나도록 설계되면 CPU독점이 발생함
  

  

• 따라서, time slice 기준으로 낮추는 것이 아니라. 각 job에 할당된 time allotment를 기준으로 낮춤
• job의 run time을 계속해서 accounting(계산)한다는 의미

 

MLFQ 정리 - parameters

1. 우선순위 레벨의 수
2. time slice 간격
3. boosting 주기
4. time allotment (Accounting에 필요한)

 

---

Fair-Share Scheduling (공정배분)

• 같은 말로 proportional share(비례배분)
• 각 job들은 tickets를 CPU time에 비례해서 배정 받음
• 그리고나서 랜덤한 숫자가 지정되고, 그 숫자에 해당하는 ticket counts를 가진 job을 실행

 

Stride Scheduling

• stride = 큰 수를 지정하고, 그 수를 ticket counts로 나눈 값
• stride가 가장 작은 값이 next job이 되고 실행되면 stride를 더해감