[혼자 공부하는 컴퓨터구조+운영체제]11장 CPU 스케줄링

11-1 CPU 스케줄링 개요

프로세스 우선순위

운영체제는 각 프로세스의 PCB에 우선순위를 명시하며, 일반적으로 입출력 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적이다.

• 입출력 집중 프로세스(I/O bound process)
  • 입출력 작업이 많은 프로세스 ⇒ 입출력 버스트가 많은 프로세스
    • 입출력 버스트(I/O burst): 입출력장치를 기다리는 작업
  • 실행 상태보다 입출력을 위한 대기 상태에 더 많이 머무름
  • 예) 비디오 재생, 디스크 백업 작업 등
• CPU 집중 프로세스(CPI bound process)
  • CPU 작업이 많은 프로세스 ⇒ CPU 버스트가 많은 프로세스
    • CPU 버스트(CPU burst): CPU를 이용하는 작업
  • 입출력을 위한 대기 상태보다 실행 상태에 더 많이 머무름
  • 예) 복잡한 수학 연산, 컴파일, 그래픽 처리 작업 등

스케줄링 큐

운영체제가 우선순위를 위해 매번 PCB를 검사하는 것은 비효율적이다.

• 스케줄링 큐
  • 프로세스를 줄 세워 관리하는 공간
  • 큐이지만 반드시 선입선출 방식일 필요 없음
  • 메모리로 적재되고 싶은 프로세스를 위한 큐, CPU를 이용하고 싶은 프로세스를 위한 큐, 특정 입출력장치를 이용하고 싶은 프로세스를 위한 큐 등 모두 각기 다른 큐로 관리
• 준비 큐(ready queue)
  • CPU를 이용하고 싶은 프로세스가 서는 큐
• 대기 큐(waiting queue)
  • 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스가 서는 큐

운영체제는 큐에 삽입된 PCB를 순서대로 꺼내어 실행하되, 그중 우선순위가 높은 프로세스를 먼저 실행한다.

선점형과 비선점형 스케줄링

• 선점형 스케줄링(preemptive scheduling)
  • 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당
  • 어느 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식
  • 예) 타이머 인터럽트가 발생하여 CPU가 자원을 빼앗아 다음 프로세스에 할당
  • 장점: 한 프로세스의 자원 독점을 막고, 골고루 자원 배분 가능
  • 단점: 문맥 교환 과정에서 오버헤드 발생 가능
• 비선점형 스케줄링(non-preemptive scheduling)
  • 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어둘 수 없는 스케줄링 방식
  • 하나의 프로세스가 자원 사용 독점 가능
  • 장점: 문맥 교환 횟수가 적어 오버헤드가 선점형 스케줄링보다 적음
  • 단점: 모든 프로세스가 골고루 자원 사용하기 어려움

11-2 CPU 스케줄링 알고리즘

스케줄링 알고리즘의 종류

운영체제는 저마다 다른 스케줄링 알고리즘을 사용한다.

선입 선처리 스케줄링

• First Come, First Served Scheduling, FCFS 스케줄링
• 준비 큐에 삽입된 순서대로 프로세스를 처리하는 비선점형 스케줄링 방식
• 프로세스가 기다리는 시간이 매우 길어질 수 있음
• 호위 효과(convoy effect) 발생 가능
  • CPU 이용 시간이 짧은 프로세스가 앞서 실행된, CPU 이용 시간이 긴 프로세스를 한참 동안 기다려야 하는 현상

최단 작업 우선 스케줄링

• Shortest Job First Scheduling, SJF 스케줄링
• 준비 큐에 삽입된 프로세스 중 CPU 이용 시간이 가장 짧은 프로세스부터 실행하는 방식
• 일반적으로 비선점형 스케줄링 알고리즘으로 분류

라운드 로빈 스케줄링

• 선입 선처리 스케줄링 + 타임 슬라이스
  • 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 준비 큐에 삽입된 순서대로 프로세스가 CPU를 사용하되, 정해진 시간을 모두 사용하면 다시 큐의 맨 뒤로 삽입되는 선점형 스케줄링 방식
  • 문맥 교환 발생
• 타입 슬라이스가 지나치게 큰 경우 선입 선처리 스케줄링과 다를 바 없어 호위 효과 발생, 타입 슬라이스가 지나치게 작은 경우 CPU가 프로세스 처리보다 문맥 교환에 더 열중

최소 잔여 시간 우선 스케줄링

• Shortest Remaining Time Scheduling, SRT 스케줄링
• 최단 작업 우선 스케줄링 + 라운드 로빈 알고리즘
• 준비 큐에 삽입된 프로세스 중 남은 CPU 이용 시간이 가장 짧은 프로세스부터 실행하되, 정해진 타임 슬라이스만큼만 사용하는 스케줄링 방식

우선순위 스케줄링

• 프로세스에 우선순위를 부여하고 높은 우선순위를 가진 프로세스부터 실행
  • 우선순위가 같다면 선입 선처리 스케줄링 적용
• 최단 작업 우선 스케줄링, 최소 잔여 시간 우선 스케줄링 → 일종의 우선순위 스케줄링
• 기아(starvation) 현상 발생 가능
  • 우선순위가 낮은 프로세스가 계속해서 우선순위가 높은 프로세스에 의해 실행이 연기되는 현상
• 에이징(again) 기법
  • 기아 현상을 방지하기 위한 기법
  • 오래 대기한 프로세스의 우선순위를 점차 높이는 방식

다단계 큐 스케줄링

• Multilevel queue scheduling
• 우선순위별로 준비 큐를 여러 개 사용하는 방식
• 우선순위가 높은 큐의 프로세스를 먼저 처리 → 큐가 빈다면 그다음 우선순위 큐에 있는 프로세스 처리
• 프로세스 유형별로 우선순위를 구분하여 편리하게 사용 가능
• 큐별로 타임 슬라이스를 지정 가능 + 큐마다 다른 스케줄링 알고리즘 사용 가능
• 기아 현상 발생 가능

다단계 피드백 큐 스케줄링

• Multilevel feedback queue scheduling
• 다단계 큐 스케줄링의 기아 현상을 막기 위해 보완된 스케줄링 방식
• 다단계 큐 스케줄링과 달리 프로세스가 큐 사이를 이동 가능
  • 프로세스가 타임 슬라이스 동안 실행을 다 못 끝낸 경우, 우선순위가 낮은 큐로 삽입 ⇒ CPU를 오래 사용하는 프로세스는 우선순위가 점차 낮아짐
  • 낮은 우선순위 큐에서 프로세스가 너무 오래 기다리고 있다면 높은 우선순위 큐로 옮겨 기아 현상 예방 가능 ⇒ 에이징 기법의 적용
• 구현이 복잡하지만 가장 일반적으로 사용되는 CPU 스케줄링 알고리즘