정의
- OS가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
=> 우선순위가 높은 프로세스를 빨리 처리해야 효율적 (우선순위는 PCB에 명시됨)
프로세스 종류
- CPU 집중 프로세스 = CPU 버스트가 많은 프로세스 (CPU를 많이 사용해야하는 프로세스)
※ CPU 버스트 = CPU를 이용하는 작업
- 입출력(I/O) 집중 프로세스 = 입출력 버스트가 많은 프로세스
※ 입출력(I/O) 버스트 = 입출력장치를 기다리는 작업
=> 입출력 집중 프로세스의 우선순위가 CPU 집중 프로세스의 우선순위 보다 높음
스케줄링 큐
- 실행될 프로세스들이 여러 개가 있으면 큐에 삽입되고 그 중에서 하나만 우선 실행되고 나머지는 CPU가 자유로워질 때까지 큐에서 대기하는 방식 (일반적으로 선입선출(FIFO) 방식을 따름)
- 프로세스들이 사용하고 싶어하는 장치의 종류(CPU, 입출력장치 등)에 따라 해당하는 장치와 연관된 큐에 프로세스들이 삽입됨
- 준비 큐 = CPU를 이용하고 싶어 준비 상태에 접어든 프로세스들이 삽입된 큐
- 대기 큐 = 입출력장치를 이용하고 싶어 대기 상태에 접어든 프로세스들이 삽입된 큐
선점형/비선점형 스케줄링
선점형 스케줄링(Preemptive scheduling)
- 하나의 프로세스가 자원을 사용하고 있을 때 다른 프로세스가 해당 자원을 강제로 빼앗을 수 있는 스케줄링
- 자원 독점을 막아 프로세스들에게 자원을 골고루 배분할 수 있음
- 문맥 교환(Context Switching) 과정에서 오버헤드 발생 가능성이 있음
비선점형 스케줄링(Non-Preemptive scheduling)
- 하나의 프로세스가 자원을 사용하고 있을 때 다른 프로세스가 해당 자원을 강제로 빼앗을 수 없는 스케줄링
- 선점형 스케줄링에 비하여 오버헤드 발생 가능성이 낮음
- 하나의 프로세스가 자원을 사용중일 때 다른 프로세스가 당장 자원을 사용해야 해도 끝날 때까지 기다려야 함 (독점)
대표적인 CPU 스케줄링 알고리즘
선입 선처리 스케줄링(FCFS 스케줄링, First Come First Served scheduling)
- 단순히 준비 큐에 삽입된 순서대로 CPU를 할당하는 비선점형 스케줄링
- 호위 효과(Convoy Effect) = 프로세스들이 CPU 할당을 기다리는 시간이 매우 길어질 수 있는 현상
최단 작업 우선 스케줄링(SFJ 스케줄링, Shortest Job First scheduling)
- CPU 사용 시간이 가장 짧은 프로세스부터 CPU를 할당하는 스케줄링
라운드 로빈 스케줄링(RR 스케줄링, Round Robin scheduling)
- FCFS 스케줄링 + 타임 슬라이스 => 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 사용하는 선점형 스케줄링
- 타임 슬라이스(Time Slice) = 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
최소 잔여 시간 우선 스케줄링(SRT 스케줄링, Shortest Remaining Time scheduling)
- SFJ 스케줄링 + RR 스케줄링
- 정해진 시간 만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스로 선택하는 스케줄링
우선순위 스케줄링(Priority scheduling)
- 프로세스들에 우선순위를 부여하고 가장 높은 우선순위를 가진 프로세스부터 CPU를 할당하는 스케줄링
- 기아(Starvation) 현상 = 우선순위가 낮은 프로세스가 준비 큐에 먼저 삽입되어있음에도 우선순위가 높은 프로세스에 의하여 실행이 계속해서 연기되는 현상
- 에이징(Aging) = 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식 => 우선순위가 낮아도 언젠가 우선순위가 높아짐
다단계 큐 스케줄링(Multilevel Queue scheduling)
- 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 => 우선순위가 가장 높은 큐에 있는 프로세스들에 먼저 CPU를 할당
- 우선순위를 프로세스가 아닌 큐 단위로 선정
- 프로세스들이 큐 사이를 이동할 수 없음 => 기아 현상 발생 가능
다단계 피드백 큐 스케줄링(Multilevel Feedback Queue scheduling)
- 프로세스의 큐 간 이동이 가능한 다단계 큐 스케줄링
- CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고 입출력 집중 프로세스의 우선순위는 상대적으로 높아짐
- 프로세스들이 큐 사이를 이동할 수 있기 때문에 에이징을 적용하여 기아 현상 해결 가능
- CPU 시간이 길면 우선순위가 낮아지고 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식의 스케줄링
댓글