CPU 스케줄링이 필요한 이유가 무엇일까?
CPU 스케줄링은 컴퓨터 시스템에 있는 job들이 homogeneous하지 않고 I/O bound job가 CPU bound job이 섞여 heterogeneous하기 때문이다.
CPU Scheduling에서 고민해야 할 사항은 다음과 같다.
CPU Scheduling에서 무엇을 고민해야 할까?
- Process에게 어떤 우선순위를 줘야하는지
- Starvation을 어떻게 해결해야 할지
Multilevel Queue
multilevel queue는 ready queue에 한 줄 서기를 하는 게 아니라 여러 줄로 줄을 기다리는 큐를 말한다. 즉, Ready Queue를 여러 개로 분할한 것이다.
위는 Multilevel queue에 여러 줄로 줄을 서 있는 모습으로, 위에 있는 process가 우선순위가 높은 job에 해당한다. 우선순위가 높은 job이 기다리고 있으면 그 job부터 처리하는 차별적인 방법이다.
위의 그림에서 batch process 의 경우 CPU를 오래 사용하는 CPU bound job이며 interactive process 와 같은 I/O bound job보다 하단에 위치한 것을 볼 수 있다.
Foreground queue
interactive job을 집어넣는다. 각 줄마다 독립적인 스케줄링 방식이 필요한데, foreground queue의 경우는 사람과 interaction이 필요한 작업이기 때문에 round robin이 적합하다.
Background queue
사람과 interaction이 없는 batch 작업을 집어 넣는다.
background에 있는 job들은 어차피 CPU만 오래 쓰는 작업들이며, 응답 시간이 빠를 필요가 없기 때문에 context switch overhead를 줄이기 위해 먼저 온대로 처리하는 FCFS가 적합하다.
큐에 대한 스케줄링
각 줄에서 큐에 대한 스케줄링이 필요하다. 스케줄링이 두가지로 이루어지는데, 먼저 어느 큐에게 CPU를 줄지 결정해야 하고, 그 다음에는 그 줄에서 어떤 프로세스에게 CPU를 줄지 결정해야 한다.
큐에 대한 스케줄링(어느 큐에 CPU를 줄지) 방식은 다음과 같다.
Fixed priority scheduling
우선순위가 높은 큐가 다 비어있을 때만 낮은 큐에 있는 프로세스들에게 CPU가 간다. 이는 우선순위를 매우 강하게 적용하는 방식이며, 우선순위가 낮은 줄은 영원히 CPU를 얻지 못할 가능성이 있기 때문에 starvation이 발생할 수 있다는 문제점이 있다.
Time slice
위의 방법에서 일어나는 starvation을 막기 위한 방법이다. 각 줄 별로 CPU 시간을 적절한 비율로 나눠서 할당하는 것이다. 예를 들어, 80%는 우선순위가 높은 줄에게 CPU시간을 주고, 20%는 우선순위가 낮은 줄에게 주는 방식이다.
Multilevel Feedback Queue
여러 줄로 줄 서기를 하면서 프로세스가 경우에 따라 줄을 왔다갔다하면서 우선순위가 높아졌다 낮아졌다 할 수 있다.
큐를 몇개 둘 것인가, 각 큐에서는 어떤 scheduling algorithm을 쓰느냐, 프로세스를 상위/하위 큐로 보내는 기준, 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 정하는 기준(처음 큐로 들어갈 때 어디로 들어갈 것인가)을 정하는 것이 해당 방식의 이슈이다.
처음 들어오는 프로세스는 우선순위가 가장 높은 큐에 집어넣는다. 우선순위가 가장 높은 큐는 Round Robin의 할당 시간을 짧게 준다. 밑으로 갈 수록 Round Robin의 할당시간을 길게 주고, 제일 아래는 FCFS를 사용한다. 현재 큐에서 할당 시간 내에 수행이 안 된 경우 다음 큐로 넘어가게 되고, 위의 큐가 빌 때까지 기다린다.
먼저 도착한 프로세스는 얼마 기다리지 않고 CPU를 사용한다. 이 방식은 CPU 사용 시간이 짧은 프로세스에게 우선순위를 많이 주는 스케줄링 방식이다. 왜냐하면 해당 방법으로 구현 시, CPU 사용 시간이 긴 프로세스의 경우 할당 시간 내에 작업을 끝내지 못해 다음 큐로 이동하게 되고 그렇게 더 많이 기다리게 되기 때문이다.
따라서 CPU 사용시간을 미리 예측할 필요가 없으며(처음에 들어올 때 누구든지 짧은 시간을 주기 때문!) 짧은 프로세스가 우대를 받는 스케줄링 방법이다.
지금까지 말한 CPU Scheduling은 CPU가 하나뿐인 상황이었으며, 지금부턴
1. CPU가 여러 개이거나
2. 시간에 대한 deadline 제약 조건이 있거나
3. 스레드가 여러 개 있는
등의 특이 케이스에 대한 CPU 스케줄링을 알아보자.
Multiple-Processor Scheduling
CPU(프로세서)가 여러 개인 상황에서의 스케줄링에 대해 알아보자.
Homogeneous processor인 경우
큐에 한 줄로 줄을 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
그런데, 어떤 job은 특정한 CPU가 꼭 실행해야 하는 제약조건이 있을 수 있다. 이 경우에는 이를 먼저 할당해두고 스케줄링을 하게 된다.
Load Sharing
CPU가 여러 개인 경우 load sharing이 잘 되는 것이 중요하다. 특정 CPU만 일하고 나머지 CPU는 놀고 있으면 안 되므로(전체적으로 일을 해야 전체적인 성능이 좋아진다), 부하를 적절히 공유하는 메커니즘이 필요하다.
별개의 큐를 두는 방법과 공동 큐를 사용하는 방법이 있는데, 별개의 큐를 두는 경우에는 CPU 마다 별도의 줄을 서게 한다.
Symmetric Multiprocessing(SMP)
모든 CPU를 대등하며, 각 CPU가 알아서 스케줄링한다.
Asymmetric Multiprocessing
하나의 CPU가 시스템 데이터의 접근과 공유와 같은 전체적인 컨트롤을 담당하고 나머지 CPU는 그것에 따르는 것이다.
Real-Time Scheduling
Real-Time job은 정해진 시간 안에 수행이 되어야 하는 job이다. CPU 스케줄링을 할 때도 데드라인을 보장하는 것이 중요하다. 보통은 Real-Time job이 먼저 주어져 있고 이들을 미리 스케줄링하여 적재적소에 배치가 되도록 한다. 보통 오프라인으로 미리 스케줄링을 해두거나, 주기적으로 업데이트가 되어야 하는 제약조건이 있는 경우엔 이에 맞게 해준다.
Hard real-time systems
정해진 시간 안에 반드시! 끝내도록 스케줄링해야 한다.
Soft real-time computing
데드라인은 존재하지만 정해진 시간 안에 반드시 끝낼 필요는 없는 것으로, 예를 들어 영화와 같은 것들이 있다. Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 스케줄링한다.
Thread Scheduling
스레드를 구현하는 방식은 User Level Thread, Kernel Level Thread가 있다.
User Level Thread의 경우, 사용자 프로세스가 직접 스레드를 관리하여 운영체제는 그 스레드의 존재를 모른다.
반면 Kernel Level Thread의 경우, 운영체제가 그 스레드의 존재를 알고 있다.
이렇게 상황이 다르기 때문에 Thread를 구현하는 방식에 따라 스케줄링하는 방법도 다르다.
Local Scheduling
User Level Thread의 경우, 운영체제는 그 스레드를 모르기 때문에 운영체제 입장에서는 그냥 그 프로세스에게 CPU를 줄지 주지 않을지를 결정하는 것과 같다. 프로세스 내부에서 어떤 스레드에게 CPU를 줄지는 운영체제가 아니라 프로세스 내부에서 결정하는 것이다. 따라서 Local Scheduling은 사용자 프로세스가 직접 사용자 수준의 thread library에 의해 어떤 thread에게 CPU를 줄지 결정한다.
Global Scheduling
Kernel Level Thread의 경우 운영체제가 그 스레드를 알고 있기 때문에 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정한다.
Algorithm Evaluation
어떤 알고리즘이 좋은지 평가할 수 있는 방법들을 크게 3가지로 나누어 볼 수 있다.
Queueing models
이는 굉장히 이론적인 방법으로, 이론가들이 주로 사용하는 방법이다. 확률분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산한다. 최근에는 시스템에서 직접 돌려보는 값들을 더 의미있게 보지만 이론적으로는 여전히 많이 사용한다.
Implementation(구현) & Measurement(성능 측정)
실제 시스템에 알고리즘을 구현하고 실제로 돌려보는 실제 작업(workload)에 대해 성능을 측정하여 어디가 더 빨리 끝나는지, 어떤 것이 더 좋은지를 비교한다.
Simulation(모의 실험)
실제로 돌리는 것이 아니라 모의실험을 하는 방식이다. 좀 더 쉽게 측정을 할 수 있다. 사용 시간을 손으로 계산하는 게 아니라 이를 계산해주는 프로그램을 짜는 것이 시뮬레이션 방식이다.
알고리즘을 모의 프로그램으로 작성 후 trace(실제 프로그램을 통해 추출한 Input data. 임의로 만들 수도 있고 실제 프로그램을 돌려 뽑을 수 있다. 실제 프로그램을 돌려 뽑는 경우 실제 상황을 더 잘 반영한다.)를 입력으로 하여 결과를 비교한다.
[6장] Process Synchronization
컴퓨터 시스템 내에서 데이터가 접근되는 패턴을 알아보자. 컴퓨터 시스템 내에 어떤 위치에 있든 데이터를 접근하는 것은 다음과 같은 경로를 따르게 된다.
데이터가 저장된 위치에서 저장된 데이터를 읽어와 연산한 후 연산 결과를 다시 원래 위치에 반영한다. 이런 방식을 사용하여 Process Synchronization 문제가 발생할 수 있다. 왜냐하면 데이터를 누가 먼저 읽어 갔느냐에 따라 결과가 달라질 수 있기 때문이다.
Race Condition
S-box를 공유하는 E-box가 여러 개인 경우, Race Condition의 가능성이 있다.
예를 들어, 그림과 같은 상황에서 왼쪽의 E-box가 먼저 count를 읽어가고 오른쪽 E-box가 count++연산이 S-box에 반영되기 전에 데이터를 읽어간다면 결과적으로 count--연산만 반영되게 된다.
이렇게 하나의 데이터에 여러 개의 주체가 동시에 접근하려 한다면 이를 Race Condition이라 한다. 이런 경쟁 상태에서 어떤 하나의 주체가 읽어갔는데 그 동안에 또다른 주체가 데이터를 읽어가면 우리가 원하지 않는 결과를 얻을 수 있다. 따라서 이런 문제를 조율해주는 방법이 필요하다.
multiprocessor system에서 메모리를 공유하고 있다면 이런 문제가 발생할 수 있다. 프로세스는 원칙적으로는 자기 자신의 주소공간만을 접근할 수 있지만 공유메모리를 사용하는 경우에 이런 문제가 생길 수 있다.
더 중요한 문제는 운영체제 커널과 관련된 문제들이다. 프로세스들이 본인이 직접 실행할 수 없어 운영체제에게 직접 요청하기 위해 System call을 하는 경우 커널의 코드가 그 프로세스를 대신하여 실행해주는데 이 경우 커널의 코드를 실행시키는 것이기 때문에 커널의 데이터에 접근하게 된다. 이런 상황에서 CPU를 도중에 빼앗겨 또다른 프로세스에게 CPU가 넘어간 상황을 가정해보자. 이 때 이 프로세스가 또 System Call을 하게 되면 이런 Race Condition 문제가 발생할 수 있다.
또한 커널의 코드를 실행 중인데 도중에 Interrupt가 들어올 수 있다. interrupt가 들어오면 지금 하는 일은 잠시 잊고 interrupt를 처리하는 커널 코드를 실행하여 커널의 데이터를 처리한다. 이런 상황에서 운영체제 커널 안의 데이ㅓ는 여러 프로세스들이 동시에 사용할 수 있는 공유데이터이기 때문에 문제가 발생할 수 있다.
OS에서 race condtion이 발생하는 경우
동시에 접근해서 문제가 생기는 경우를 크게 세가지로 설명할 수 있다.
Kernel 수행 중 인터럽트 발생 시
이런 문제를 해결하기 위해 중요한 변수값을 건드리는 동안에는 인터럽트가 들어와도 인터럽트 처리 루틴으로 넘기는 게 아니라 실행 중이었던 작업이 끝난 다음(store시킨 다음)에 인터럽트 처리 루틴으로 넘겨 Race Condition을 방지한다.
Process가 System call을 하여 Kernel mode로 수행 중인데 context switch가 일어나는 경우
위의 그림에서 Pa는 자신이 계산하고 있던 값을 계산 완료하고 저장시키기 때문에 Pb에서 일어난 count++는 반영되지 않는다.
이런 문제는 프로세스가 커널 모드에 있을 때는 할당시간이 끝나도 CPU를 빼앗기지 않도록 하여 해결한다. 작업이 진행 중인데 진행 도중 CPU를 뺏는 것이 아니라, 커널모드가 끝나고 유저모드로 빠져나올 때 빼앗는다. (preempt) 이렇게 하면 할당 시간이 정확하게 지켜지진 않지만 time sharing system의 경우 real time system이 아니기 때문에 조금 더 할당 받았다 해서 시스템에 큰 지장을 주지 않는다.
Multiprocessor에서 shared memory 내의 kernel data
이 상황에선 앞에서 설명한 방법들로 해결되지 않는다. 즉, interrupt를 단순히 막는 것만으로는 해결할 수 없다. 근본적으로 작업주체가 여럿이기 때문에 생기는 문제이기 때문이다.
CPU가 여러 개 있는 환경에서는 race condition을 어떻게 막을 수 있을까?
Lock을 사용해 해결한다. 데이터를 Load하기 전에 데이터에 lock을 걸어 다른 어느 누구도 해당 데이터에 접근할 수 없도록 하고 저장이 끝나면 unlock하여 다른 CPU가 접근할 수 있도록 한다.
또 다른 해결법은 다음과 같다. 결국 이런 문제가 생기는 이유는 운영체제 커널을 여러 CPU가 동시에 접근하기 때문에 생기는 문제이다. 따라서 한번에 하나의 CPU만이 커널에 접근할 수 있도록 한다면 이런 문제를 해결할 수 있다. 즉, 커널 전체를 하나의 lock으로 막고, 커널을 빠져나올 때 unlock하는 것이다. 이 방법은 비효율적이기 때문에 위에서 설명한 데이터에 lock/unlock하는 방법이 권장된다.
Process Synchronization 문제
Process Synchronization문제는 여럿이서 동시에 접근하려 하여 시간적으로 맞아 떨어지지 않아서 생기는 문제이다. 공유데이터에 동시에 접근하려는 상황에서 데이터의 불일치 문제가 발생할 수 있다. 일관성을 유지하기 위해 협력 프로세스(공유데이터를 접근하는 프로세스)들 간의 실행 순서를 정해주는 메커니즘이 필요하다. 즉 한 프로세스가 읽어가서 수정하는 동안에는 다른 프로세스가 접근하지 못하도록 막는 방법이 필요한 것이다.
여러 프로세스들이 공유데이터를 동시에 접근하려는 상황을 race condition이라 한다. 이를 막기 위해서는 동시에 접근하련느 process 간에 동기화(synchronize)가 잘 되어야 한다.
보통 프로세스들은 자신만의 독자적인 주소 공간을 갖기 때문에 사용자 프로세스를 수행 중 timer interrupt가 발생하여 context switch가 발생한다해서 무조건 race condition이 발생하는 것이 아니다. 공유데이터를 사용하거나 커널에 있는 데이터를 건드리는 동안에 CPU가 넘어가는 상황과 같을 때 문제가 발생한다.
Critical-Section Problem
Critical-Section
critical-section이란 공유 데이털르 접근하는 코드이다.
한 프로세스가 critical section을 수행 중이면, 다른 프로세스에게 CPU가 넘어가더라도 공유데이터에 접근하는 critical section을 수행할 수 없어야 한다.
이를 해결하기 위한 알고리즘은 다음시간에!
