[혼공컴운] chapter 11. CPU 스케줄링

11-1. CPU 스케줄링 개요

운영체제가 프로세스들에게 CPU 자원을 배분 하는 것
PCB에 명시되어 있음

프로세스 우선순위

우선순위가 높은 프로세스를 먼저 처리하는 것이 효율적

• 입출력 집중 프로세스

  입출력이 많은 프로세스 
  예) 비디오 재생, 디스크 백업 등
  실행 상태보다 입출력을 위한 대기 상태에 많이 머무름

• CPU 집중 프로세스
  CPU 작업이 많은 프로세스
  예) 수학연산, 컴파일, 그래픽 처리 등
  대기 상태보다 실행 상태에 많이 머무름

• CPU 버스트
  CPU를 사용하는 작업

• 입출력 버스트

  입출력장치를 기다리는 작업

CPU 집중 프로세스와 입출력 집중 프로세스가 동일한 빈도로 CPU를 사용하는 것은 비합리적
입출력 집중 프로세스를 빨리 실행시켜 입출력 장치를 끊임없이 작동시키고 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적
입출력 작업을 완료하기 전까지 입출력 집중 프로세스는 대기 상태이기 때문

스케줄링 큐

프로세스들을 순서대로 줄 세우는 것
이때 큐 사용

• 준비 큐

  CPU를 이용하고 싶은 프로세스들이 서는 줄 

  • 대기 큐
    입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄
    OS는 PCB들이 큐에 삽입된 순서대로 꺼내어 실행하되, 우선순위가 높은 프로세스를 먼저 실행

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

• 선점형 스케줄링

  운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 방식 
  자원 독점을 막고 자원을 골고루 배분 할 수 있다 
  문맥 교환 과정에서 오버헤드 발생 

  • 비선점형 스케줄링

    프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 방식 
    문백 교환에서 발생하는 오버헤드가 적다 
    골고루 자원을 사용할 수 없다 \

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

스케줄링 알고리즘의 종류

1. FCFS 스케줄링

선입 선처리 스케줄
준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링
프로세스 대기 시간이 매우 길어질 수 있음

• 호위 효과
  CPU를 오래 사용하는 프로세스가 먼저 도착하여 다른 프로세스의 대기 시간이 기다리는 현상
  예) 2ms 를 실행하기 위해 22ms 대기

  2. SJF 스케줄링

  최단 작업 우선 스케줄링
  준비 큐에 삽입된 프로세스 중 CPU 사용 시간의 길이가 가장 짧은 프로세스부터 실행하는 방식
  호위 효과를 방지할 수 있음
  기본적으로 비선점형이지만, 선점형으로 구현할 수도 있음

  3. RR 스케줄링

  라운드 로빈 스케줄링
  FCFS + 타임 슬라이스

• 타임 슬라이스

  CPU를 사용할 수 있는 시간

  입력 순서대로 정해신 시간(타임 슬라이스)만큼만 CPU를 사용할 수 있는 선점형 스케줄링 방식
  프로세스가 완료되지 않았다면 큐의 맨 뒤에 삽입

  4. SRT 스케줄링

  최소 잔여 시간 우선 스케줄링
  SJF + RR
  잔여시간이 짧은 프로세스부터 실행하되, 타임 슬라이스만큼만 CPU 사용 가능

  5. 우선순위 스케줄링

  프로세스에 우선순위를 부여하고 가장 높은 우선순위 프로세스부터 실행
  우선순위가 같으면 FCFS
  SJF, SRT 은 우선순위 스케줄링의 일종

• 기아 현상
  우선순위가 낮은 프로세스는 실행이 계속 연기될 수 있음

• 에이징
  기아현상을 방지하기 위한 대표적인 방식
  오래 대기한 프로세스의 우선순위를 높이는 방식

  6. 다단계 큐 스케줄링

  우선순위 스케줄링의 발전된 형태
  우선순위별로 준비큐를 여러 개 사용하는 방식
  프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해짐
  각 큐에서 적절한 스케줄링 방식을 활용할 수 있음

  7. 다단계 피드백 큐 스케줄링

  다단계 큐 스케줄링의 발전된 형태 (기아현상 방지)
  프로세스가 큐 사이를 이동할 수 있음
  새롭게 준비 상태가 된 프로세스가 있다면 우선순위가 가장 높은 우선순위 큐에 삽입되고 타임 슬라이스 동안 실행
  해당 큐에서 끝마치지 못했다면 다음 우선순위큐에 삽입 (점점 우선순위가 낮아짐)
  낮은 우선순위 큐에서 기아 현상이 발생했다면 우선순위가 높은 큐로 이동시키는 에이징 방식을 활용할 수 있다