-
CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업이라고 할 수 있으며, FCFS, SJF, 라운드로빈 등의 알고리즘들이 있습니다.
-
장기스케줄러 :
- 어떤 프로세스를 준비큐에 넣을지 결정하는 일을 담당한다.(프로세스의 상태 : new -> ready)
-
단기스케줄러 :
- 장기스케줄러에 의해 선별된 작업중 어떤작업을 해야할지 고르는 일을 담당한다.(프로세스의 상태 : ready -> running -> waiting -> ready)
-
중기스케줄러 :
- 메모리에 올라온 작업이 CPU가 감당하기힘든 상태가되어 시스템성능이 저하될수있는데 이를 해결하기위해 적재된 프로세스의 수를 동적으로 조절하는일을 담당한다.(프로세스의 상태 : ready-> suspended)
Q) 현재 CPU에서 장기스케줄러를 사용하고있나요? 사용하고있지않다면 그이유는 무엇인가요?
- 사용하고있지않습니다. 10개의 준비된 프로세스중 메모리에 적재할수있는것이 6개라고 가정했을때 선별하는것이 장기스케줄러인데 현재는 메모리의 크기도 커지기도했고, 가상메모리 관리 덕분에 메모리가 무한인것처럼 사용할수있어 준비된 10개의 프로세스를 모두 적재할수있기 때문입니다.
- 장기스케줄러에 의해 프로세스를 적재했는데 CPU가 감당하기 힘든상태가 되어 우선순위가 가장 낮거나 일정시간동안 활성되지않은 프로세스중 일부 메모리를 디스크의 스왑영역에 저장합니다. 이로인해 프로세스가 중지(suspended)상태가 됩니다. 장기스케줄러와 동일한이유로 현재 중기스케줄러는 사용되지않습니다.
- 장기스케줄러는 수십초, 수분단위로 호출되어 단기스케줄러보다 느린속도이고 단기스케줄러는 스케줄링 알고리즘에 따라 ms이하의 시간단위로 매우빈번하게 호출되므로 수행속도가 충분히 빨라야합니다.
-
선점형 스케줄러 :
- CPU를 선점하고있는 프로세스를 교체할수있는 스케줄링 방식
-
비선점형 스케줄러 :
- CPU를 선점하고있는 프로세스가 종료될때까지 교체할수없는 스케줄링 방식
- 선점형 알고리즘에는 라운드로빈, 멀티레벨큐, 멀티레벨피드백큐 등이 있습니다.
- 비선점형 알고리즘에는 SJF, HRN 등이 있습니다.
-
위 그림과같이 작업 평균처리시간이 A=100, B=10, C=10 이 소요되는 작업이 차례로 들어온경우 작업 평균반환시간이 늦어지는 문제가있으며, convoy effect를 야기할수있습니다.
- 호위 효과(convoy effect) 라고합니다. 짧은시간동안만 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상을 의미합니다.
-
작업마다 타임슬라이스를 할당받아 CPU를 선점하고, 타임슬라이스가 끝나면 다음작업으로 전환하는 방식으로 시분할 시스템에서 중요할수있는 응답시간을 개선할수있는 알고리즘입니다.
-
시분할 컴퓨터의 등장으로 시스템과 원활하게 상호작용 하기위해 스케줄링 알고리즘을 평가할때 '응답시간(작업이 도착해서 처음 스케줄될때까지의 시간 - 도착시간)'이라는 기준도 중요해지면서 효율적으로 시스템과 상호작용해 응답시간을 개선하고 CPU시간을 공정하게 할당하기위해서 등장했습니다.
- 기아상태
- 타임슬라이스가 짧을수록 작업의 응답시간은 좋아질수있지만, 너무 짧으면 context switching 비용이 전체 성능에 영향을 주게되고 타임슬라이스가 너무 길면 작업의 응답시간이 길어질수있습니다.
- 일반적으로는 작업별로 타임슬라이스 대비 context switching 비용을 따져봐야하지만 대부분 현대 운영체제들은 10~100msec로 할당합니다.
-
- 주기적으로 모든작업의 우선순위를 상향하는 방식이있습니다. 이렇게되면 프로세스가 굶지않는다는것을 보장받습니다.
다만 얼마나 자주 상향시킬것인지?에대해 생각해봐야합니다. 주기가 너무 크면 긴 실행시간을 가진 작업은 굶을수있고, 너무 작으면 I/O bound같은 대화형작업이 CPU를 적절하게 선점할수 없게됩니다.
- 멀티레벨 큐 : 2개이상의 특정 스케줄링 규칙을 따르는 스케줄링 큐로 구성되는 방식입니다. 각 프로세스를 특정기준(우선순위 혹은 기타속성)에 따라 적절한 대기열에 할당합니다 멀티프로세서 환경에서 단일큐 스케줄링의 단점인 동기화문제를 고려하지않아도 되고 캐시친화적이라는 장점이있지만 일부 CPU가 유휴상태가 될수있는등 작업의 불균형문제가 있습니다.
예를들어, 2개의CPU가 작업중이고 4개의 작업이 있다고 가정할때, 아래와같습니다.
각 큐에서 라운드로빈을 실행한다는 가정하에 아래와 같은 스케줄을 얻을수있습니다.
작업 A 하나로 B와 D보다 2배의 CPU를 차지하게되며, 더 심한경우 Q0에 있는 작업들만 먼저 끝나게 되면 아래와같이 1개의 CPU가 유휴상태가 될수있습니다.
- 멀티레벨 피드백 큐 : 2개이상의 큐로 구성되며 각각 다른우선순위가 배정되고,각 큐에남아있는 작업을 확인해서 작업을 이동시켜서(migration) 위에서 얘기했던 작업의 불균형문제를 해소할수있는 방식입니다. 대부분의 MLFQ들은 우선순위가 높은 큐는 보통 짧은 타임슬라이스가 주어지고, 우선순위가 낮은큐는 긴 타임슬라이스를 가지게되며, 일정주기를 가지고 우선순위를 상향시켜 기아문제를 해결하기도합니다.
둘의 가장 큰 차이점은 큐에 있는작업을 이동할수있는지 없는지가 되겠습니다.
- 멀티프로그래밍이 지향하는것이 CPU이용률을 최대한 높히는건데, 이때 시스템자원을 효율적으로 사용하기위해서 관리가 필요합니다.
- 스레드 라이브러리의 기능을통해 제어합니다. 동일한 프로세스내에 있는 스레드들끼리는 우선순위에 따라 스케줄링되지만 라이브러리마다 프로그래머가 스레드의 우선순위를 변경할수도 있습니다.
- PCB에 Process Priority 라는 공간에 적재됩니다.
-
일반적으로 대칭 다중처리라 불리는 각 프로세서가 스스로 스케줄링할수있는 방식으로 접근합니다. 큐 하나를 공통으로 사용하는 방식과, 프로세서별 큐를 가지는 방식이있습니다.
-
멀티프로세서 환경에서는 동기화문제를 신경써줘야합니다. 여러 CPU들이 동시에 사용하는 큐가 있다고 가정하면 동시성 문제가 생길수있기때문입니다. 이로인해 큐를 하나만사용하는 단일 큐 스케줄링은 멀티프로세서 환경에서 락을 삽입해야하기때문에 확장성이 결여되고, 성능이 저하될수있습니다. 반면 멀티큐 스케줄링에서는 작업이 각각 독립적으로 스케줄되기때문에 동기화 문제를 피할수 있습니다.
-
캐시친화성도 고려해야합니다.
먼저 설명드릴점은 cpu에서 프로세스가 실행될때 프로세스는 해당 cpu캐시와 TLB에 상태정보를 올려놓게 되고 이 일부정보로 인해 같은 CPU에서 실행되면 더 빨리 실행될수있습니다.
위와 같이 단일큐가 있고 4개의 CPU가 있다고 가정해보겠습니다. 각 CPU는 큐 하나를 공유해서 작업을 선택하기때문에 하나의 큐에있는 A,B,C,D,E는 여러 cpu에 나누어져 실행하게되어 아래와 같은 그림상태가 됩니다.
하나의 작업이 여러 CPU에서 실행되기때문에 캐시친화적이지 않다고볼수있습니다. 물론 단일큐도 이문제를 해결하기위해 가능한 동일한 CPU에서 하나의 작업이 실행되도록 시도하지만 구현 자체가 복잡하고 이 자체가 비용일수있습니다.
멀티 큐 스케줄링 기법은 CPU 개수가 증가할수록 큐의 개수도 증가할수 있으며, 이문제를 해결합니다. 2개의 CPU와 4개의 작업이 있다고 가정해보면 아래그림과 같습니다.
-
각 큐는 스케줄링 정책이 있을것이고 라운드로빈이라고 가정해보면 스케줄은 아래와같이 생성될수있습니다.
A,B,C,D 각각의 작업은 하나의 CPU에서 고정적으로 실행되어 캐시친화적이라고 볼수있습니다.
정리하자면 일반적으로 큐하나를 여러 CPU에서 공통으로 사용하는방식, CPU별 큐를 가지게되는 멀티큐 스케줄링방식을 사용하게되며 이는 각각 장단점이 있으며 동기화, 캐시친화성, 작업의 불균형(피드백 큐같이 이동하는방식으로 해결) 을 고려해야합니다.