스케줄러(Scheduler)

목차

스케줄러

• 운영체제의 일부로, 스케줄링을 하는 코드이다. 운영체제라고 보면 된다.

• time sharing system에는 보통 장기 스케줄러가 없고,무조건 ready큐에 담긴다.
• 장기스케줄러는 new(새로운 프로세스) → ready큐에 담을 때 사용한다. 

스케줄러 종류

Long-term scheduler (장기스케줄러 or job scheduler)

• 시작 프로세스 중에서 어떤 것들을 ready queue로 보낼지 결정
• 프로세스에 memory(및 각종 자원)을 주는 문제

Short-term scheduler (단기스케줄러)

• 어떤 프로세스를 다음번에 running 시킬 지 결정
• 프로세스에 CPU를 주는 문제

Medium-Term Scheduler (중기스케줄러)

• 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄
• 프로세스에게서 memory를 뺏는 문제
• degree of Multiprogramming: 메모리에 올라간 프로그램의 수

cf) 메모리에 프로그램이 너무 많이 올라가도, 너무 적게 올라가도 성능이 좋지 않은 것이다. 참고로 time sharing system 에서는 장기 스케줄러가 없다. 그냥 곧바로 메모리에 올라가 ready 상태가 된다.

CPU 스케줄링

프로그램 실행 일대기

1. CPU burst: CPU에서 기계어 실행
2. I/O burst: I/O 작업

1, 2번 과정을 평생 반복한다.

 

CPU burst-Time 분포

• CPU bound job(process)
  • CPU를 길게(연속적) 쓰는 프로세스

• I/O bound job(process)
  • CPU를 짧게 쓰는 프로세스(I/O 작업이 끼어들기 때문에 짧게 씀)

I/O bound job에게 먼저 줘야한다.

→ CPU를 짧게 쓰고 바로 I/O 작업(Interactive)에 보내면 효율적이기 때문이다.

 

여러 종류의 job(process)들이 섞여 있기 때문에 CPU 스케줄링이 필요하다.

• Interactive job(사람과 상호작용하는 프로세스)에게 우선 제공 요망

• CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

CPU Scheduler & Dispatcher

OS의 일부 코드 형태로 실행된다.

CPU Scheduler

• Ready 상태인 프로세스 중 CPU를 줄 프로세스 고른다.

Dispatcher

• CPU Scheduler에게 선택된 프로세스에게 직접 CPU를 준다.

• 이 과정을 Context Switch(문맥 교환)이라고 한다.

CPU Scheduling이 필요한 경우

• Running → Blocked (I/o 요청하는 시스템 콜) cpu 자진 반납
• Running → Ready (할당시간 만료로 timer interrupt) cpu 강제 뺏기
• Blocked → Ready (I/O 완료 후 인터럽트) cpu 강제 뺏기
• Terminate cpu 자진 반납

Scheduling Algorithms

• FCFS(First-Come First-Served)
  • 먼저 온 고객을 먼저 서비스해주는 방식, 즉 먼저 온 순서대로 처리.
  • 비선점형(Non-Preemptive) 스케줄링
    일단 CPU 를 잡으면 CPU burst 가 완료될 때까지 CPU 를 반환하지 않는다. 할당되었던 CPU 가 반환될 때만 스케줄링이 이루어진다.
  • 문제점: 소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다.
• SJF (Shortest-Job-First)
  • 다른 프로세스가 먼저 도착했어도 CPU burst time 이 짧은 프로세스에게 선 할당
  • 비선점형(Non-Preemptive) 스케줄링
  • 문제점: 효율성을 추구하는게 가장 중요하지만 특정 프로세스가 지나치게 차별받으면 안되는 것이다. 이 스케줄링은 극단적으로 CPU 사용이 짧은 job 을 선호한다. 그래서 사용 시간이 긴 프로세스는 거의 영원히 CPU 를 할당받을 수 없다.
• SRTF (Shortest-Remaining-Time-First)
  • 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
  • 선점형 (Preemptive) 스케줄링
    현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다.
  • 문제점: 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용시간)을 측정할 수가 없다.
• Priority Scheduling
  • 우선순위가 가장 높은 프로세스에게 CPU 를 할당하는 스케줄링이다. 우선순위란 정수로 표현하게 되고 작은 숫자가 우선순위가 높다.
  • 선점형 스케줄링(Preemptive) 방식
    더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점한다.
  • 비선점형 스케줄링(Non-Preemptive) 방식
    더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 Head 에 넣는다.
  • 문제점: 실행 준비는 되어있으나 CPU 를 사용못하는 프로세스를 CPU 가 무기한 대기하는 상태
  • 해결책: 아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주자.
• RR (Round Robin)
  • 현대적인 CPU 스케줄링
  • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다.
  • 할당 시간이 지나면 프로세스는 선점당하고 ready queue 의 제일 뒤에 가서 다시 줄을 선다.
  • RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적
  • RR이 가능한 이유는 프로세스의 context 를 save 할 수 있기 때문이다.
  • 반응시간이 빠르고, 프로세스가 기다리는 시간이 CPU 를 사용할 만큼 증가한다. 공정한 스케줄링이다.
  • 문제점: 설정한 time quantum이 너무 커지면 FCFS와 같아진다. 또 너무 작아지면 스케줄링 알고리즘의 목적에는 이상적이지만 잦은 context switch 로 overhead 가 발생한다. 그렇기 때문에 적당한 time quantum을 설정하는 것이 중요하다.
• Multilevel Queue
• Multilevel Feedback Queue

 

Scheduling Criteria(조건) == Performance Measure(성능 척도)

• CPU utilization (이용률)
• Throughput (처리량)
• Turnaround time (소요시간, 반환시간)
• Waiting time (대기시간)
• Response time (응답시간)