CPU 스케줄링
기계어 명령은 크게 CPU 내에서 수행되는 명령, 메모리 접근을 필요로 하는 명령, 입출력을 동반으로 하는 명령으로 나눌 수 있다.
CPU 내에서 수행되는 명령은 Add를 예로 들 수 있다. CPU내의 레지스터에 있는 두 값을 더해 레지스터에 저장하는 명령이다.CPU 내에서만 수행되므로 명령의 수행 속도가 매우 빠르다.
메모리 접근을 수행하는 명령은 Load 명령과 Store 명령이 있다. Load 명령은 메모리에 있는 데이터를 CPU로 읽어들이는 명령이며, Store명령은 CPU에서 계산된 결괏값을 메모리에 저장하는 명령이다.
메모리 접근 명령은 CPU내의 명령보다는 오래 걸리지만 비교적 짧은 시간에 수행할 수 있는 명령이다.
입출력 명령은 시간이 오래걸리는 명령이고, 사용자 프로그램이 직접 수행할 수 없고 운영체제를 통해 서비스를 대행하도록 하고 있다.
사용자 프로그램은 CPU 작업과 I/O 작업의 반복으로 구성된다.
사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 것을 CPU버스트,
I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 느린 단계를 I/O버스트라고 부른다.
I/O 바운드 프로세스: I/O가 빈번해 CPU 버스트가 짧게 나타나는 프로세스 (대화형 프로그램)
CPU 바운드 프로세스: I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스 (계산 위주의 프로그램)
대부분의 경우 짧은 CPU 버스트를 가진다. 대화형 작업에서는 반응이 빨라야 하기 때문에 CPU연산을 수행하고 빠르게 결과를 출력해줘야 한다. 그렇기에 I/O 바운드 프로세스를 우선으로 CPU를 할당해주는 스케줄링이 필요하다. 만약 CPU 바운드 프로세스에게 우선적으로 CPU를 할당하게 된다면 I/O 바운드 프로세스는 응답 시간이 길어질 뿐 아니라 해당 I/O 장치도 그 시간 동안 작업을 수행하지 않는 휴면 상태가 되기 때문에 비효율적일 것이다.
CPU 스케줄러
CPU 스케줄러는 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드이다.
실행 상태에서 봉쇄 상태로 바뀌는 경우라던지, 준비 큐에서 꺼낸다던지, I/O 끝나서 봉쇄 상태를 준비 상태로 바꾼다던지, 타이머 인터럽트로 준비 상태로 바뀐다던지 등 많다.
비선점형 방식: CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지 CPU를 빼앗기지 않는 방법(실행 상태에 있던 프로세스가 I/O 요청으로 봉쇄 상태로 바뀌는 경우, 실행 상태에 있는 프로세스가 종료되는 경우)
선점형 방식: 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법(실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우, 봉쇄 상태에 있던 프로세스의 I/O작업이 완료되어 인터럽트가 발생하고 이 프로세스의 상태가 준비 상태로 바뀌는 경우)
디스패쳐
디스패쳐(dispatcher): 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드
디스패쳐는 한 마디로 문맥교환을 수행한다. 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간을 디스패처 지연시간 이라고 하고 이 시간의 대부분은 문맥교환 오버헤드에 해당된다.
스케줄링의 성능 평가
CPU 이용률: 전체 시간 중에서 CPU가 일을 한 시간의 비율을 나타냄
처리량: 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지(CPU버스트를 완료한 프로세스의 개수)를 나타냄
여러 프로세스가 CPU를 기다리고 있는 상황에서 주어진 시간에 더 많은 프로세스들이 CPU 작업을 완료하기 위해서는 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 할당하는 것이 유리하다.
소요시간: 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때 까지 걸린 시간. 즉, 준비 큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합을 뜻한다.
대기시간: CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
응답시간: 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간
타이머 인터럽트가 빈번히 발생할수록 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 짧아지므로 처음 CPU를 얻기까지 걸리는 시간은 줄어들게 되어 응답시간이 향상된다.
스케줄링 알고리즘
선입선출 알고리즘(FCFS)
온 순서대로 CPU를 할당한다. 이 방식은 자발적으로 CPU를 반납할 때까지 CPU를 빼았지 않는다.
평균 대기시간이 길어진다. 앞에 CPU 버스트 긴 프로세스 하나가 들어오고 뒤에 I/O바운드 프로세서들이 들어오게된다면 참 비효율적일 것이다. 하지만 만약, 그 반대로 CPU 버스트가 짧은 프로세스들이 앞에 막 들어오게된다면 괜찮을 것이다.
CPU 버스트가 짧은 프로세스가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상 콘보이 현상
최단작업 우선 스케줄링(Shortest-Job First: SJF)
CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다. 해당 방식은 평균 대기시간을 가장 짧게하는 최적 알고리즘이다. SJF 알고리즘은 선점형, 비선점형 두 가지로 구현할 수 있다.
선점형의 경우, 실행 중인 프로세스의 남은 CPU버스트 시간보다 더 짧은 CPU버스트 시간을 가지는 프로세스가 도착할 경우 CPU를 빼앗기게 된다. 이러한 선점형 SJF 를 SRTF(Shortest Remaining Time First)라고 부른다.
비선점형 방식의 경우 현재 CPU를 점유하고 있는 프로세스가 CPU 버스트를 모두 수행하고 스스로 CPU를 내어놓을 때까지 스케줄링을 하지 않는다. SJF는 CPU버스트가 긴 프로세스는 준비 큐에 줄 서서 무한정 기다리다 CPU를 영원히 할당받지 못하는 기아현상이 생길 수 있다.
우선순위 스케줄링
준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다. 이 때 우선순위는 우선순위값을 통해 표시하며 값이 작을수록 높은 우선순위를 가지는 것으로 가정한다. 만약 우선순위 결정 방식이 CPU버스트 시간이라면 SJF와 동일한 의미를 가지게 될 것이다. 시스템과 관련된 중요한 작업인가에 대한 순위도 매길 수 있다. 이 또한 SJF 와 같이 선점형 비선점형으로 구현할 수 있으며, 계속해서 우선순위가 높은 프로세스가 도착하게되면 기아현상이 발생할 수 있다.
이러한 문제점을 해결하기 위해 노화 기법을 사용할 수 있다. 이것은 기다리는 시간이 길어지면 우선순위를 조금씩 높여 언젠가는 CPU를 할당받을 수 있게 해주는 방법이다.
라운드 로빈 스케줄링
시분할 시스템의 성질을 가장 잘 활용한 새로운 의미의 스케줄링 방식이다.
각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되고, 이 시간이 경과되면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당한다. 그리고 반납한 프로세스는 준비 큐의 제일 뒤로 가서 줄을 서게 된다.
할당시간이 너무길면 FCFS와 같은 결과가 나타나게 된다. 그렇다고 너무 짧으면 문맥 교환의 오버헤드가 커지게 된다. 따라서 일반적으로 할당시간을 수십 밀리초 정도의 규모로 설정하게 된다.
라운드 로빈 스케줄링은 여러 종류의 이질적인 프로세스가 같이 샐행되는 환경에서 효과적이다. 대화형 프로세스의 빠른 응답시간을 보장할 수 있다는 장점이 있다.
할당시간이 만료되면 타이머 인터럽트로 CPU를 회수하고, 버스트 시간이 이보다 짧다면 스스로 반납한다. 해당 스케줄링의 기본적인 목적은 CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있도록 하는 동시에, CPU 버스트 시간이 긴 프로세스가 불이익을 당하지 않도록 하는 것이다.
공정한 스케줄링 방식이다. CPU를 쓰고자 하는 양이 적으면 소요시간이 짧아지고, 양이 많다면 소요시간도 비례한다.
멀티레벨 큐
준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법이다.
프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 두게 된다.
일반적으로 대화형 작업을 담기 위한 전위 큐와 계산 위주의 작업을 담기 위한 후위 큐로 분할되어 운영된다.
전위 큐는 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용하는 반면, 후위 큐는 응답 시간이 큰 의미를 가지지 않기 때문에 문맥교환의 오버헤드를 줄이기위해 FCFS 기법을 사용한다. 여기서 이제 여러 개의 준비 큐에 대해서 어느 큐에 먼저 CPU를 할당할 것인지 결정하는 스케줄링이 필요하다.
준비 큐에 우선순위를 부여하는 고정 우선순위 방식, 전체 CPU시간 중 전위 큐에 80%, 후위 큐에 20%와 같은 시간 비율을 할당하는 타임 슬라이스 방식이 있다.
멀티레벨 피드백 큐
여러 준비 큐를 사용한다는 점이 멀티레벨 큐와 같지만 큐 사이에서 이동이 가능하다는 점이 다르다.
앞서 말한 노화 기법을 이에 적용할 수 있다. 우선순위가 높은 준비 큐로 이동시키면서 말이다. 등등 프로세스를 상위큐에 승격시키는 조건들을 정해서 이용할 수가 있다.
다중처리기 스케줄링
CPU가 여러 개인 시스템을 다중처리기 스케줄링이라고 부른다. 프로세스를 준비 큐에 한 줄로 세워서 CPU가 알아서 뽑아가게끔 운용할 수도 있고, 특정 CPU에서 수행되어야 하는 프로세스가 있는 경우에는 CPU 별로 줄 세울 수도 있다.
여러 줄로 세울 경우에는 한 CPU에 작업이 편중되는 현상이 발생할 수 있으므로 부하를 적절히 분산되도록 하는 부하균형 메커니즘을 필요로 한다.
다중처리기 스케줄링 방식은 대칭형 다중처리와 비대칭형 다중처리로 나누어볼 수 있다.
대칭형 다중처리 방식: 각 CPU가 각자 알아서 스케줄링을 결정하는 방식
비대칭형 다중처리 방식: 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지 CPU는 이에 따르는 방식
실시간 스케줄링
시분할 시스템의 경우 작업 처리가 빠를수록 좋지만 특정 시간 이내에 처리 못했다고 심각한 상황이 발생하지는 않는다. 데드라인이 없다는 뜻이다. 그러나 실시간 시스템은 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야 한다.
실시간 시스템은 경성 실시간 시스템(hard real-time system)과 연성 실시간 시스템(soft real-time system)으로 나뉜다.
전자는 미사일 발사, 원자로 제어 등 정확히 시간을 지켜야 하는 시스템.
후자는 데드라인이 존재하지만 지키지 못했다고 해서 위험한 상황이 발생하지는 않는다. (ex. VOD, 스트리밍)
그래서 먼저 실시간 환경에서는 먼저 온 요청을 먼저 처리하기보다는
데드라인이 얼마 남지 않는 요청을 먼저 처리하는 EDF(Earlist Deadline First) 스케줄링을 널리 사용하게 된다.
연성 실시간 시스템처럼 일반 작업과 VOD 작업 등이 혼합된 환경에서는 데드라인이 존재하는 프로세스에게 일반 프로세스보다 높은 우선순위를 할당하는 방식도 사용되고 있다.
스케줄링 알고리즘의 평가
스케줄링 알고리즘의 성능 평가 방법
- 큐잉 모델: 수학적 계산을 통해 성능지표를 파악하여 평가
- 구현 및 실측: 원래 커널과 CPU 스케줄러를 수정한 커널에서 수행시켜보고 실행시간을 측정하여 평가
- 시뮬레이션: 실제 시스템 구현해 수행하는 것이 아닌 가상으로 CPU 스케줄링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력값으로 넣어 어떠한 결과가 나오는지 확인하는 방법. 입력 값은 가상으로 생성할 수도 있고, 실제 시스템에서의 CPU 요청 내역을 추출해 사용할 수도 있음. 이때 실제 시스템에서 추출한 입력값을 트레이스(trace)라고 부른다. 몇 초에 어떤 프로세스가 도착하고, 각각 CPU 버스트 시간을 얼마로 하는지에 대한 정보를 시간 순서대로 적어놓은 파일을 말한다.
'공부 기록들' 카테고리의 다른 글
메모리 관리 (0) | 2020.10.24 |
---|---|
프로세스 관리 (0) | 2020.10.23 |
앞으로 (0) | 2020.06.26 |
2020.06.21-22 JPA(5) (0) | 2020.06.21 |
2020.06.18 JPA(4) (0) | 2020.06.18 |