11장 CPU 스케줄링

11-1 CPU 스케줄링 개요

• CPU 스케줄링: 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원 배분하는 것

프로세스 우선 순위

프로세스마다 우선순위가 다르다.
-> 우선순위가 높은 프로세스는 대표적으로 입출력 작업이 많은 프로세스가 있다.

• 대부분 프로세스는 CPU와 입출력 장치 모두 사용하며 실행된다.

• 실행 상태와 대기 상태를 반복하며 실행

  • 입출력 집중 프로세스(I/O bound process)
    • 비디오 재생, 디스크 백업 작업 담당
      - 실행상태보다 < 입출력을 위한 대기 상태에 더 많이 머무름

• CPU 집중 프로세스:

  • 복잡한 수학 연산, 컴파일, 그래픽 처리 작업 담당
  • 대기 상태 < 실행 상태

• CPU 이용하는 작업: CPU 버스트,
• 입출력 장치를 기다리는 작업: 입출력 버스트
• 
• 모두 동일한 빈도로 CPU를 사용하는 건 비합리적!

• 대기상태
  • 

• 운영체제는 프로세스마다 우선순위를 PCB에 부여하고, 그 기준으로 먼저 처리할 프로세스를 결정한다.
• 유닉스 체계 운영체제에서는
  • ps -el 명령어로 우선순위를 확인할 수 있다.
  • nice 명령을 통해 일부 프로세스의 우선순위를 변경할 수도 있다.

스케줄링 큐

• 운영체제가 매번 일일이 모든 PCB를 검사하여 먼저 자원을 이용할 프로세스를 결정하는 일은 매우 번거롭다!

• 줄 세우는 것을 스케줄링 큐로 구현하고 관리한다.

  • 스케줄링에서 말하는 큐는 반드시 선입선출 방식일 필요는 없다.

• 메모리로 적재되고 싶은(새로 생성되는) 프로세스들을 큐에 삽입하여 줄세우고, CPU를 이용하고 싶은 프로세스들 또한 큐에 삽입하여 줄을 세우고, 특정 입출력 장치를 이용하고 싶은 프로세스들 역시 큐에 삽입하여 줄을 세운다.

준비 큐(ready queue)

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

• 준비 상태에 있는 프로세스들의 PCB는 준비 큐의 마지막에 삽입 되어 CPU를 사용할 차례를 기다린다.

• 우선순위가 낮은 프로세스들이 먼저 큐에 삽입돼 줄섰을지라도, 우선순위가 높은 프로세스는 먼저 처리될 수 있다.

대기 큐(waiting queue)

• 입출력 장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄
  
  

• 같은 장치를 요구한 프로세스들은 같은 대기 큐에서 기달니다.
  • 입출력이 완료되어 완료 인터럽트가 발생하면
  • 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고
  • 이 PCB를 준비 상태로 변경한 뒤 대기 큐에서 제거
  • PCB는 준비 큐로 이동한다.

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

선점형 스케줄링

프로세스가 CPU를 비롯한 자원을 사용하고 있더라도,
운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식을 의미

• 어느 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식
• 프로세스마다 정해진 시간만큼 CPU를 사용하고, 정해진 시간을 모두 소비하여 타이머 인터럽트가 발생하면 운영체제가 해당 프로세스로부터 CPU자원을 빼앗아 다음 프로세스에 할당하는 방식

• 장점: 어느 한 프로세스의 자원 독점 막고, 프로세스들에 골고루 자원 배분 가능
• 단점: 문맥교환 과정에서 오버헤드가 발생할 수 있다.
  • 오버헤드: 오버헤드는 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등

비선점형 스케줄링

• 하나의 프로세스가 자원 사용하고 있다면, 그 프로세스가 종료되거나 스스로 대기상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없음
  • 하나의 프로세스가 자원 사용 독점 가능

• 장점: 문맥교환 횟수가 비교하여 발생하는 오버헤드가 적음
• 단점: 모든 프로세스가 골고루 자원 사용할 수 없다는 단점

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

• 선입 선처리 스케줄링
• 최단 작업 우선 스케줄링
• 라운드 로빈 스케줄링
• 우선순위 스케줄링
• 다단계 피드백 큐 스케줄링

선입 선처리 스케줄링(FCFS 스케줄링)

• First Come First Served Scheduling
• 비선점형
• 준비 큐에 삽입된 순서대로 프로세스들 처리

CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식

• 호위효과: 긴 시간을 기다려야만 하는 현상

최단 작업 우선 스케줄링(SJF 스케줄링)

• Shortest Job First Scheduling
• CPU 사용 시간이 짧은 간단한 프로세스를 먼저 실행
• 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 수도 있다.

라운드 로빈 스케줄링

• 선입 선처리 스케줄링 + 타임 슬라이스 개념 더해진 스케줄링 방식
• 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미
  • 타임슬라이스의 크기가 매우 중요하다.
• 정해진 시간만큼 사용한 후에도 아직 프로세스가 완료되지 않았다면, 다시 큐의 맨 뒤에 삽입된다. 이때 문맥교환이 발생한다.

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

• Shortest Remaining Time
• 최단 작업 우선 스케줄링 + 라운드 로빈 알고리즘을 합친 스케줄링 방식

  최소 잔여 시간 우선 스케줄링 하에서 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.

우선순위 스케줄링

• 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘
• 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링

기아

• 우선순위가 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있다.
• 계속 뒤로 밀림

에이징

• 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

다단계 큐 스케줄링

• 우선순위 스케줄링의 발전된 형태

  우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식

• 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해진다.

• 큐별로 타임 슬라이스를 여러 개 지정할 수 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수 있다.

다단계 피드백 큐 스케줄링

• 다단계 큐 스케줄링의 발전된 형태이다.
• 프로세스들이 큐 사이를 이동할 수 없었음
  👉 우선순위가 낮은 프로세스는 계속 연기될 여지가 있다.
  👉 기아현상 우려
  👉 우선순위가 낮은 프로세스 입장에서는 매우 불리

프로세스들이 큐 사이를 이동할 수 있다.

• 타임 슬라이스동안 실행이 끝나지 않으면 다음 우선순위 큐에 삽입된다.
• CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아지게 된다.

• CPU를 비교적 오래 사용해야 하는 CPU 집중 프로세스들: 우선순위 자연스레 낮아짐
• CPU 비교적 적게 사용해야 하는 입출력 집중 프로세스들:
  자연스레 우선순위가 높은 큐에서 실행이 끝난다.
• 기아현상 예방: 낮은 우선순위 큐에서 너무 오래 기다리고 있으면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법 적용
• 

339p
1. 3
2. 기아현상
에이징