실버벨의 Stack Overflow

#5-3. CPU SCHEDULING

cf> 여태까지 스케줄링은 큐에서 한줄서기를 하면서 cpu사용을 기다려 왔지만,

      Multilevel queue와 Multilevel feedback queue는 여러줄 서기를 할 수 있다!!

* Multilevel Queue

# 밑에 그림을 통해 우선순위를 알수 있다.
: 맨 위에 줄이 우선순위가 높으며, 밑으로 갈수록 우선순위가 낮아진다.

# system process : 시스템과 관련된 일을 하는 프로세스
  interactive Process: 사람하고 관련된 일을 하는 프로세스
  interative editing process : 그것보다는 살짝 인터렉션이 떨어지는 프로세스
  batch process : cpu만 오랫동안 사용하는 프로세스를 여기서는 batch process라고 얘기를 하는것 같다.
  student process : 학생을 무시하는건가....?

=> 여기는 완전 계급제!
 즉, 맨 위에 부터 비어있나 확인을 해서 밑으로 내려간다. 밑에 있는 프로세스는 영원히 cpu할당을 못 받을 수 도 있다.(starvation 발생)

cf> 반면에!!
Multilevel Feedback Queue는 완전 계급제는 아니다. 방탕하게 살면 우선순위가 떨어지기도 하고 열심히 살면 우선순위가 올라가기도 한다!!

 (다음에 나오는 Multilevel Feedback Queue 그림 참고하기!!)

# 고려해야 할점?

 - Ready queue를 여러 개로 분할
  v. foreground (interactive)
  v. background (batch-no human interaction)

 - 각 큐는 독립적인!! 스케줄링 알고리즘을 가짐.
  v. foreground  => RR
  v. background  => FCFS

 # 줄에 특성에 맞는 queue별 스케줄링을 채택! (이렇게 채택된 이유를 알겠지?)

 - 큐에 대한 스케줄링이 필요
  v. Fixed priority scheduling
    # 이 방식은 우선순위를 아주 강하게 주어 우선순위만을 사용하는 방식인데, 이렇게 되면 우선순위가 낮은 프로세스들은 starvation이 발생한다. 이에대한 해결책이 Time slice!!

  v. Time slice

  - 각큐에 CPU TIME을 적절한 비율로 할당
     ex> 우선수위 높은 RR은 80%주고, 낮은 FCFS는 20%주고!

* Multilevel Feedback Queue

# (Multilevel queue와 비교하여)고려해야될 점
(사진의 빨간색 글씨 부분들!!! (중요!))

# 우선순위가 높으면 RR의 quantum을 짧게 해주며, 우선순위가 낮아질수록 quantum을 높여줘서 나중에는 FCFS가 되게끔 한다.

-----------------------------------------------------------------------------------------------------------------------
# 여기까지는 CPU가 하나일때의 CPU SCHEDULING 이었다면, 지금부터의 내용은
CPU가 여러개 일 경우,
Thread가 여러개일 경우,
등등 특이한 case의 cpu스케줄링을 알아 보겠습니다.

* Multiple-Processor Scheduling
: 이 부분은 화두만 보고 넘어가자!

# Load sharing : 하나의 줄에만 부하되는것을 막는 것.

# Symmetric Multiprocessing : cpu가 모두 대등한 것.

# Asymmetric Multiprocessing : 하나의 cpu가 컨트롤을 담당하고 나머지가 그 cpu를 따르는 것.

* Real-Time Scheduling
: 반드시 데드 라인을 보장해야 한다.

# 그때 그때 스케줄링하기보다는 real time job들이 정해져 있고, 그것들을 미리 스케줄링해서 데드라인이 보장되도록 적재적소에 배치되도록 하는 그런 시스템을 쓰고 있다.

cf> real time job : dead라인이 있는 job!
    (정해진 시간안에 완료해야하는 작업이 있는 job)

# hard는 데드라인이 꼭 지켜져야 하고
  soft는 데드라인을 지켜야하는 의무가 좀더 부드럽다.

* Thread Scheduling

cf> Thread : 프로세스 하나 안에 cpu 수행단위.

# User level Thread : 사용자 프로세스가 직접 쓰레드를 관리하고 os는 그 쓰레드를 모르는 상황. => 그래서 os가 프로세스에게 cpu사용권을 주면 그 프로세스 내에서 어떤 쓰레드에게 cpu사용권을 줄지를 결정하는 것. => "Local Scheduling"

# Kernel level Thread : os가 쓰레드의 존재를 이미 알고 있는 상황. => 그래서 kernel의 단기 스케줄러가 cpu사용권을 결정하는 것. => "Global Scheduling"

* 알고리즘 성능 평가

cf> trace : 실제 프로그램을 통해 추출한 input data.

* 복습

cpu 스케줄링의 매커니즘 : ready 큐에 있는 프로세스중 누구한테 cpu를 줄지 정하는 것.
(크게 두가지 이슈가 있다)

1. cpu burst에 들어온 수많은 프로세스들중 누구한테 줄까?
2. cpu를 프로그램한테 줬으면 I/O를 하러 나갈때까지 계속 줄꺼냐? 아니면 중간에 뺏을꺼냐?

즉, 누구한테 줄것인가? 일단 줬으면 중간에 뺏어 오게 할 수 있게 할 것인가.
(공평도 필요하지만 효율적으로 하기위한 매커니즘)

* CPU 스케줄링 알고리즘

# 알고리즘들을 크게 두가지로 나누어 본다면,

 1) NONPreemtive 한 스케줄링 : 강제로 cpu를 빼앗지 않는 방법 (일단 cpu한번 주면 자진반납할때 까지 cpu보장해주는 방법- 비선점형)

 2) Preemtive 한 스케줄링 : 언제든지 뺏어올 수 있는 방법 (선점형, 요즘은 이걸 많이씀)

* CPU 스케줄링 성능 척도

# 성능척도를 크게 두가지로 생각해 볼수 있다.
 1) 시스템 입장에서의 성능 척도
  : CPU 하나를 가지고 최대한 일을 많이 시키면 좋은것(파란색 2개)
 2) 프로그램 입장에서의 성능 척도
  : 내가(프로세스) CPU를 빨리 얻어서 빨리 끈나면 좋은것, 그래서 시간과 관련이 있는 3가지를 고려(빨간색 3개)

# 척도 소개

 (처음 2개는 사장 입장)
 - CPU utilization : 전체 시간중에서 cpu가 놀지 않고 일한 시간.
 - Througput : 주어진 시간 동안에 몇개의 작업을 처리 하였느냐

 (밑에 3개는 고객입장(빨리 서비스 받고 싶다.))
 - Turnaround time : cpu를 쓰러 들어와서 다쓰고 나갈때 까지의 시간. (waiting time + cpu이용시간)
 - Waiting time : cpu를 쓰고자 ready큐에서 기다리는 시간
 - Response time : ready큐에 들어와서 cpu쓰겠다고 들어와서 처음으로 cpu를 얻기까지 걸린 시간.

cf> waiting time과 response time의 차이를 구분해보자면, preemtive(선점형)인 경우, cpu를 계속해서 돌려쓰게 되는데
1) waiting time : 기다리는거 모두 합한 값.
2) response time : 제일 처음 기다린 시간.
3) turnaround time : waiting time + 실행 시간

???) 시간을 왜 굳이 3개씩이나 나누지?
: 응답시간을 둔 이유는 time sharing 환경에서는 처음으로 cpu를 얻는 시간이 사용자 응답과 관련해서 굉장히 중요한 시간의 개념이다. 그래서 반환시간도 있고 대기시간도 있지만 응답시간을 별도로 둬서 이야기 하는 이유이다!

* FCFS
 : 먼저오면 먼저 처리 (NoonPreemtive)

# NoonPreemtive한 스케줄링이다. 중간에 시간이 많이 걸리는게 있다면 비효율적이다.

# 앞에 경우와 비교해보면 평균 waiting time이 짧아진것을 볼 수 있다.

# Convoy effect : 긴 프로세스가 먼저 도착해서 짧은 프로세스들이 지나치게 많은 시간을 기다리는 효과를 의미. (부정적 효과)

* SJF
 : 수행시간이 짧은게 먼저 처리

# Average waiting time이 최소화 되는 방법.

# SJF 알고리즘도 두가지 방법으로 나누어서 생각해 볼수 있다.

1) NoonPreemtive 한 방법
2) Preemtive한 방법 : cpu를 줬다 하더라고 남은 수행시간이 더 짧은 애가 오면 cpu를 빼앗긴다.(SRTF 라고도 부른다)

# 두가지 예를 봐보자

1) NoonPreemtive version.

2) Preemtive version.

# Preemtive 버전이 더 짧다는것을 알수 있다. (더 좋다.)

???) 그러나 두가지 문제점이 있다.

1) starvation(기아현상) : SJF는 수행시간이 짧은거를 선호 하기 때문에, 수행시간이 긴 프로세스는 영원히 서비스를 못 받을 수도 있다.

2) 매번 cpu사용 시간을 미리 알수 없다는게 문제이다. 그럼 SJF는 실제로 적용 못하나요? => 정확히는 알수 없지만, 과거의 사례(과거의 CPU burst time)을 통해서 추정한다

# 다음 cpu burst time 예측

 : 점화식을 해석해 보면 과거일수록 반영하는 가중치가 줄어든다.

* Priority Scheduling 
 : 우선순위가 높은 프로세스한테 cpu할당

# Priority Scheduling 알고리즘도 두가지 방법으로 나누어서 생각해 볼수 있다.

1) NoonPreemtive 한 방법
2) Preemtive한 방법 : cpu를 줬다 하더라고 남은 수행시간이 더 짧은 애가 오면 cpu를 빼앗긴다.(SRTF 라고도 부른다)

cf> 작은 숫자가 우선순위가 높다.

# Aging : 아무리 우선순위가 낮더라 하더라도, 시간이 지나게 되면서 우선순위를 조금씩 높여주자(starvation의 해결책!)

* Round Robin
: 가장 현대적인 스케줄링 알고리즘, 여태 우리가 배웠던 시스템이 RR이다.

# RR의 장점 : cpu 응답시간이 빨라진다. (누구든지 조금만 기다리면 cpu를 맛볼수 있다.)
(n-1)q 만 기다리면 내 차례가 돌아온다. (q라는 퀀텀을 짧게 잡아줄수록 내 차례가 빨리 다가온다.)

#
1) q를 너무 크게 잡으면 : FCFS
2) q를 너무 짧게 잡으면 : context switch 오버헤드가 커진다.(시스템 전체 성능이 나빠질수 있다.)
 => 즉, 너무 크거나 짧게 q를 잡으면 성능이 나빠진다.

# 할당 시간(q)이 20 인경우의 예제

# RR의 장점 : Response time이 줄어든다!!

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

1. 문제 이해

L 시간동안 탈주범이 있을 수 있는 공간의 갯수를 세어보는 문제입니다.

2. 접근 방법

- dfs를 통해 문제에 접근하였습니다.

- 4방향으로 나누어 현재와 다음단계의 파이프를 비교하여 갈수 없는곳을 continue 시켰습니다.

- ret 이라는 변수를 따로 두어 지나간 곳을 1로 체크하여 1이 체크된 곳의 수를 세어 출력하였습니다.

(visit은 ret과 다른 용도 입니다. ret을 쓰지 않으면 갔던곳을 또 갈수 없기 때문에 1번(+)파이프일 경우에 오류가 생기게 됩니다.)

3. 문제 해결