CPU 스케줄링

[jay200333]

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

입출력 집중 프로세스(I/O bound process) : 입출력 작업이 많은 프로세스

• 실행 상태보다 입출력을 위한 대기 상태에 더 많은 시간이 소요됨

ex) 비디오 재생, 디스크 백업 작업을 담당하는 프로세스 등

CPU 집중 프로세스(CPU bound process) : CPU 작업이 많은 프로세스

• 대기 상태보다 실행 상태에 더 많은 시간이 소요됨

ex) 복잡한 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스 등

→ 입출력 집중 프로세스는 CPU 집중 프로세스에 비해 CPU 사용을 비교적 덜 하므로 입출력 집중 프로세스를 가능한 한 빨리 실행시켜 입출력장치를 작동시킨 후, CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적임

---

모든 프로세스의 PCB를 조회해 우선순위를 찾으면 비효율적이기에 스케줄링 큐 사용

스케줄링 큐

준비 큐(ready queue) : CPU를 이용하고 싶은 프로세스들이 있는 큐

대기 큐(waiting queue) : 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 있는 큐

---

선점형 스케줄링(preemptive scheduling) : CPU 자원을 할당받아 실행중인 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식

😁 장점 : 한 프로세스의 자원 독점 방지할 수 있음

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

비선점형 스케줄링(non-preemptive scheduling) : 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케줄링 방식

😁 장점 : 문맥 교환 횟수가 적기에 오버헤드 발생이 적음

😫 단점 : 한 프로세스가 자원을 독점할 수 있음

---

CPU 스케줄링 알고리즘

FCFS 스케줄링[선입 선처리 스케줄링](First Come First Served Scheduling) : 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링

→ 프로세스가 기다리는 시간이 매우 길어질 수 있음 → 호위 효과(Convoy Effect)

SJF 스케줄링[최단 작업 우선 스케줄링](Shortest Job First Scheduling) : CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식

→ 비선점형 스케줄링 알고리즘

RR 스케줄링(round robin scheduling) : 정해진 타임 슬라이스 만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링

→ 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간

→ 큐에 삽입된 프로세스가 정해진 시간만큼 CPU를 이용하고 정해진 시간이 지났음에도 프로세스가 완료되지 않은 경우 다시 큐의 맨 뒤에 삽입됨 → 이때 문맥 교환 발생

• 타임 슬라이스가 클 경우 : FCFS 스케줄링과 다를게 없고 호위 효과가 생길 수 있음
• 타임 슬라이스가 작은 경우 : 문맥 교환이 자주 발생하여 오버헤드가 발생할 수 있음

SRT 스케줄링[최소 잔여 시간 우선 스케줄링](Shortest Remaining Time) : SJF + RR

→ 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 이용하는 시간이 짧은 프로세스부터 실행하는 방식

우선순위 스케줄링(priority scheduling) : 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링

기아 : 우선 순위가 낮은 프로세스는 준비 큐에 먼저 삽입되었음에도 우선 순위가 높은 프로세스들에 의해 실행이 계속 연기 되는 현상

에이징 : 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식 ⇒ 기아 현상 해결

다단계 큐 스케줄링(multilevel queue scheduling) : 우선순위별로 준비 큐를 여러 개 사용하는 방식

→ 우선순위가 가장 높은 큐에 있는 프로세스 먼저 처리하고 그 다음 우선순위 큐에 있는 프로세스 처리

→ 큐를 여러 개 두어 유형별로 우선순위를 구분하여 실행할 수 있음

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

😫 단점 : 프로세스들이 큐 사이를 이동할 수 없으므로 기아 현상 발생 할 수 있음

다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling) : 다단계 큐 스케줄링과 비슷하게 작동하지만 프로세스들이 큐 사이를 이동할 수 있음

→ 새로 준비 상태가 된 프로세스가 있다면 우선 순위가 가장 높은 우선순위 큐에 삽입되고 타임 슬라이스 동아 실행 → 만약 프로세스가 실행이 끝나지 않았다면 다음 우선순위 큐에 삽입되어 실행

→ CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아짐

→ 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시켜(에이징 기법) 기아현상 예방할 수 있음

→ 가장 일반적인 CPU 스케줄링 알고리즘

---

스레드 스케줄링

커널 수준 스레드 : 커널이 직접 스레드를 관리하고 스케줄링

→ 스레드가 독립적으로 CPU를 할당받음 → 다중 CPU 활용 가능

😁 장점

• 프로세스의 스레드들을 프로세서에 한 번에 디스패치 할 수 있기에 멀티프로세서 환경에서 매우 빠르게 동작한다.
• 커널이 직접 스레드를 제공해 주기 때문에 안정성과 다양한 기능이 제공된다.

😫 단점

• 스케줄링과 동기화를 위해 커널을 호출하는데 무겁고 오래 걸린다.
• 문맥 교환이 빈번히 발생하여 성능 저하가 발생 → 오버헤드 증가

유저 수준 스레드 : 사용자 영역에서 스레드를 관리하고 스케줄링

• 프로세스 내의 Thread 관련 Library가 Thread를 관리한다.
• 유저 수준 스레드의 존재를 커널에서는 알지 못한다.
• 하나의 Thread라도 동작을 멈출 경우, 그 프로세스 전체가 Block 된다.
• 멀티 프로세서를 전혀 이용할 수 없다.
  • ex. new Thread() 같이 프로세스 내에서 Thread를 생성하는 것

😁 장점

• 스케줄링이나 동기화를 위해 커널을 호출하지 않기에 인터럽트 발생시 오버헤드가 적다.
• 문맥 교환 시 커널 개입 없음 → 빠른 전환 가능

😫 단점

• 시스템 전반에 걸친 스케줄링 우선순위를 지원하지 않는다.
• I/O 작업 등에 의해 하나라도 Block된다면 전체 스레드가 Block된다.

하이브리드 모델 : 커널 스레드와 사용자 스레드를 혼합하여 효율적

→ 블로킹 문제 해결 및 다중 CPU 활용 가능

---

장기 스케줄러(long term scheduler)

→ 어떤 프로세스를 준비 큐에 넣을 것인가 결정

디스크에서 어떤 프로그램을 가져와 커널에 등록할지(준비 큐에 등록할지) 결정한다.

• 수 십 초 내지 수 분 단위로 가끔 호출하기에 상대적으로 속도가 느린 것이 허용된다.
• 메모리에 동시에 올라가 있는 프로세스의 수를 조절하는 역할을 한다.

현대의 시분할 시스템에서 사용되는 운영체제에는 일반적으로 장기 스케줄러를 사용하지 않는다.

과거에는 적은 양의 메모리를 많은 프로세스들에게 할당하면 프로세스당 메모리 보유량이 적어져 장기 스케줄러가 이를 조절하는 역할을 했지만 현재의 운영체제에서는 프로세스가 시작되면 바로 프로세스에 메모리를 할당해 준비 큐에 넣어주게 된다.

중기 스케줄러(medium term scheduler)

→ 메모리에 적재된 프로세스 수 관리

너무 많은 프로세스에게 메모리를 할당해 시스템의 성능이 저하되는 경우 해결하기 위해 메모리에 적재된 프로세스의 수를 동적으로 조절하기 위해 추가된 스케줄러

중기 스케줄러의 등장으로 프로세스의 상태에는 중지(suspenden, stopped) 상태가 추가 되었으며, 중지 상태의 프로세스는 메모리를 통째로 빼앗기고 디스크로 스왑 아웃된다.

중지 상태는 중지 준비 상태와 봉쇄 중지 상태가 있다.

• 중지 준비(suspended ready) : 준비 상태의 프로세스가 중기 스케줄러에 의해 디스크로 swap out
• 봉쇄 중지(suspended block) : 봉쇄 상태의 프로세스가 중기 스케줄러에 의해 디스크로 swap out

중지 봉쇄 상태인 프로세스가 봉쇄 도었던 조건을 만족하게 되면 이 프로세스의 상태는 중지 준비 상태로 바뀌게 된다. 중지 상태에 있는 프로세스들은 중지 준비 상태이든 중지 봉쇄 상태이든 관계없이 메모리를 조금도 보유하지 않고 디스크에 통째로 스왑 아웃된 상태로 존재하게 된다.

단기 스케줄러(short term scheduler)

→ 메모리 내의 준비 상태에 있는 작업 중 실행 할 프로세스를 선택하여 CPU를 할당

CPU 스케줄러 라고도 하며 준비 상태의 프로세스 중에서 어떤 프로세스를 다음 번에 실행 상태로 만들 것인지를 결정한다. 시분할 시스템에서 타이머 인터럽트가 발생하면 단기 스케줄러가 호출된다.

스케줄러 종류	관련된 상태
장기 스케줄러	생성 상태 관리
중기 스케줄러	중단된 준비, 준비, 중단된 대기, 대기 상태 관리
단기 스케줄러	준비, 실행, 대기 상태 관리