CPU 스케줄링

CPU 스케줄링 기본개념

• 실행과정을 보게 되면 cpu burst → I/O burst 번갈아면서 반복하다 cpu burst로 프로그램 종료
• 메모리에 실행되는 program 1개 밖에 없다면 cpu가 cpu burst로 막 실행하다 I/O 일어나면 CPU 기다릴 때 할일 없어진다.
• 위의 상황을 방지하기 위해 프로그램 여러개를 main memory에 갖다두고 A 프로그램이 I/O 하고 있으면 CPU 뺏고 B 프로그램한테 줘서 cpu burst 되도록 하게 한다. (multi programming 개념 → cpu 활용도 ↑)
• cpu를 기다리고 있는 레디큐에 여러개의 프로세스가 있다고 하면 어떤애한테 cpu를 줄것인가 라는 것을 결정하는 것이 바로 cpu 스케줄러가 하는일이다.
  • ex) process A가 cpu 반환, cpu 나눠줄 다음 process 선택하는 것이 cpu 스케줄링의 목적
• I/O 하기전 CPU 사용시간, 즉 CPU burst 시간이 어떻게 분포되었는가 하는 것이 우리의 관심사이다.
• 대부분 우리의 프로그램들은 짧게 cpu를 사용하고 I/O를 많이 기다리고 짧게 사용하고 I/O를 많이 기다리는 방식으로 프로그램이 실행된다.

 

 

CPU 스케줄러

• short-term scheduler라고 부른다.
• short-term scheduler는 현재 메모리에 올라와있는 프로세스들 중에서 다음 번에 어떤 프로세스한테 cpu를 할당할 것인가 결정하는 스케줄러
• cpu는 언제 동작하느냐
  • 어떤 프로세스가 실행상태에서 I/O 때문에 대기 상태로 가면 CPU 내놓기 때문에 CPU 스케줄러 동작시킨다.
  • 어떤 프로세스가 실행 상태에서 시간 많이 써서 운영체제가 강제로 CPU 뺏고 다른 프로세스에게 실행 상태로 보내졌을 때
  • 어떤 프로세스가 I/O 를 기다리고 있다가 READY 상태로 감 (운영체제가 실행되고 있을때니까 새로 들어온 프로세스한테 CPU를 줄 것인가 기존 실행되고 있던 프로세스한테 CPU 줄 것인지 결정)
  • 한 프로세스가 종료 → CPU 스케줄러 돌아감. 자발적으로 프로세스가 CPU 내놓는다.
  • 1,4 → 프로세스가 더이상 CPU 필요없어서 스스로 내놓는 것
  • 2 → P1이 실행되고 있었는데 많이 사용했다는 이유로 강제로 뺏는것
  • 3 → P1 이 실행되고 있었는데 다른 P2가 I/O 끝내고 난 다음 레디큐에 와 운영체제가 P1에 있는 CPU 뺏어서 P2로 주는 경우 
• 강제로 뺏기는것 → PREEMPTIVE (선점)
• 선점 알고리즘 사용할 때 조심해야 할 것
  • 언제 종료당할지 모르는 프로세스가 critical shared data 를 건드리고 있을때 뺏겨버리면 현재 데이터가 일반적이지 않은 상태 될 수 있다. 선점하는 경우에 내가 선점당하지 않아야 된다고 생각하면 lock을 걸던지 해야 하는데 선점 알고리즘 조심해서 사용해야 한다. (deadlock 문제 가능성)
  • 커널 더 급한일 있어서 중지시킨다면 데이터가 어떤 일하다가 inconsistency 상태 빠질 수 있다. 커널도 마찬가지로 주의해야 한다.

 

디스패처

• 디스패처는 운영체제 일부다.
• cpu 스케줄러가 레디 큐에 있는 어떤 프로세스한테 cpu를 줘야겠다고 결정하게 되면 실제 프로세스에게 cpu 주는 역할하는 것이 디스패처 프로그램
• 하는일
  • 현재 프로세스의 context 저장, 새로 실행해야 할 process 복원
  • 사용자 모드로 변경
  • 사용자가 예전에 프로세스가 중지 되었던 위치로 jump해서 프로그램 실행
• cpu를 써서 일해야되므로 시간이 걸린다.
• Dispatcher latency - 디스패처가 잡아먹는  시간 (디스패처 지연시간)
  • 디스패처가 쓰는 시간을 사용자 프로그램을 실행 시키기 위해서 쓰는 시간이 아니라 문맥교환하는데 쓰는 시간이므로 사용자 입장에서는 오버헤드 시간 줄이는 것이 좋다.

 

 

스케줄링 기준

• 어떤 스케줄 알고리즘이 좋은지 평가하기 위함
• 종류
  • cpu 활용도 - 전체시간중에 cpu가 몇 퍼센트 일하는 건지 (cpu 효율시간 줄이면 된다.)
  • 처리량 - 단위시간 당 자기 작업을 다 끝낸 프로세스
  • 작업 반환 시간 - 내가 작업을 A한테 줬을 때 A작업이 끝나고 결과가 돌아오는 시간
    • process가 시스템에 돌렸을 때 시스템에서 끝나서 결과가 나한테 올 때까지 걸리는 시간
  • waiting time - 내 프로세스가 얼마나 대기했는지 시간
  • 반응 시간 - 프로그램 돌렸는데 처음 반응이 나올때까지 걸린 시간 

 

 

 

FCFS

• 선입선처리 - 들어오는 순서대로 처리해준다.
• 전체적으로 waiting time 길어지고 초위함 효과라는 나쁜 효과가 나온다.
  
  • 초위함 효과 - 짧은 burst 가진 process가 긴 burst 가진 process 뒤에 붙어서 (I/O 큐, 레디큐 뒤에서) 항상 기다리는 현상

 

 

 

SJF

• 각 process 한테 다음 cpu를 얼마나 사용할래라는 길이를 붙여둔다. 
  • cpu burst 시간 알아내는 것이 문제 - 악의적인 사용자 현실적이지 못함, 시스템이 어떻게든 알아내는 것이 적당한 방법
• 짧은 burst 부터 먼저 처리하는 방법 - 짧은 작업을 먼저 실행하게 되면 대기시간이 준다.
• cpu burst 짧은 프로세스를 처리를 하게 되면 전체적으로 대기시간 평균이 최적이다.

 

 

• 다음 cpu bust 시간을 어떻게 추정하나?
  • 프로세스가 과거 행동 가지고 다음에 p1한테 cpu 줬을 때 얼마나 cpu 사용할 것인가 추정 - 예측값이 가장 짧은 프로세스 고른다.
  • 기하 평균 사용

직전의 행동 1/2 만큼 전전 행동 1/4 만큼 영향 - 과거로 멀어지면 멀어질수록 지수적 영향력이 줄게 된다.

 

 

 

 

shortest-remaining-time-first

• P1의 burst time = 10, p2의 burst time =2 → 우리가 강제로 p1을 뺏어서 p2를 주는 것
• cpu burst time 기준으로 shortest job이 선점적인 버전으로 스케줄링 하는 것