CPU 스케줄링
- 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
- 컴퓨터 전체 성능과도 직결되는 중요한 문제
- CPU를 그저 차례대로 돌아가며 사용하는 것 보다 각각의 상황과 요구에 맞게 배분하는 것이 더 효율적
- 그러므로 프로세스 우선 순위에 따라 실행됨
- 프로세스 우선순위는 사용자가 직접 설정할 수도 있고 운영체제가 내부적으로 정해준 우선 순위가 있기도 함
프로세스 우선순위(priority)
- 입출력 작업이 많은 프로세스(=입출력 집중 프로세스)의 우선순위는
CPU 작업이 많은 프로세스(=CPU 집중 프로세스)의 우선순위보다 높음- 프로세스마다 비디오 재생, 디스크 백업과 같이 입출력작업을 많이 하는 프로세스도 있고,
컴파일 작업이나 복잡한 수학 연산과 같이 CPU를 주로 사용하는 프로세스도 있음 - 입출력작업이 많은 프로세스는 CPU 집중 프로세스보다 대기 상태에 많이 머무르게 됨
- 그렇기 때문에 입출력 집중 프로세스를 빨리 처리해버리고, CPU 집중 프로세스에게 CPU를 더 많이 할당
- 프로세스마다 비디오 재생, 디스크 백업과 같이 입출력작업을 많이 하는 프로세스도 있고,
- 프로세스 우선순위는 PCB에 저장됨
- 프로세스 우선순위가 높은 프로세스는 더 빨리 더 자주 실행됨
- 프로세스 우선순위는 간단한 명령어(우측 위)나 프로그램(아래)을 통해 확인할 수 있음
스케줄링 큐(Scheduling Queue)
- PCB 마다 우선순위가 적혀있지만, 운영체제 입장에서는 다음에 CPU를 사용할 프로세스를 선정하기 위해 일일히 PCB 값을 찾아보는 건 비효율적임
- 이는 CPU뿐만 아니라 입출력장치나 메모리도 해당되는 이야기
- 그래서 특정 자원을 이용하고 싶어하는 프로세스들을 큐에 삽입한 뒤, 줄을 세워서 자원을 이용하도록 만듦
- 원래 Queue는 자료구조 관점에서는 선입선출(FIFO) 구조이지만, 스케줄링Q에서 이야기하는 Q는 반드시 선입선출일 필요는 없음! 즉, 먼저 삽입되었다고 해서 먼저 처리되는 것이 아닌 우선순위에 따라 처리됨
준비큐와 대기큐
- 스케줄링 큐에 여러 종류가 있지만, 대표적으로 대기큐와 준비큐가 있음
- 준비큐 : CPU를 이용하고자 하는 프로세스들이 기다리는 줄
- 대기큐 : 입출력장치를 이용하고 싶은 프로세스들이 기다리는 줄
- 대기큐는 보통 입출력장치별로 있는 경우가 많음
- 그래서 같은 장치를 요구한 프로세스들은 같은 큐에서 대기함
- 예를 들어 PID 123번 하드 디스크 입출력 완료 인터럽트를 받으면, 하드디스크 대기 큐에서 PID 123번 PCB를 찾은 뒤 준비 큐로 이동시킴
프로세스 상태 다이어그램
선점형과 비선점형 스케줄링
- 어떤 프로세스가 실행 중인데, 갑자기 급하게 실행해야하는 프로세스가 나타나면 어떻게 관리할까?
- 현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아 다른 프로세스에 할당
OR - 현재 CPU를 사용 중인 프로세스의 작업이 끝날 때까지 프로세스 기다리기
- 현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아 다른 프로세스에 할당
선점형 스케줄링(Preemptive Scheduling)
- 현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아 다른 프로세스에 할당
- (+) 어느 한 프로세스의 자원 독점을 막고 프로세스들에게 골고루 자원을 배분할 수 있음
- (-) 그만큼 문맥 교환 과정에서 오버헤드가 발생할 수 있음
- 프로세스 상태 다이어그램에서
실행 상태에 있던 프로세스가 타이머 인터럽트가 발생하면 준비상태로 바뀌는데,
이런 것도 운영체제가 이 프로세스로부터 CPU 자원을 딱 뺏어서 다음 차례의 프로세스한테 CPU 자원을 넘겨주는 것이므로 이것도 선점형 스케줄링임
비선점형 스케줄링(Non-preemptive Scheduling)
- 현재 CPU를 사용 중인 프로세스의 작업이 끝날 때까지 프로세스 기다리기
- 작업이 대기 상태나 종료 상태로 바뀌기 전까지는 다른 프로세스가 끼어들 수 없는 방식
- (+) 선점형 스케줄링에 비해 문맥 교환에서 발생하는 오버헤드가 적다
- (-) 모든 프로세스가 골고루 자원을 이용하기 어렵다
스케줄링 알고리즘
스케줄링 알고리즘은 굉장히 다양하고, 운영체제마다 다름.
스케줄링 알고리즘을 있는 그대로 외우기 보단,
알고리즘의 아이디어(작동 방식, 장단점)에 집중하기
목차
- 선입 선처리 스케줄링
- 최단 작업 우선 스케줄링
- 라운드 로빈 스케줄링
- 최소 잔여 시간 우선 스케줄링
- 우선순위 스케줄링
- 다단계 큐 스케줄링
- 다단계 피드백 큐 스케줄링
1. 선입 선처리 스케줄링
= FCFS(First Come First Served) 스케줄링
- 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
- 먼저 CPU를 요청한 프로세스부터 CPU 할당
- 단점 : 호위 효과
프로세스들이 기다리는 시간이 매우 길어질 수 있음
- 위 사진과 같이 가장 먼저 실행되는 프로세스의 길이가 가장 길면, 뒤에 있는 프로세스들의 대기 시간이 증가해 전체적인 평균 대기 시간이 길어짐.
2. 최단 작업 우선 스케줄링
= SJF (Shortest Job First) 스케줄링
- 호위 효과를 방지하기 위해 CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스는 먼저 실행
- 즉, CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식
- 선점형 또는 비선점형으로 구현할 수 있지만, 기본적으로는 비선점형 스케줄링으로 분류됨
- 선점형으로 구현된 최단 작업 우선 스케줄링은 최소 잔여 우선 스케줄링 참고
3. 라운드 로빈 스케줄링
= RR(Round Robin) 스케줄링
- 라운드로빈 : 차례대로 돌아가면서 무언가 하는 것
- 선입 선처리 스케줄링 + 타임 슬라이스(time slice)
- 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
- 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
- 일단 큐에 삽입된 순서대로 프로세스들을 처리하되 정해진 시간만큼만 CPU를 쓰도록 하는 방식
- 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입(문맥 교환)
- 타임 슬라이스가 중요함
- 타임 슬라이스가 너무 크면, 호위 효과 발생
- 타임 슬라이스 크기가 너무 작으면 문맥 교환에 발생하는 오버헤드 때문에 CPU 부담 증가
4. 최소 잔여 시간 우선 스케줄링
= SRT (Shortest Remaining Time) 스케줄링
- 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
- 최단 작업 우선 스케줄링 : 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘
- 라운드 로빈 스케줄링 : 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘
- 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택
5. 우선순위 스케줄링
- 프로세스들에 우선순위를 부여하고, 우선 순위가 높은 프로세스부터 실행
- 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
- 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링 모두 넓은 의미에서 우선 순위 스케줄링에 속한다고 볼 수 있음
기아 현상 (Starvation)
- 우선순위 스케줄링의 근본적인 문제점
- 우선순위 높은 프로세스만 계속 실행됨
- 우선순위 낮은 프로세스는 준비큐에 먼저 삽입되더라도 실행이 계속 연기됨
에이징 기법(aging)
- 기아 현상을 방지하기 위한 기법
- 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
- 대기 중인 프로세스의 우선 순위를 마치 나이 먹듯 점차 증가시키는 방법
- 우선순위가 낮아도 언젠가는 우선순위가 높아짐
6. 다단계 큐 스케줄링
= Multilevel queue 스케줄링
- 우선순위 스케줄링의 발전된 형태
- 우선순위별로 준비 큐를 여러개 사용하는 스케줄링 방식
- 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
- 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리
- 우선순위 0번이 가장 우선순위가 높으면 0번 먼저 다 처리하고 그 다음 우선순위1번 처리하는 방식
- 큐를 여러개 둠으로써 프로세스 유형별로 우선순위를 구분하는 것이 쉬워짐
- 어떤 큐에는 입출력 집중 프로세스 삽입, 어떤 큐에는 CPU 집중 프로세스 삽입
- 어떤 큐는 타임 슬라이스를 적게 지정, 어떤 큐는 크게 지정
- 어떤 큐는 선입 선처리 방식 스케줄링, 어떤 큐에는 라운드로빈 스케줄링 적용 등
- 큐 별로 스케줄링을 달리 적용해서 프로세스를 유형별로 관리하기 쉬워짐
- 단점 : 기아 현상
- 다단계 큐 스케줄링은 큐 간에 프로세스 이동이 불가능함
- 그래서 우선순위가 낮은 프로세스는 계속 낮은 큐에 머물러 기아 현상 발생
7. 다단계 피드백 큐 스케줄링
= Multilevel feedback queue 스케줄링
- 다단계 큐 스케줄링의 발전된 형태
- 큐 간의 이동이 가능한 다단계 큐 스케줄링
동작 방식
- 새롭게 준비 상태가 된 프로세스를 일단 가장 높은 우선순위에 삽입
- 일정 시간(타임 슬라이스)만큼 CPU를 할당 받아서 사용
- 실행이 끝났다면 끝. 하지만 실행이 끝나지 않았다면 그땐 한 칸 낮은 우선순위 큐로 이동 (0 → 1)
- 또 실행이 안끝났으면 한 칸 낮은 우선순위로 또 이동
- 실행이 끝날 때까지 반복
- 이 과정에서 자연스럽게
CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고 (실행에 오랜 시간이 걸리므로),
입출력 집중 프로세스의 우선순위는 상대적으로 높아짐
다단계 피드백 큐에서의 에이징 기법 적용
- CPU를 엄청 많이 사용하는 프로세스의 경우 우선순위가 낮아져 실행되지 못할 수 있음
- 그러므로 일정 시간 이상 낮은 우선순위 큐에서 기다렸던 프로세스가 있다면 이 프로세스의 우선순위를 점차 높임으로써 에이징 기법을 적용함
다단계 피드백 큐 스케줄링 정리
- 어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아지고,
어떤 프로세스가 낮은 우선 순위 큐에서 너무 오래 기다리면 우선 순위를 높이는 방식 - CPU 스케줄링 방식의 가장 일반적인 형태
출처 : 혼자 공부하는 컴퓨터구조 + 운영체제 (저자 강민철)
'취업역량강화 > 컴퓨터공학' 카테고리의 다른 글
| [운영체제] 교착 상태와 해결 방법 (0) | 2026.02.21 |
|---|---|
| [운영체제] 프로세스 동기화(뮤텍스 락, 세마포, 모니터) (0) | 2026.02.19 |
| [운영체제] 파이썬으로 프로세스와 스레드 다루기 (0) | 2026.02.15 |
| [운영체제] 프로세스와 스레드 (0) | 2026.02.13 |
| [운영체제] 운영체제(정의, 핵심기능, 커널, 이중모드와 시스템 호출) (0) | 2026.02.11 |