[운영체제] CPU 스케줄링 2

스케줄링 알고리즘

FCFS

선착순
nonpreemptive: 먼저 도착했으면 다 쓰고 나갈 때까지 기다려줌

프로세스 3개가 있다면 도착한 순서에 따라 먼저 도착한 P1에 먼저 준다
=> 평균 기다리는 시간 17초

• 앞에 사용시간 긴 프로세스가 들어오면 전체 대기 시간이 길어진다
• 콘보이 이펙트 : 숏 프로세스 비하인드 롱 프로세스
  롱 프로세스가 먼저 도착하는 바람에 숏 프로세스가 오래 기다리게 되는 것

SJF

짧게 쓰는 프로세스한테 CPU 주는 방법

• 대기 시간 측면에서 옵티멀(최적의) 방법

• 두 가지 버전

  • nonpreemptive
    CPU 줬는데 새로운 프로세스가 큐에 도착한다면
    CPU 얻은 친구가 나갈 때까지는 빼앗지 않는다

  • preemptive
    더 짧은 프로세스가 도착하면 뺏어서 걔한테 주는 것

  • 둘 중 평균 대기시간이 더 짧은 것은 빼앗는 preemptive 방법 => 큐의 길이를 더 짧게 하는 효과

SRTF 남은 시간이 제일 짧은 친구한테 시피유를 준다
줬는데 5초 쓰기로 햇는데 3초 쓰고 2초 남은 시점에 1초짜리가 도착하면 누구한테 줄것인가?
남은 시간을 기준으로 2초랑 새로온 애 1초 비교해서

nonpreemptive

0초 시점에 P1이 CPU 획득
이후 뒤에 더 짧은 프로세스가 와도 빼앗지 않고 보장

7초 시점에는 P2, P3, P4가 줄서있는데 그 중 가장 실행시간 짧은 1초인 P3한테 CPU를 준다

preemptive

0초시점에 P1만 도착해서 CPU 획득
2초에 레디큐에 P2 도착
고민 기준은 P1의 5초(남은시간)와 P2의 4초
4초가 더 짧아서 P2에게 넘김
쓰다가 더 짧은 다르 프로세스 도착하면 또 넘겨줌

새로운 프로세스가 도착할 때마다 누가 더 짧은지 비교하고 빼앗음
옵티멀한 대기시간

SJF의 약점

1. starvation 발생 (기아 상태)
   효율성만 고려해서 짧은 프로세스에게만 CPU 줌
   영원히 CPU 못얻는 프로세스도 생김
   따라서 공평하게 기회를 줘야 한다

2. 누가 짧게 쓰고 갈게 쓰는지 미리 알 수 없음
   따라서 과거의 CPU 버스트를 통해 예측한다
   N + 1번째를 예측하고 싶다고 하면 과거 N번의 데이터를 바탕으로 예측
   t는 과거 CPU 버스트의 값

N + 1 번재 예측을 위해서는 과거 N번의 실제 CPU 버스트를 반영하고, 최초로 예측했던 값이 반영

바로 직전 것을 더 많이 반영하고 예전을 적게 반영한다
직전 것이 더 신빙성 있다고 본다

우선순위 스케줄링

우선순위가 높은 애한테 먼저 주겠다
SJF도 여기에 포함
(버스트 타임을 우선순으로 놓으면 시간이 짧은 프로세스가 우선순위 높아지기 때문)

우선순위를 정수로 표현하는데 작은 정수일수록 높은 우선순위로 표현

• preemptive
  • 우선순위가 더 높은 애가 오면 빼앗는다
• nonpreemptive
  • 다 끝내고 나올 때까지 빼앗지 않고 기다린다

문제점 : 스타베이션
우선순위 낮으면 영원히 실행 못할 수 있다
솔루션 : 에이징
오래 기다리면 기다린 시간만큼 우선순위 올려주는 것

라운드 로빈

타이머 세팅된 시간이 만료되면 인터럽트를 통해 운영체제로 넘어가도록 한다
preemptive 프로세스가 CPU 얻을 때 주어진 할당 시간이 끝나면 빼앗긴다

• 대기시간을 보장해준다
• 할당 시간이 너무 길면 FCFS(선착순)과 같다
• 할당 시간이 너무 작으면 문맥교환 오버헤드가 커진다
  I/O는 한번에 처리돼서 나갈 수 있지만 CPU는 여러 번에 처리돼서 나갈 수 있도록 잡으면 적당

53초 쓰고자 했지만 할당 20이라 쓰다가 뺏김

장점

• 응답 시간이 짧다 (최초로 CPU 얻을 때까지의 시간)
  다 같이 10분일때 라운드 로빈하면 다끝나는 시간이 동일 => 효과 없음
• average turnaround 시간은 길어진다
• 롱잡과 숏잡이 섞여있을 때 효과적

타임퀀텀에 따른 턴 어라운드 시간

타임퀀텀(실행의 최소 단위시간)이 짧을 때 비효율적인 경우도 생긴다

• SJF는 극단적인 효율성을 추구
• 라운드로빈은 대체적으로 합리적으로 공평하다
  기다리는 시간이 쓰려는 시간에 비례하기 때문

멀티레벨 큐

큐를 여러 개 분리해놓고 각 큐 별로 스케줄링 알고리즘 지정
CPU를 기다리기 위해 여러 줄로 줄을 서는 것

두개로 분할

포그라운드(interactive)

우선순위를 무조건 주는게 아니라 각 큐마다 시간 웨이트 주는 것
인터랙티브가 CPU를 더 빨리 얻을 가능성이 생긴다

백그라운드(batch)

처리량을 중점

• 큐 여러개라서 각각 스케줄링하는 알고리즘 필요
• 포 그라운드에 80 분배, 백그라운드 20분배하면 스타베이션 없다

제일 우선순위 높은 순대로

• 시스템 프로세스들
• 사람과 인터랙션하는 것들
• 그 아래 것들
  프로세스는 큐 중 한 군데만 있을 수 있다

멀티레벨 피드백 큐

큐를 여러개 두고 피드백 받아서 옮겨갈수 있도록 스케줄링 알고리즘을 만드는 것이 일반적

• 줄 간 이동이 가능
• 각 큐의 우선순위는 위가 높고 아래로 갈 수록 낮다
• 아래는 위 큐가 빌 때만 아래쪽 큐로 넘어가도록 한다
• 큐 개수 여러개를 줄 수 있고 각 큐마다 알고리즘 승격기준 강등기준 등 여러개를 정해야 한다
• 여러 방식으로 구현할 수도 있다(에이징과 같은 방식으로도 구현이 가능)

맨 윗 줄에 위치>
8 이내라면 쓰고 나가고, 8보다 길면 그 다음 큐로 넘어간다

라운드 로빈만 쓰는 것 보다는 I/O 바운드를 걸러내는 효과가 있다
짧게 쓰는 프로세스를 걸러내면서 다단계로 확인할 수 있다

멀티레벨 큐와의 차이점

멀티레벨 피드백 큐는 스타베이션 발생할 가능성이 있다 (위에 큐가 비지 않으면 아래는 갈 수 없음)