[혼공컴운]4주차_Chap11 | CPU 스케줄링

<학습목표>

• 프로세스 우선순위를 이해한다.
• 스케줄링 큐의 개념과 필요성을 학습한다.
• 선점형 스케줄링과 비선점형 스케줄링의 차이를 이해한다.
• 다양한 CPU 스케줄링 알고리즘을 학습한다.

🎇 CPU 스케줄링 개요

🔗 CPU 스케줄링

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

• CPU 스케줄링은 컴퓨터 성능과도 직결되는 중요한 문제

🔗 프로세스 우선순위

• 우선순위가 높은 프로세스부터 먼저 처리해야 함

• 우선순위가 높은 프로세스에는 대표적으로 입출력 작업이 많은 프로세스가 있음

🔍 왜 입출력 작업이 많은 프로세스를 먼저 처리해야 하나?

➡ 프로세스의 종류마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에는 차이가 있음

프로세스의 종류
CPU 집중 프로세스 (CPU bound process)	복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스 같이 CPU 작업이 많은 프로세스
입출력 집중 프로세스 (I/O bound process)	비디오 재생이라 디스크 백업 작업을 담당하는 프로세스 같이 입출력 작업이 많은 프로세스

• 입출력 집중 프로세스는 입출력을 위한 대기 상태에 더 많이 머무르고, CPU 집중 프로세스는 실행 상태에 더 많이 머무름

➡ 따라서 입출력 집중 프로세스를 가능한 빨리 실행시켜 입출력장치를 끊임없이 작동시키고, 그 다음 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적임

➡ 입출력 집중 프로세스는 입출력장치가 입출력 작업을 완료할 때까지는 대기 상태이기 때문에 먼저 처리하면 다른 프로세스가 CPU를 사용할 수 있음

⭐CPU 버스트와 입출력 버스트

• CPU 버스트 : CPU를 이용하는 작업
• 입출력 버스트 : 입출력장치를 기다리는 작업

➡ 즉, 프로세스는 일반적으로 CPU 버스트와 입출력 버스트를 반복하며 실행함

➡ CPU 버스트가 많은 프로세스를 CPU 집중 프로세스, 입출력 버스트가 많은 프로세스를 입출력 집중 프로세스라고 함

---

• 운영체제는 프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 프로세스마다 우선순위를 부여함
  • 각 프로세스의 PCB에 우선순위를 명시하고 PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정함

🔗 스케줄링 큐

• 운영체제는 프로세스들의 우선순위를 확인하기위해 모든 프로세스의 PCB를 확인할 수 없음

➡ 운영체제는 프로세스들에게 '줄을 서서 기다리게 함'

• 이 줄을 스케줄링 큐로 구현하고 관리함
  • 자료구조 관점에서 큐는 선입선출 자료구조이지만 스케줄링에서의 큐는 선입선출 방식일 필요 없음

큐의 종류
준비 큐	CPU를 이용하고 싶은 프로세스들이 서는 줄
대기 큐	입출력장치를 이용하기 위해 대기 상태에 있는 프로세스들이 서는 줄

• 스케줄링 큐에 있는 프로세스들은 삽입된 순서대로 하나씩 실행하되, 그 중 우선순위가 높은 프로세스를 먼저 실행한다.

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

⚪ 선점형 스케줄링 (preemptive scheduling)

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

• 어느 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식

• 장점 : 어느 한 프로세스의 자원 독점을 막고 프로세스들에게 골고루 자원을 배분할 수 있음

• 단점 : 문맥 교환 과정에서 오버헤드가 발생할 수 있음

⚪ 비선점형 스케줄링 (non-preemptive scheduling)

하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식

• 하나의 프로세스가 자원 사용을 독점할 수 있는 스케줄링 방식

• 장점 : 문맥 교환의 횟수가 선점형 스케줄링 방식보단 적기 때문에 문맥 교환에서 발생하는 오버헤드는 선점형 스케줄링보다 적음

• 단점 : 하나의 프로세스가 자원을 독접 중이면 다른 프로세스들은 무작정 기다려야 함

🎇 CPU 스케줄링 알고리즘

알고리즘 종류

⚪ 선입 선처리 알고리즘 (FCFS (First Come First Served Scheduling))

준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식

• 프로세스들이 기다리는 시간이 매우 길어질 수 있음
• CPU를 가장 오래 사용하는 프로세스가 먼저 큐에 들어왔다면 CPU를 적게 사용하는 프로세스는 무작정 기다려야 함 ➡ 호위 효과

⚪ 최단 작업 우선 스케줄링 (SJF (Shortest Job First Scheduling))

준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식

• 최단 작업 우선 스케줄링은 기본적으로 비선점형 스케줄링
• 선점형으로 구현한 것이 최소 잔여 시간 우선 스케줄링임

⚪ 라운드 로빈 스케줄링 (round robin scheduling)

선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식

• 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 즉, 정해진 시간동안만 CPU를 사용할 수 있는 선점형 스케줄링 방식
• 라운드 로빈 스케줄링은 타임 슬라이스의 크기가 중요함
  • 타임 슬라이스의 크기가 너무 크면 선입 선처리 스케줄링과 다를 바 없이 호위 효과가 생길 수 있음
  • 타임 슬라이스의 크기가 너무 작으면 문맥 교환에 발생하는 비용이 커짐

⚪ 최소 잔여 시간 우선 스케줄링 (SRT (Shortest Remaining Time))

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

• 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택됨

⚪ 우선순위 스케줄링 (priority scheduling)

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

• 우선순위가 낮은 프로세스들은 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있음 ➡ 기아 현상

⭐ 이를 방지하기 위한 대표적인 기법 ➡ 에이징
에이징 기법 : 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

⚪ 다단계 큐 스케줄링

우선순위 스케줄링의 발전된 형태. 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식

• 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 높은 큐가 비어있으면 그다음 우선순위 큐에 있는 프로세스들을 처리함

• 큐를 여러 개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해짐

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

⚪ 다단계 피드백 큐 스케줄링

다단계 큐 스케줄링의 발전된 형태

• 다단계 큐 스케줄링에서는 프로세스들이 큐 사이를 이동할 수 없으므로 우선 순위가 낮은 프로세스는 계속 연기될 수 있음 ➡ 기아 현상

• 다단계 큐 피드백 스케줄링은 프로세스들이 큐 사이를 이동할 수 있으므로 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있음

• 다단계 큐 피드백 스케줄링은 구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘임