모든 프로세스는 운영체제로부터 자원을 할당받는다.
자원의 종류는 다르지만 공통으로 사용해야 하는 자원은 CPU이다.
따라서 운영체제는 프로세스에게 공정하고 합리적으로 CPU 자원을 배분해야 하고 이를 CPU 스케줄링이라고 한다.
운영체제가 프로세스에 CPU를 나누어주는 방법이 스케줄링에 대해서 정리한다.
프로세스 우선순위
프로세스마다 우선순위가 다름
입출력 작업이 많은 프로세스가 CPU 작업이 많은 프로세스보다 우선순위가 높다.
입출력 작업이 많은 프로세스 = 입출력 집중 프로세스(I/O bound process)
CPU 작업이 많은 프로세스 = CPU 집중 프로세스(CPU bound process)
따라서 입출력 작업이 많은 프로세스는 CPU를 사용하다가 입출력 요청에 의해 대기상태를 머무르는 시간이 더 많기 때문에
빠르게 CPU를 사용하다가 다른 프로세스에게 CPU를 넘기는 것이 가능
따라서 입출력 집중 프로세스가 CPU 집중 프로세스보다 우선순위가 높다.
운영체제는 PCB에 저장된 프로세스의 우선순위를 보고 CPU를 할당한다.
우선순위가 높은 프로세스는 더 빨리 더 자주 실행된다.
+ CPU 버스트와 입출력 버스트
CPU 버스트는 CPU를 이용하는 작업
입출력 버스트는 입출력장치를 기다리는 작업
따라서 입출력 집중 프로세스는 입출력 버스트가 많다.
CPU 집중 프로세는 CPU 버스트가 많다.
스케줄링 큐
운영체제가 프로세스마다 PCB의 우선순위를 확인 ❌
운영체제는 프로세스들을 사용하는 자원에 따라 줄을 세워서 기다리게 한다.
➡️ 스케줄링 큐
대표적인 종류
- 대기큐 : 입출력장치 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄 (인터럽트가 오면 준비큐로 간다.)
- 준비큐 : CPU를 이용하고 싶은 프로세스들이 서는 줄
방식
- 선점형 스케줄링
프로세스가 CPU를 비롯한 자원을 사용하고 있더라고 운영체제가 프로세로부터 자원을 강제로 빼앗아 다른 프로세스에게 할당할 수 있는 스케줄링 방식- 어느 한 프로세스의 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있는 장점이 있지만 그만큼 문맥 교환 과정에서 오버헤드가 발생한다.
- 비선점형 스케줄링
하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케줄링 방식- 문맥 교환 횟수가 선점형 스케줄링보다 적기 때문에 오버헤드 발생확률이 적지만 모든 프로세스에게 골고루 자원을 배분할 수 없다.
CPU 스케줄링 알고리즘
알고리즘의 작동 방식과 장단점에만 집중
용어는 중요하지 않다.
선입 선처리 스케줄링
First Come First Served Scheduling
말 그대로 먼저 들어온게 먼저 처리되는 비선점 스케줄링 방식
따라서 먼저 들어온게 CPU를 사용하는 시간이 길다면
뒤에 기다리는 프로세스들은 오랫동안 기다려야 한다.
이런 현상을 호위 효과(convoy effect)라고 한다.
오히려 CPU를 짧게 사용하는 프로세스가 앞에 위치해서 빨리 실행하고 나가는 것이 더 효율적으로 보인다.
최단 작업 우선 스케줄링
Shortes Job First Scheduling
앞서 선인 선처리의 호위 효과를 개선하는 방법
CPU를 사용하는 시간이 짧은 프로세스를 앞에 배치한다.
라운드 로빈 스케줄링
선업 선처리 스케줄링 + 타임 슬라이스
즉 선점형 스케줄링의 방식
타임 슬라이스란
프로세스가 CPU를 사용할 수 있는 정해진 시간
타임 슬라이스의 크기는 매우 중요하다
지나치게 크면 사실상 선입 선처리와 똑같은 방식으로 운영됨
너무 짧으면 프로세스를 전환하는 비용이 더 많이 든다.
최소 잔여 시간 우선 스케줄링
Shortest Remaining Time 스케줄링
= 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
최소 잔여 시간 우선 스케줄링 하에서 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세로는 남아있는 작업 시간이 가장 적은 프로세스가 선택
우선순위 스케줄링
프로세스들에 우선순위 부여
(최단 작업 우선 스케줄링, 최소 잔여 시간 우선 스케줄링도 넓은 의미해서 우선순위 스케줄링)
발생하는 문제 "기아"
우선순위가 낮은 프로세스를 무한정 기다리는 문제가 발생할 수 있음
해결방법 "에이징"
오랫동안 대기한 프로세스의 우선순위를 점차 증가시키는 방식
다단계 큐 스케줄링
발전된 우선순위 스케줄링
우선순위 별로 준비큐를 여러 개 사용하는 스케줄링
우선순위가 가장 높은 큐가 비어있으면 다음 우선순위 큐로 이동하면서 처리
큐마다 타임 슬라이스를 별도로 지정 가능
큐마다 스케줄링 알고리즘을 다르게 설정 가능
다단계 피드백 큐 스케줄링
다단계 큐 스케줄링 + 프로세스가 큐 이동 가능
다단계 큐 스케줄링은 우선순위가 낮은 프로세스는 계속 기다려야 한다,
따라서 프로세스가 큐를 이동하는 방식이 도입되었다.
새로 준비 상태가 된 프로세스가 있다면 우선순위가 가장 높은 우선순위 큐에 삽입되고 타임 슬라이스 동안 실행
➡️ 만약 프로세스가 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행
이 방식을 반복한다.
결국 CPU를 오래 사용해야 하는 프로세스는 계속 우선순위가 낮아진다.
CPU 집중 프로세스는 우선순위가 점차 낮아지고 입출력 집중 프로세스는 우선순위가 점차 높아진다.
