01. CPU 스케줄링
CPU 스케줄링이란 작업을 처리하기 위해서 프로세스들에게 CPU를 할당하기 위한 정책을 계획하는 것으로 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것입니다.
가장 공정한 CPU 스케줄링은 무엇일까요 ?보통 그냥 CPU를 사용하고 싶어하는 프로세스들이 차례로 돌아가며 사용하는 방법이라고 생각하겠지만 이는 좋은방법은 아닙니다. 빨리 처리해야하는 프로세스가 있기 때문입니다.(= 프로세스마다 우선순위가 다르기 때문) 예를 들어 입출력 작업이 많은 프로세스(=입출력 집중 프로세스)의 우선순위는 CPU 작업이 많은 프로세스(=CPU 집중 프로세스) 의 우선순위보다 높습니다. 입출력 작업은 실행상태보다 대기상태에 더 많이 머무르기 때문에 실행을 빨리 끝내고(대기상태에 머물게 되면 CPU를 쓰지 않음) CPU 집중 프로세스에 CPU를 몰아서 쓸 수 있게 됩니다. 이처럼 각각의 상황에 맞게 CPU를 배분하는 것이 효율적입니다.
02. 프로세스 우선순위
02-1. 스케줄링 큐
프로세스의 우선순위는 PCB에 담겨있는데 일일이 모든 프로세스의 PCB를 뒤지는건 비효율적이므로, 운영체제는 각종 자원 별로 줄을 세워놓는 스케줄링 큐를 이용합니다. 즉, 스케줄링 큐란 자원을 이용하고싶어하는 프로세스들이 스는 줄이라고 생각하면 됩니다.
(스케줄링에서의 큐는 큐라고 해서 반드시 선입선출 방식일 필요는 없다.)
02-2. 준비큐(Ready queue)와 대기 큐
여러 프로세스가 돌아갈 때 CPU자원은 한정적이므로 번갈아가며 사용해야합니다. 이때 이 프로세스는 ready 상태가 되어 ready queue에 들어가서 CPU의 할당을 기다리게 됩니다. 그러다 자기 차례가 되면 디스패치 되어 실행상태가 되고, 실행 시간이 완료되면 다시 ready 상태로 돌아갑니다.
즉, 레디큐인 준비큐는 CPU를 (할당받기 위해) 이용하기 위해 기다리는 줄이고 대기큐는 입출력장치요청이 들어오면 입출력장치를 이용하기 위해 기다리는 줄입니다.대기큐에서 입출력완료라는 인터럽트가 발생하면 대기 상태 벗어나 레디큐로 접어들게 됩니다. 대기큐는 보통 입출력장치 별로 있으며, 같은 장치를 요구한 프로세스들은 같은 큐에서 대기합니다.
02-3. 선점형, 비선점형 스케줄링
프로세스가 자기 차례에 CPU를 할당받아 실행되는 도중 다른 프로세스가 들어올때 두가지 방법 선택이 가능합니다.
1. 현재 CPU 를 사용중인 프로세스로부터 CPU 자원을 빼앗아 급한 프로세스에게 주기 -> 선점형 스케줄링
2.현재 작업중인 프로세스를 작업이 완료될때까지 기다리기 -> 비선점형 스케줄링
선점형 스케줄링은 어느 한 프로세스의 자원 독점을 막고 프로세스들에게 골고루 자원을 배분할 수 있지만, 그만큼 많이 이루어지는 문맥교환 과정에서 오버헤드가 발생할 수 있습니다.
비선점형 스케줄링은 선점형 스케줄링에 비해 문맥교환에서 발생하는 오버헤드가 적지만, 모든 프로세스가 골고루 자원을 이용하기가 어렵습니다.
선점형 스케줄링 (preemptive scheduling)
장점 -> 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다.
단점 -> 그만큼 문맥교환과정에서 오버헤드가 발생할 수 있다.
비선점형 스케줄링(non-preemptive scheduling)
장점 -> 선점형 스케줄링에 비해 문맥 교환에서 발생하는 오버헤드가 적다
단점 -> 모든 프로세스가 골고루 자원을 이용하기 어렵다.
저는 선점형은 놀이공원에 매직패스라고 생각하고 비선점형은 매직패스가 없는 버전이라고 이해했습니다. 썩은 비유지만 ,, 전 비유로 생각하면 이해가 잘되더라구여,,,
03. CPU 스케줄링 알고리즘의 종류
1.선입 선처리 스케줄링
2. 최단 작업 우선 스케줄링
3. 라운드 로빈 스케줄링
4.최소 잔여 시간 우선 스케줄링
5.우선순위 스케줄링
6.다단계 큐 스케줄링
7.다단계 피드백 큐 스케줄링
03-1. 선입 선처리 스케줄링(FCFS : First Come First Served)
단순히 ready queue에 삽입된 순서대로 처리하는 비선점 스케줄링으로 먼저 CPU를 요청한 프로세스부터 CPU를 할당합니다. 앞선 프로세스가 실행시간이 길어질수록 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용이 있습니다. 이를 호위효과(convoy effect)라고 합니다.
호위효과를 방지하려면 어떻게 해야할까요? 실행시간이 짧은것부터 실행하면됩니다. 그래서 나온 스케줄링 알고리즘이....(더보기)
03-2. 최단 작업 우선 스케줄링 (SJF : Shortest Job First)
호위효과를 방지하기 위해 CPU 사용이 긴 프로세스는 나중에 실행하고, CPU 사용 시간이 짧은 프로세스는 먼저 실행합니다. 주로 비선점형 스케줄링으로 구분됩니다. 수행 시간이 긴 프로세스는 영원히 CPU를 할당 받지 못할 수도 있습니다.(starvation)
03-3.라운드 로빈 스케줄링 (RR : Round Robin)
돌아가며 차례대로 처리되는 알고리즘으로 선입 선처리 스케줄링(FCFS)과 타임 슬라이스(time slice)가 합쳐져있는 개념으로 정해진 타임 슬라이스 만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링입니다.
타임 슬라이스(=Time Quantum)란 각 프로세스가 CPU를 사용할 수 있는 정해진 시간입니다.
큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼만 사용합니다. 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입됩니다.(문맥교환) 타임 슬라이스의 크기가 중요한데 타임 슬라이스가 너무 크면 선입 선처리 스케줄링(FCFS)이랑 다를바가 없어서 호위효과가 일어나게 되고 , 타임 슬라이스가 작으면 문맥교환이 잦아져 context 오버헤드가 발생합니다.
03-4. 최소 잔여 시간 우선 스케줄링 (SRT : Shortest Remaining Time)
최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링 -> SJF + RR
정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택합니다.
03-5.우선순위 스케줄링
프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행합니다. 우선순위가 같은 프로세스들은 선입 선처리 스케줄링(FCFS)방식으로 처리됩니다. SJF와 SRT 스케줄링은 넓은 의미에서 우선순위 스케줄링의 한 종류로 볼 수 있습니다.
우선순위 스케줄링의 부작용으로는 기아현상(starvation)이 있습니다. 우선순위가 높은 프로세스만 계속 실행되면 우선순위가 낮은 프로세스는 ready queue에 먼저 삽입되었음에도 불구하고 실행이 계속 연기되어 방치게 됩니다. 이와같은 현상을 기아현상이라고 합니다.
기아현상 해결하기위해 나타나는 aging 기법이 있습니다. aging기법이란 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식으로 대기중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법입니다.
03-6.다단계 큐 스케줄링(Multilevel queue)
우선순위 스케줄링의 발전된 형태로 우선순위별로 ready 큐를 '여러 개' 사용하는 스케줄링 방식입니다. 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스를 처리합니다. 우선순위가 높은 큐에는 작은 time Quantum을, 낮은 큐에는 큰 time Quantum을 할당합니다.큐별로 프로세스를 유형별로 처리할 수 있게 되었다는 장점이 있지만 큐 간의 이동이 불가능하여 다른 큐로 이동할 수가 없습니다. 그렇기 때문에 여전히 starvation 발생이 가능합니다.
03-7. 다단계 피드백 큐 스케줄링(Multilevel feedback queue)
다단계 큐 스케줄링(multilevel queue)의 발전된 형태로 큐 간의 이동이 가능합니다.
즉, 큐 간의 이동이 가능한 multilevel queue라고 볼 수 있습니다. 새롭게 ready 상태가 된 프로세스를 가장 높은 우선순위에 삽입하고 타임 슬라이스 만큼 실행시킵니다. 만약,타임 슬라이스 동안 실행을 다 못끝냈다면 일단 낮은 우선순위 큐로 이동하게 됩니다. 그렇다면 자연스럽게 CPU 집중 프로세스는 CPU를 많이 써야하기 때문에 우선순위는 상대적으로 낮아지고 입출력 집중 프로세스의 우선순위는 상대적으로 높아지게 됩니다.
다단계 피드백 큐에서도 에이징 기법 적용하여 낮은 우선순위큐에서 기다리고 있었던 프로세스의 우선순위를 높일 수 있습니다.
즉, 어떤 프로세스의 CPU 시간이 길면 타임슬라이스 내에 다 실행하지 못하므로 우선순위가 낮아지고 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식(aging)하게 됩니다. 다단계 피드백 큐 스케줄링은 CPU 스케줄링 방식에 가장 일반적인 형태로 알려져 있습니다.
SJF는 거의 비선점형이다 라고 써놓긴했는데 SJF의 선점형 버전이 SRTF입니다. 알고리즘들은 간트차트로 과정을 확인하면 이해가 더 잘됩니다.
job queue
wait queue는 왜있어야되지 ->
RR -> 이름 유래
FCFS -> 프린터 입출력 대기열
SJF -> 사전에 작업시간을 알 수 있는 경우
SRT -> 실시간 게임
RR -> 대화형 운영체제
스케줄링의 시간 복잡도 & 공간 복잡도
FCFS -> 시간 복잡도 최악
SJF -> 시간 복잡도 보통
SRT -> 시간 복잡도가 높음
RR -> 작업 수와 타임 슬라이스에 따라 달라짐
우선순위 -> 시간복잡도 있는 편
다단계 큐 & 다단계 피드백 큐 -> 각각 너무 다름
프로세스 우선순위 -> 선점형 스케줄링 & 비선점 스케줄링
비선점 -> FCFS, SJF ,우선순위 스케줄링
선점 -> SRT , RR, 다단계 큐 / 다단계 피드백 큐
본 글은 인프런의 [혼자공부하는 컴퓨터 구조 + 운영체제 ] 인강을 참고하였습니다.
https://inf.run/W32w
[무료] 개발자를 위한 컴퓨터공학 1: 혼자 공부하는 컴퓨터구조 + 운영체제 - 인프런 | 강의
베스트셀러 『혼자 공부하는 컴퓨터 구조 + 운영체제』 저자 무료 직강. 개발자들이 꼭 알아야 할 컴퓨터 구조, 운영체제 전공서 요약집., 개발자 필수지식 컴퓨터 구조와 운영체제강의 하나로
www.inflearn.com
'CS > 운영체제' 카테고리의 다른 글
| [운영체제] 교착상태 (Deadlock) (0) | 2023.08.25 |
|---|---|
| [운영체제] 프로세스와 스레드 (0) | 2023.08.19 |
| [운영체제] 운영체제 기초 (0) | 2023.08.19 |
| [컴퓨터구조]입출력장치 [I/O device] (0) | 2023.08.18 |
| [컴퓨터구조]CPU의 성능향상기법 (0) | 2023.08.14 |
