티스토리 뷰
참고
- 재학 대학의 '운영체제' 강의 자료
- 「수제비 2023 정보처리기사 실기 Vol. 2」 (NCS 정보처리기술사 연구회 지음)
내용 구성
- 용어 정리
- 스케줄링 메트릭스 (Scheduling Metrics)
- 스케줄링 정책: 비선점형 스케줄링 vs 선점형 스케줄링
- FCFS (First Come First Serve)
- SJF (Shortest Job First)
- HRN (Highest Response Ratio Next)
- SRT (Shortest Remaining Time First)
- RR (Round Robin)
- MLFQ (Multi-Level Feedback Queue)
- 마치며
1. 용어 정리
- 프로세스(Process)
메모리에 올라와서 실행 중인 프로그램으로, CPU를 할당받아 독립적으로 수행되는 스케줄링 개체이다. 반면 프로그램은 디스크에 존재하는 수동적인 바이너리 파일이다. 예를 들어 컴퓨터 배경화면에 저장된 워드 파일은 단지 디스크에 저장된 바이너리 파일이지만, 워드 파일을 더블 클릭하여 실행하면 메모리로 올라오고 CPU를 할당받아 수행되는 프로세스가 된다.
프로세스를 스케줄링의 관점에서 Job이라고도 부른다.
- 프로세스 상태 전이(State and Transition)
| 상태(State) | 설명 |
| new | 새로 생성된 상태 |
| ready | CPU를 할당받기 위해 Ready List에서 기다리는 상태 |
| running | CPU를 할당받아 실행 중인 상태 |
| waiting | 입출력 처리나 이벤트가 끝날 때까지 Waiting List에서 기다리는 상태 |
| terminated | 모든 수행이 종료된 상태 |
| 전이(Transition) | 상태(State) 변화 | 설명 |
| admitted | new → ready | 생성된 프로세스가 메모리로 올라옴 |
| dispatch (= schedule) | ready → running | Ready List 내 프로세스 중 우선순위에 따라 한 프로세스에 CPU 할당 |
| timeout (= preemptive) | running → ready | 주어진 타임 슬라이스를 다 사용하였거나 우선순위가 높은 프로세스에 의해 선점 당함 |
| sleep (= wait) | running → waiting | 입출력 처리나 이벤트가 발생하여 프로세스가 스스로 CPU 반납 후 Waiting List로 이동 |
| wakeup | waiting → ready | 기다리던 입출력 처리나 이벤트가 종료되어 Ready List로 이동 |
| exit | running → terminated | 프로세스가 running 상태에서 할 일을 모두 끝냄 |
- 문맥교환(Context Switch)
문맥(Context)은 수행을 멈춘 프로세스가 이후에 다시 수행되기 위해 필요한 모든 프로세스 정보들이며, PCB(Process Control Block)에 저장된다. 더욱 자세하게 말하면, eax, ebx 등 하드웨어 레지스터의 정보가 저장된다.
문맥 교환은 ① Context Save와 ② Context Restore라는 2개의 작업으로 구성된다. 예를 들어 CPU를 할당받아 수행되던 프로세스 A가 프로세스 B에게 CPU를 넘기는 상황에서 ① 프로세스A의 문맥을 A의 PCB에 저장하고 ② 프로세스B의 문맥을 B의 PCB에서 복구해오는 것이다.
문맥 교환에는 오버 헤드가 발생한다. 문맥 A를 저장하고, 문맥 B를 복구하는 과정에서 프로세스 A와 B 모두 수행되지 못한 채 방치(idle)되기 때문이다. 이 단점을 개선하기 위해 인텔은 하이퍼 쓰레딩에서 AS(Architectural State)라는 레지스터를 사용하는데, 프로세스의 상태를 저장하는 AS를 여러 개 둠으로써 하드웨어 수준에서 문맥 교환을 지원한다.
- PCB(Process Control Block)
운영체제가 각 프로세스를 관리하기 위해 필요한 프로세스 정보를 저장하는 곳으로, 각 프로세스는 개별적으로 PCB를 가진다. 프로세스 상태와 프로세스 아이디(pid), 문맥교환 시 필요한 레지스터 정보, 스케줄링 정보 등이 저장된다.
- 프로세스 스케줄링(Process Scheduling)
CPU라는 자원을 할당받길 원하는 여러 프로세스가 있을 때 어떤 프로세스에게 CPU를 할당할 것인지 지정하는 것이다.
- 타임 슬라이스(Time Slice)
한 프로세스가 CPU를 할당 받아 한 번에 수행될 수 있는 시간이다. 스케줄링 과정에서 작업 시간이 긴 프로세스가 CPU를 오랫동안 독점하지 못하도록 방지한다.
타임 퀀텀(Time Quantum)이라고도 한다.
타임 슬라이스 길이와 문맥 교환의 오버헤드는 비례 관계이다. 아래 각 스케줄링 알고리즘에서 확인할 테지만, 타임 슬라이스가 짧을수록 프로세스들의 응답률이 향상된다. 그러나 너무 과하게 짧아지면, 오히려 문맥 교환 오버헤드로 인해 성능이 저하될 수 있으므로 적절한 타임 슬라이스를 설정해야 한다.
- 워크로드(Workload)
수행되어야 할 작업의 양이다. 컴퓨터에서는 주로 프로세스들이 필요로 하는 자원의 양을 의미한다.
2. 스케줄링 메트릭스 (Scheduling Metrics)
| 용어 | 계산식 | 설명 |
| 반환 시간(Turnaround Time) | 반환 시간 = 종료 시간 - 도착 시간 | 프로세스가 입력되고 수행되어 완료될 때까지의 시간 |
| 응답 시간(Response Time) | 응답 시간 = 첫 수행 시간 - 도착 시간 | 프로세스가 입력되어 처음 수행되기까지의 시간 |
3. 정책: 비선점형 스케줄링 vs 선점형 스케줄링
사용 중인 CPU를 뺏을 수 있는지, 없는지로 스케줄링 정책이 구분된다.
- 비선점형 스케줄링(Non-Preemptive Scheduling)
한 번 CPU를 할당 받은 프로세스는 작업이 종료될 때까지 CPU를 독점한다. 해당 프로세스가 종료되기 전까지는 다른 프로세스가 CPU를 사용할 수 없다.
- 선점형 스케줄링(Preemptive Scheduling)
프로세스A가 CPU를 사용하고 있더라도, 그것보다 우선순위가 높은 프로세스B가 CPU를 뺏을 수 있다. 즉, 기존 프로세스를 중단시켜 CPU를 반납하게 한 후, 우선순위가 높은 프로세스가 CPU를 할당 받아 수행될 수 있다. 이때 문맥 교환이 발생한다.
- 비교
| 구분 | 비선점형 스케줄링 | 선점형 스케줄링 |
| 장점 | 모든 프로세스를 공평하게 처리한다. | 응답 시간이 빠르다. |
| 단점 | 작업 시간이 짧더라도, 긴 작업 시간을 가진 프로세스가 끝날 때까지 대기해야 한다. | 문맥 교환이 과하게 발생하면 오버헤드가 발생한다. |
| 알고리즘 | FCFS, SJF, HRN 등 | SRT, RR, MLFQ 등 |
| 활용 | 프로세스 간 작업 시간이 비슷한 환경 | 실시간 응답 환경 |
4. FCFS (First Come First Serve)
프로세스가 도착한 순서대로 수행된다. 먼저 온 것이, 먼저 수행되기 때문에 FIFO(First In, First Out)이라고도 한다.
- 장점: 자료구조 Queue를 사용하면 되므로 이해하기도, 구현하기도 쉽다.
- 단점: 긴 작업의 프로세스가 있다면, 짧은 작업의 프로세스 종료 시간이 뒤로 밀린다. (Convoy Effect)
| 프로세스 | 반환 시간 | 응답 시간 |
| A | 10 - 0 = 10 | 0 - 0 = 0 |
| B | 110 - 1 = 109 | 10 - 1 = 9 |
| C | 130 - 3 = 127 | 110 - 3 = 117 |
| D | 140 - 4 = 136 | 130 - 4 = 126 |
| 평균 | 95.5 | 63 |
5. SJF (Shortest Job First)
Ready List에 있는 프로세스들 중에서 짧은 작업 시간을 가진 프로세스에 높은 우선순위를 부여한다.
- 장점: 최적의 평균 반환 시간을 제공한다.
- 단점: 짧은 작업 시간을 가진 프로세스가 계속 들어올 경우 먼저 들어온, 긴 작업 시간을 가진 프로세스의 수행이 계속 뒤로 밀린다. (기아 상태)
| 프로세스 | 반환 시간 | 응답 시간 |
| A | 10 - 0 = 10 | 0 - 0 = 0 |
| B | 140 - 1 = 139 | 40 - 1 = 39 |
| C | 40 - 3 = 37 | 20 - 3 = 17 |
| D | 20 - 4 = 16 | 10 - 4 = 6 |
| 평균 | 50.5 | 15.5 |
6. HRN (Highest Response Ratio Next)
SJF에서 기아 상태이라는 단점을 해결하기 위한 기법으로, Response Ratio가 큰 긴 프로세스에 높은 우선순위를 부여한다. 즉, 대기 시간이 긴 프로세스의 우선순위를 높임으로써 기아 상태를 방지한다.
- 장점: 작업 시간이 긴 프로세스와 짧은 프로세스 간 불평등을 어느 정도 해소한다. SJF의 기아 상태를 최소화한다.
- 단점: 각 프로세스의 작업 시간을 계속 추적해야 하므로 오버헤드가 발생한다.
| 프로세스 | 반환 시간 | 응답 시간 |
| A | 20 - 0 = 20 | 0 - 0 = 0 |
| B | 50 - 10 = 40 | 20 - 10 = 10 |
| C | 80 - 20 = 60 | 60 - 20 = 40 |
| D | 60 - 30 = 30 | 50 - 30 = 20 |
| 평균 | 37.5 | 17.5 |
7. SRT (Shortest Remaining Time Next/First)
SJF에서 기아 상태를 방지하기 위해 만들어진 선점형 스케줄링 방식이다. 작업 시간이 더 짧게 남은 프로세스에 우선순위를 준다. 어떤 프로세스가 실행 중이더라도, 남은 작업 시간이 더 짧은 프로세스가 Ready List에 들어오면 새 프로세스를 우선적으로 수행한다.
- 장점: 작업 시간이 긴 프로세스의 기아 상태가 발생하지 않는다. SJF에 비해 평균 반환 시간과 평균 응답 시간이 짧다.
- 단점: 각 프로세스의 남은 작업 시간을 계속 추적해야 하므로 오버헤드가 발생한다.
| 프로세스 | 반환 시간 | 응답 시간 |
| A | 10 - 0 = 10 | 0 - 0 = 0 |
| B | 140 - 10 = 130 | 10 - 10 = 0 |
| C | 50 - 20 = 30 | 20 - 20 = 0 |
| D | 40 - 30 = 10 | 30 - 30 = 0 |
| 평균 | 45 | 0 |
8. RR (Round Robin)
FIFO처럼 먼저 도착한 순서대로 프로세스를 수행한다. 그러나 정해진 타임 슬라이스(Time Slice) 동안 프로세스의 작업이 끝나지 않는다면, 해당 프로세스를 Ready List의 맨 뒤로 보내고 다음 프로세스를 수행한다. 이 작업을 Ready List가 빌 때까지 반복한다.
타임 슬라이스가 클수록 문맥 교환 오버헤드가 적지만, 응답률이 나빠진다. 반면 타임 슬라이스가 작을수록 응답률은 향상되지만, 잦은 문맥 교환으로 인해 오버헤드가 증가한다. 따라서 적절한 타임 슬라이스를 설정해야 한다.
- 장점: 평균 응답 시간이 우수하다.
- 단점: 평균 반환 시간이 다소 나쁘다.
| 프로세스 | 반환 시간 | 응답 시간 |
| A | 30 - 0 = 30 | 0 - 0 = 0 |
| B | 100 - 10 = 90 | 10 - 10 = 0 |
| C | 70 - 20 = 50 | 30 - 20 = 10 |
| D | 60 - 30 = 30 | 50 - 30 = 20 |
| 평균 | 50 | 7.5 |
9. MLFQ (Multi Level Feedback Queue)
FIFO와 RR을 혼합한 방식이다. 여러 대기 큐가 존재하고, 각 큐는 서로 다른 우선순위를 갖는다. 우선순위가 고정되어 있지 않고, 프로세스의 과거 행동에 따라 유동적으로 변하기 때문에 "피드백Feedback"이라고 한다.
규칙
- 우선순위가 높은 프로세스가 낮은 프로세스보다 먼저 수행된다.
- 우선순위가 같은 프로세스들은 RR 방식으로 수행된다.
- 새로 들어오는 프로세스는 가장 높은 우선순위 대기 큐에 들어간다.
- 특정 레벨에서 한 프로세스가 총 타임 슬라이스 시간만큼 수행되었다면, 그 프로세스의 우선순위를 낮춘다. (아니면 기존 우선순위를 유지한다)
- 기아 상태를 해결하기 위해 일정 시간이 지날 때마다 모든 프로스세의 우선순위를 주기적으로 높여준다. (Boosting)
- 장점: 짧고 인터랙티브한 프로세스와 길고 배치 성격을 가진 프로세스 모두 공평하게 수행되도록 한다.
⭐ 처음에 A가 타임 슬라이스만큼 수행되었지만, ready queue가 비어 있기 때문에 우선순위를 낮추지 않는다.
| 프로세스 | 반환 시간 | 응답 시간 |
| A | 4 - 0 = 4 | 0 - 0 = 0 |
| B | 20 - 2 = 18 | 2 - 2 = 0 |
| C | 16 - 4 = 12 | 4 - 4 = 0 |
| D | 19 - 6 = 13 | 6 - 6 = 0 |
| E | 11 - 8 = 3 | 8 - 8 = 0 |
| 평균 | 10 | 0 |
10. 마치며
지금까지 프로세스 스케줄링 방법에 대해 살펴보았다. 여러 스케줄링 방법이 존재하고, 자신이 인터랙티브를 중요시하는지, 아니면 배치 작업을 중요시하는지 등에 따라 알맞은 방식을 선택해서 사용하면 된다.
C언어로 FCFS, SJF, RR, MLFQ를 구현한 코드가 궁금하다면 아래 깃허브 링크에서 확인할 수 있다.
GitHub - kmi0817/Scheduling-Simulator: [Operating System] implement a scheduling simulator <FCFS, SJF, RR, MLFQ>
[Operating System] implement a scheduling simulator <FCFS, SJF, RR, MLFQ> - GitHub - kmi0817/Scheduling-Simulator: [Operating System] implement a scheduling simulator <FCFS, SJF, RR, MLFQ>
github.com
⭐ 틀린 부분이 있다면 댓글로 말씀해주세요!