운영체제와 정보기술의 원리

6장 CPU 스케줄링

CPU는 컴퓨터 내 중앙처리장치로 프로그램이 시작되어 메모리에 올라가면 pc라는 이름의 레지스터가 cpu에서 수행할 코드의 메모리 주소값을 가진다. cpu에서 수행되는 기계어 명령은 아래와 같다.

• CPU 내에서 수행되는 명령

  add로 레지스터 내에 있는 두 값을 더해 레지스터에 저장

• 메모리 접근 명령

  메모리에 있는 데이터를 CPU로 읽어들이는 Load, CPU에 계산된 결괏값을 메모리에 저장하는 Store

• 입출력 명령

  키보드, 디스크 저장, CPU의 제어권이 운영체제 커널로 넘어가 많은 시간 소요된다. I/O 버스트

  프로그램이 I/O를 수행하고 다음번 I/O를 수행할 때까지 직접 CPU를 가지고 명령을 수행하는 과정이 CPU 버스트

• I/O 바운드 프로세스

  I/O 요청이 빈번해 CPU 버스트가 짧게 일어나는 프로세스(짧은 CPU 버스트를 많이 소유)

  사용자로부터 인터렉션을 받아가며 프로그램을 수행하는 대화형 프로그램

• CPU 바운드 프로세스

  I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 일어나는 프로세스(긴 CPU 버스트를 적게)

  프로세스 수행의 상당 시간을 입출력 없이 CPU 작업에 소모하는 계산 위주 프로그램

CPU 스케줄링은 여러 프로그램이 동일한 시스템에서 실행되기에 필요

짧게 사용하는 I/O 바운드 프로세스의 빈도가 높으므로 이것의 우선순위를 높이는 것이 바람직하다.

1. CPU 스케줄러

준비 상태에 있는 프로세스가 있는 준비 큐에서 어떤 프로세스에 CPU 할당할지 결정하는 운영체제 코드

• I/O 요청 등에 의해 실행 -> 봉쇄: 비선점
• 타이머 인터럽트에 의해 실행 -> 봉쇄: 선점
• I/O 작업 완료로 봉쇄돼 문맥교환을 통해 CPU 할당 -> 준비: 선점
• 실행 중 -> 종료: 비선점

위의 경우가 발생하면 CPU 스케줄러 필요

• 비선점형 방식

  CPU를 획득한 프로세스가 반납 전까지 내놓지 않음

• 선점형 방식

  프로세스에게서 CPU 빼앗을 수 있음

2. 디스패처

새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정하는 운영체제 코드

프로세스 문맥을 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원, 시스템 상태 사용자모드로 전환(프로세스에게 CPU 넘김)

=> 이 과정에서 걸리는 프로세스 정지, 다른 프로세스에 CPU 전달까지의 시간을 디스패치 지연시간 이라고 한다.

3. 스케줄링의 성능 평가

CPU 이용률, 처리량, 소요시간, 대기시간, 응답시간

• CPU 이용률

  전체 시간 중 CPU가 일 한 시간의 비율

• 처리량

  주어진 시간동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 마쳤는지(CPU 버스트 완료된 개수)

• 소요시간

  CPU 다 쓰고 끝날 때까지 걸린 시간

• 대기시간

  CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU 기다린 시간

• 응답시간

  첫번째 CPU 획득까지 기다린 시간

4. 스케줄링 알고리즘

선입선출 FCFS

준비 큐에 도착한 순서대로 CPU 할당

앞 프로세스가 길면 뒤는 무한 기다림 -> 콘보이 현상

최단 작업 우선 SJF

CPU 버스트가 가장 짧은 프로세스에게 먼저 할당

비선점형, 선점형(더 짧은 애가 들어오면 뺏어감, SRTF) 둘 다 가능하고 평균 대기시간을 가장 짧게 할 수 있음

좋지만 CPU 버스트 시간을 미리 알 수가 없다. 예측 시간으로 구현한다. 이게 최선이지도 않은게 긴 CPU 버스트 가진 프로세스는 영원히 기다리기만 해야한다. -> 기아 현상

우선순위 priority scheduling

우선순위가 높은 프로세스에게 CPU 할당

우선순위는 CPU 버스트 시간 기준일 수도, 다른 요소일 수도 있다.

이것도 SJF 처럼 기아현상이 일어날 수 있어 오래 기다리면 우선순위 높여주는 노화 기법을 사용하게 된다.

라운드 로빈

시분할 시스템을 가장 잘 활용한 알고리즘

CPU가 사용할 수 있는 시간이 제한되어 있고 시간이 지나면 다른 프로세스에게 CPU 할당하고 큐의 제일 뒤에 간다.

이 시간을 잘 설정해야 문맥교환의 오버헤드는 줄이고 FCFS와 같아지는 문제가 안일어난다.

멀티레벨 큐

준비 큐를 여러 개로 분할해 관리하는 기법

프로세스 성격에 맞는 스케줄링을 적요하기 위해 준비 큐를 별도로 준다.

• 전위 큐

  대화형 작업을 담기 위함, 응답시간을 짧게 하기 위해 라운드 로빈 사용

• 후위 큐

  계산 위주의 작업을 담기 위함, 응답시간이 의미를 같지 않으므로 FCFS 사용해 문맥교환 오버헤드 줄임

큐 자체에 대해 어느 큐에 먼저 CPU를 할당할 것인지 결정할 스케줄링 필요

• 고정 우선순위 방식

우선순위 높은거 먼저하고 그게 비어있을 때만 낮은 큐 실행(보통 전위 큐를 우선 큐로)

• 타임 슬라이스 방식

  기아 현상 해소로 각 큐에 CPU 시간을 적절한 비율로 할당

멀티레벨 피드백 큐

CPU를 기다리는 프로세스를 여러 큐에 줄 세움과 동시에 하나의 큐에서 다른 큐로 이동 가능

큐의 수, 각 큐의 스케줄링 알고리즘, 프로세스를 상위 큐로 승격시키는 기준, 강등시키는 기준, 들어갈 큐를 결정할 기준 등으로 멀티레벨 피드백 큐를 정의할 수 있다.

다중처리기 스케줄링

CPU가 여러개면 어떻게 스케줄링할까?

CPU별 부하가 적절히 분산되도록 부하균형 매커니즘 필요

• 대칭형 다중처리

  각 CPU가 알아서 스케줄링 결정

• 비대칭형 다중처리

  하나의 CPU가 다른 CPU의 스케줄링 및 데이터 접근 관리

실시간 스케줄링

실시간 시스템에서는 반드시 정해진 데드라인 안에 작업을 처리해야 한다.

• 경성 실시간 시스템

  미사일 발사같이 무족건

• 연성 실시간 시스템

  데드라인을 안지킨다고 큰 문제가 일어나지는 않는 상황

5. 스케줄링 알고리즘의 평가

• 큐잉모델

  확률분포를 통해 프로세스들의 도착률과 CPU의 처리율 주면 성능지표, CPU의 처리량, 프로세스의 평균 대기시간 구함

• 시뮬레이션

  가상으로 CPU 프로그램 작성하고 결과 확인, 입력값이 가상일수도 있고 실제(trace)일수도

• 구현 및 실측

  운영체제 커널의 소스코드 중 CPU 스케줄링 코드 수정해 커널 컴파일하고 측정