Context Switching에 대해서는 앞 포스트에서도 몇 번 언급이 되었다. 사실, 프로세스를 이야기 하면서 필연적으로 등장할 수 없는 존재이기 때문에, 해당 내용만 먼저 설명했어야 하는게 아닌가 하는 생각이 든다.
프로세스의 상태
프로세스는 각자의 상태 를 갖고 있다. 프로세스가 현재 동작중일 수 있고, CPU에게 작업이 할당되기 전 까지 대기할 수도 있고, 아니면 앞에서 설명한 인터럽트에 놓일 수도 있기 때문이다.
각각의 상태는 PCB에 저장된다.
- New: 프로세스가 생성 중
- Running: 명령어들이 실행되고 있음
- Waiting: 프로세스가 이벤트를 대기하고 있음 (입출력 완료/신호 수신)
- Ready: 프로세스가 CPU에 스케쥴링 되기를 대기 중
- Terminated: 프로세스가 종료 됨
Context Switching
앞에서, Context에 대해 다음과 같이 정의했었다.
프로세스의 상태와 관련된 레지스터의 집합을 의미한다.
그렇다면 자연스럽게 Context Switching의 의미도 알 수 있을 것이다. 레지스터의 값을 교체하는 것이지 않을까?
싱글 코어 CPU는 한 번에 하나의 프로세스만 처리할 수 있기 때문에, 그 프로세스가 동작하는 동안 레지스터의 값들은 모두 현재 실행중인 프로세스와 연관이 있을 것이다. 그러나 만약 다른 프로세스를 사용하게 된다면, 현재 레지스터의 값들을 모두 바꿔야 한다.
그런데 여기에 한 발짝 더 나아가서, 현재 실행중인 프로세스가 다른 프로세스로 교체 되는데, 만약 현재 프로세스의 작업이 끝나지 않았다면? 그렇다면 지금까지 실행한 작업들을 다 저장해야 한다. (그래야 이어서 할 수 있으니...) 따라서, 기존의 Context를 저장하고, 새로운 프로세스를 맞이할 준비를 하는 것을 Context Switching 이라고 부른다.
우리는 앞에서 PCB, TCB라는 자료구조에 대해 알아보았는데, 이 두 자료구조에는 이런 레지스터의 값들을 저장할 수 있는 공간이 존재했었다!
프로세스 스케쥴링
그렇다면, 프로세스를 CPU가 어떤 순서대로 처리해야 효율적으로 처리할 수 있을까? 이 방법을 연구하기 위해 수많은 스케쥴링 방법이 도입되었다.
스케쥴링 방법이 잘못되면 하나의 프로세스만 오래 붙잡을 수도 있고, 심지어 어떤 프로세스는 아예 선택되지 않아 절대 실행되지 않는 일이 발생할 수도 있다. 따라서, 좋은 스케쥴링 알고리즘이 필요하다.
스케쥴러의 분류
스케쥴러는 크게 장기, 단기, 그리고 중기로 분류할 수 있다.
- 장기 스케쥴러 (Long-Term Schedular)
- 어떤 프로세스를 Ready Queue에 삽입할지 결정하는 역할을 함.
- 프로그램을 가져와 커널에 등록하면 프로세스가 되는데, 어떤 프로그램을 가져와 등록할지 결정하는 역학을 함.
- 일반적으로 수십 초 ~ 분 단위로 호출되기 때문에 속도가 느려도 괜찮다.
- 전체적으로 메모리에 올라오는 프로세스의 수를 조절하는 역할을 함.
- 단기 스케쥴러 (Short-Term Schedular)
- Ready 상태에 있는 프로세스 중 어떤 프로세스를 CPU에 할당할 지 결정하는 역할을 함.
- 이후 설명할 스케쥴링 알고리즘은 대부분 단기 스케쥴러에 적용 됨.
- ms 단위로 빈번하게 호출되기 때문에 속도가 빨라야 함.
- 중기 스케쥴러 (Medium-Term Schedular)
- 장기 스케쥴러와는 반대로 역으로 메모리에 적재된 프로세스를 내림.
사실 요즘은 단기 스케쥴러만 있다. 이후에 설명할 Virtual Memory가 발달한 이후 메모리의 크기에 제약이 없어졌고, 그래서 최근 운영체제는 그냥 모든 프로세스를 전부 메모리에 적재한다.
따라서 이후 설명할 스케쥴링의 경우, 단기 스케쥴러에 초점을 맞춰 설명할 것이다.
First-Come, First-Served (FCFS)
가장 간단한 방법으로, CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다. 구현은 일반적인 FIFO 큐를 활용하면 쉽게 구현할 수 있다.
구현도 쉽고, 코드도 짧지만, 대기시간이 한없이 길어질 수 있다.
프로세스가 P1, P2, P3이 있고, Burst Time이 각각 24, 3, 3이라고 하자.
P1 → P2 → P3 순으로 가면, 대기 시간은 각각 0, 24, 27이고 평균 대기시간은 17ms이다.
P2 → P3 → P1 순으로 간다면, 대기 시간은 각각 6, 0, 3이고, 평균 대기시간은 3ms이다. 따라서 FCFS Queue에 들어가는 순서에 따라 시간이 크게 변할 수 있다.
예시를 하나만 보자. CPU-bound 프로세스 1개와 I/O-Bound 프로세스 여러개가 있다고 하자. CPU-bound 먼저 들어가면 긴 시간을 한참동안 기다리다가, I/O 요청을 위해 I/O Queue로 이동하게 되면, 다른 프로세스들은 빠르게 움직인다. (I/O Burst가 기니까) 그러다 CPU-bound 프로세스가 Ready Queue에 가게 되면 또 한없이 기다려야 한다... → 우리는 이런 상황을 Convey Effect (다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것.) 라고 부른다.
Shortest-Job-First (SJF)
각 프로세스에 CPU burst 길이를 남기도록 하고, 이용 가능해지면 Burst 시간이 가장 짧은 프로세스를 할당한다.
즉, P1, P2, P3, P4의 Burst Time이 6, 8, 7, 3이면,
다음과 같이 할당할 수 있다.
실제로 증명을 하면 최소의 평균 대기 시간을 가진다는 것을 알 수 있다. (그리디 알고리즘)
현실은... CPU burst 시간을 어떻게 알 수 있냐는 것이다. 그래서 이전 CPU burst 시간을 기록해서 이후의 시간을 추측한다. 즉, 단기 CPU 스케쥴링에서는 SJF를 사용하기에 현실적으로 어려움이 있고, 장기 CPU 스케쥴링에서 많이 사용된다.
Tn을 n번째 CPU burst의 길이라고 하면, 0 < a < 1에 대해서, 이라는 공식이 성립하는데, t는 최근의 정보를, τ은 과거의 역사를 저장한다. 매개변수 a의 값은 최근의 값과 이전 값의 가중치를 제어한다. 식을 최대한 확장하면,
이라는 공식이 나올 것이다. 0 < a < 1 이므로, 더해지는 값은 점점 갈 수록 감소하는 경향을 띌 수 밖에 없다.
또한, SJF는 선점/비선점형이 모두 가능한데, 만약 새로운 프로세스가 들어올때 현재 실행되고 있는 프로세스와 비교해서 CPU burst 시간이 짧다면, 선점형에 한해 현재 실행되고 있는 프로세스를 빼앗을 것이다.
Priority Scheduling
사실 SJF는 우선순위 스케쥴링의 일부이다. 당연히 우선순위 스케쥴링은 우선순위를 기준으로 하여 높은걸 먼저 배치할 것이다.
우선순위의 요건은 다양한데, 시간제한, 메모리 요구, 파일 수, 평균 I/O burst, 평균 CPU burst...
단점이라면, 무한 봉쇄(indefinite blocking)과 기아 상태(starvation)이 발생할 수 있다는 것이다. 만약 우선순위가 낮은 프로세스가 있다면, CPU를 할당받지 못하고 계속해서 뒤쪽에 머물러 있을 것이다.
이런 문제를 해결하기 위해 노화(aging) 기법을 사용하는데, 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 방법이다.
Round-Robin Scheduling
특별히 시분할 시스템을 위해 설계된 알고리즘이다. FCFS와 유사하지만, 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점성이 추가된다.
시간 할당량 (time quantum) 또는 시간 조각 (time slice)라고 하는 작은 단위의 시간을 정의하고, Ready Queue를 Circular Queue로 만들어서 작동한다.
스케쥴러는 하나의 프로세스를 선택해 일정 시간 이후에 인터럽트를 걸도록 타이머를 설정하고, Dispatch한다.
프로세스가 작동하다가 시간 할당량을 초과하면 현재 프로세스가 끝나지 않았음에도 다음 프로세스로 넘어가기 때문에, 선점형으로 볼 수 있다.
시간 할당량이 매우 크면 사실상 FCFS와 같아지고, 매우 적으면 과도한 Context Switching이 발생하기 때문에 오버헤드에 의한 성능 저하가 발생할 수 밖에 없다. 즉, 시간 할당량은 최소한 Context Swiching에 걸리는 시간보단 길어야 할 것이다.
Multilevel Queue Scheduling
프로세스들을 몇몇 그룹으로 분리하여 활용하기 위한 스케쥴링 알고리즘. (ex. foreground process/background process)
Ready Queue를 별도의 큐로 분류한다. 프로세스를들을 메모리 크기나 우선순위, 메모리등으로 분류하여 하나의 Ready Queue에 영구적으로 배정한다. 이때, 각각의 Ready Queue에는 서로 다른 알고리즘을 부여할 수 있다.
또한, 큐와 큐 사이의 스케쥴링도 존재해야 하는데, 일반적으로는 고정적인 우선순위의 선점형 알고리즘을 활용한다.
Multilevel Feedback Queue Scheduling
위에서 언급한 Multilevel Queue Scheduling의 경우, 프로세스가 큐를 바꾸지 않아 오버헤드가 상대적으로 적으나, 융통성이 적다.
위에서 우선순위 스케쥴링의 단점이었던 무한 봉쇄와 기아 상태가 발생할 수도 있으므로, 중간 중간에 우선순위가 다른 큐로 프로세스를 이동시킴으로써 그러한 단점을 해소할 수 있을 것이다.
설계중인 특성 시스템에 부합하도록 각각의 큐의 조건을 정의할 수 있고, 대응하기도 쉬우나 가장 좋은 스케쥴러로 동작하기 위해선 모든 매개변수들의 값을 선정해야 하므로 (큐의 수, 각각의 큐의 스케쥴링 알고리즘, 한 프로세스를 높은/낮은 우선순위를 갖고 있는 큐로 이동시키는 조건, 처음에 프로세스가 들어갈 큐를 결정할 조건...) 가장 복잡한 알고리즘이라는 단점도 있다.
스레드 스케쥴링
그런데, 결국 스레드도 스케쥴링 해야 하지 않을까? 실제 작업을 수행하는 단위는 스레드이니 말이다.
스레드는 어떻게 스케쥴링할까? 사실 스레드 스케쥴링은 라이브러리에 의해 실행되기 때문에, 위에서 이야기한 스케쥴링 알고리즘을 OS단에서 적용하지 않는다. 즉, OS는 커널 스레드만 신경 쓰면 될 문제이다.
이 경우 스레드 라이브러리는 사용자 수준 스레드를 사용 가능한 범위에서 스케쥴링 한다. 즉, 동일한 프로세스에 속한 스레드들이 CPU를 경쟁하기 때문에 스케쥴링 기법을 PCS(Process-contention score, 프로세스-경쟁 범위)라고 한다. 그러나 스케쥴링 한다고 해서 실제로 실행된다는 소리는 아니다. 왜냐하면 커널 스레드를 물리적인 CPU로 배정하기 위해 또 다른 스케쥴링을 진행해야 하기 때문이다. 커널이 어떤 커널 스레드를 스케쥴 할 지 결정하기 위해선 SCS(System-contention score, 시스템-경쟁 범위)을 사용한다.
당연히 싱글 스레드 환경이라면 SCS만 사용할 것 이다. 또한, PCS는 우선순위에 따라 행해지는 것이 일반적이나, 유저에 의해 우선순위가 조정될 수 있고 대부분의 스레드 라이브러리는 권한이 없다.
멀티코어 스케쥴링
지금까지의 스케쥴링은 CPU가 1개일때의 이야기이다. 만약에 CPU가 여러개라면? 그럴땐 부하 공유(Load Sharing)이 가능해진다. 물론 스케쥴링 문제는 저것까지 고려해야 하기 때문에 매우 복잡해진다.
크게 두가지 방법으로 나눠본다면, 하나는 비대칭 다중 처리(Asymmetirc Multiprocessing)라고 하여 하나의 처리기를 주 서버라고 부르고, 이것으로 하여금 모든 스케쥴링 결정과 I/O, 그리고 다른 시스템의 활동을 취급하게 하는 것을 말한다. 다만 주 서버에 문제가 생기면 전체 시스템에 병목현상이 발생할 수 있다.
다른 하나는 대칭 다중 처리 (Symmetric Multiprocessing, SMP)라고 하는데, 이 방식에서는 각자 독자적으로 스케쥴링 한다. 모든 프로세스는 공동의 Ready Queue에 있거나 각 프로세서 마다의 Ready Queue에 있어야 한다. 다만 이 경우엔 동시에 여러 프로세서가 공동 Ready Queue에 접근하는 일이 없도록 잘 프로그래밍 되어야 한다.
현대적인 OS는 모두 SMP를 지원한다.
멀티코어의 경우 스케쥴링이 조금 더 복잡해진다. 메모리 멈춤 (Memory Stall)이라고 하여 프로세서가 메모리를 접근할 때 데이터의 가용을 기다리면서 대기 시간이 길어지는 것인데, 이는 캐시 미스를 포함한 다양한 원인 때문에 발생한다. 그래서 이를 해결하기 위해 각 코어에 여러개의 하드웨어 스레드를 할당하고 스레드가 번갈아가면서 실행되는 방식을 도입했다.
일반적으로 프로세서를 멀티스레딩화 하는데에는 두 방법이 있다. 하나는 Stall이 발생할 때 까지 한 프로세서에서 실행되다가 긴 대기 시간이 발생하면 명령어 파이프라인을 정리하고 채우는 방식이고, 다른 하나는 명령어 주기의 경계 처럼 세밀한 부분에서 교환을 시키는 바법이다.
