[운영체제(2)]CPU Scheduling 2

Multilevel Queue

여러줄로 cpu를 기다리는 줄서기를 배워보자

• 위에 있을 수록 높은 우선순위를 가진다.

1. 시스템 관련 process
2. 사람과 interaction 하는 process
3. 덜 interaction 하는 process
4. batch processes: cpu만 오랫동안 사용하는 process
5. student processes

• 완전히 계급제

• 위에 queue에 process가 없어야 밑에 quque에 있는 process가 cpu를 얻을 수 있음.
  => 어떤 queue에 넣을 것인가, starvation은 어떻게 해결할 것인가에 대한 질문
  

• foreground quque : 사람과 interactive 하는 process이기 때문에 응답시간을 짧게 해야 함. => Round Robin 스케줄링

• background queue : cpu를 오랫동안 사용하는 process이기 때문에 응답시간이 빠를 필요 없음. 되려 cpu를 뺏었다가 얻었다가 하는 context switch로 인해 생기는 오버헤드를 줄이기 위해서 먼저 온 순서대로 처리=> FCFS 스케줄링
  => 어떤 queue에 cpu를 줄 것이냐? 하는 문제
  1) Fixed priority scheduling

• foreground에 있는 프로세스가 cpu를 다 쓰고 나서야 backgroud 에 cpu를 준다.

• starvation이 생길 수 있는 문제
  2) Time slice

• cpu 시간을 적정한 비율로 나눈다.

• Multilevel quque는 Round Robin 과 달리 공정하지 않음.

• 대신, 우선적인 process한테 cpu를 차별적으로 주면서 효율성이 증대 된다.

• 신분을 영원히 극복하지 못함

Multilevel Feedback Queue

• 현대 사회처럼 출신이 낮아도 승격 가능, 강등도 가능
• process가 줄간에 이동 가능
• 처음 들어오는 process는 가장 우선순위가 높은 quque에 집어넣는다.
• 밑에 큐로 갈수록 Round Robin의 할당 time을 짧게 주고, 제일 아래 queue는 FCFS 방식/

지금까지는 cpu가 1개일 때를 이야기 했다.
이제는 "cpu가 2개"이거나 "시간의 데드라인 조건"이 있거나 "스레드가 여러개" 있거나 등 특이한 케이스에서 스케줄링을 이야기해보자

Multiple-Processor Scheduling

1) cpu가 여러개 있을 때

• symmetric : 대등하다는 의미. cpu 각자 스케줄링
• asymmetric : 하나의 cpu가 전체적인 control 담당. 데이터 접근, 공유 책임/ 나머지 cpu가 따름

Real-Time Scheduling

real-time job: deadline이 있는 job

• 미리 스케줄링을 해서 deadline이 보장되도록 job을 cpu에 배치한다.
  => 오프라인으로 스케줄링 or 주기적으로 1초에 한번씩 10초에 한번씩 cpu를 잡아야 한다등.

soft-real time: 최근에는 일반적인 time sharing system에서 다른 process들하고 섞여서 실행되는게 있다. ex) 영화보는 것.
반드시 deadline을 지키는 시스템은 아님.

Thread Scheduling

thread: 하나 process 안에 cpu 수행단위가 여러개 있는 것.

thread 구현 방식
1) user level thread: 사용자 process가 thread를 직접 관리하고 운영체제는 thread의 존재를 모르는 경우
2) kernel level thread: 운영체제가 이 thread의 존재를 이미 아는 것.

상황이 다르기 때문에 thread를 스케줄링 하는 방법도 다름.

Local Scheduling: 운영체제는 어떤 프로세스한테 cpu를 줄지 결정하고, 해당 프로세스 내부에서 어떤 스레드에게 cpu를 줄지 스케줄링한다.
Global Scheduling: process 스케줄링 하듯이, 운영체제가 어떤 알고리즘에 근거해서 이번에 어떤 스레드에게 cpu를 줄지 스케줄링한다.

Algorithm Evaluation

어떤 알고리즘이 좋은지 평가하는 방법에 대해 알아보자.

1. Queueing models

• 거의 이론가들이 주로 하는 방법
  
  1) queue에 job들이 도착을 한다. => quque에 쌓임
  2) 여기서 server는 cpu를 의미한다. (cpu 스케줄링을 하고 있기 때문)
  3) 도착한 process들을 cpu 용량과 능력에 따라서 처리를 하고 빠져나가는 service rate 처리율이 있다.
  4) arrive rate: process들이 도착하는 도착률
  5) service rate: cpu의 처리 능력인 처리율 (단위 시간당 몇개씩 처리할 수 있는지)
  6) 위 rate가 확률분포로 주어질 때, 복잡한 수식 계산을 한다.
  7) 그 결과로 여러가지 성능척도가 나온다. : performance index
  8) 그러면, cpu의 throughput 단위시간당 몇개 처리하는지 , 기다렸던 job들이 평균적으로 얼마나 기다렸는지 계산에 의해서 나오게 됨.
• 요즘에는 실제 system에서 돌려보는걸 선호하기 때문에 이 방법을 잘 쓰지는 않지만 여전히 이론적으로는 많이 사용하는 방법 중 하나.

2. **Implementation(구현) & Measurement(성능 측정) **
ex) cpu 스케줄링 알고리즘을 하나 만들었음. 그 알고리즘이 좋은지 실제 시스템에 구현. linux 커널의 소스코드를 수정해서 새로운 알고리즘으로 바꿔. 리눅스 커널을 컴파일하면, 리눅스의 실행 binary code가 나온다. 그래서 실제 프로그램들을 돌려서 어느쪽이 얼마나 빨리 끝나는지 확인하는 방식.

3. Simulation
그런데 2번과 같이 직접 리눅스 커널 운영체제 내부의 코드를 고치는 것은 어려운 일임/ 그래서 simulation이 있음.

• 모의실험을 함.
• 복잡한 process 사용패턴(CPU를 여러번 쓰고, Burst time도 제각각)과 여러 process들을 SJF 알고리즘에서 손으로 계산하는건 어려운 일이야. 그걸 대신해서 계산해주는 프로그램을 짜는 것이 simulation.
• 그리고 결과를 계산하면 (wating time등) simulation에 의한 결과라고 할 수 있음.
• 실제 프로그램을 통해서 추출한 input data를 trace라고 함.
• trace: simulation 프로그램의 input으로 들어갈 data /
• trace를 임의로 만들수도 있고, 그리고 실제 프로그램을 돌리면서 뽑을수도 있음. 아무래도 실제 프로그램을 돌리면서 뽑은 그런 trace를 가지고 simulation을 하면 좀 더 실제 상황을 잘 반영
• 우리도 충분히 만들어볼 수 있을 정도임.