지난 시간에 이어서 멀티 프로세서 스케줄링 설명.
Multiple-Processor Scheduling
- CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐.
Homogeneous processor인 경우 (모두 동일한 CPU이고 제약조건이 없는 경우)
- 큐에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐.
Load sharing
여러 CPU들이 균형있게 골고루 일하도록 하는 것이 중요.
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 매커니즘 필요
- 별개의 큐를 두는 방법과 공동 큐를 사용하는 방법 등 여러가지 있다.
Symmetric Multiprocessing(SMP)
- 각 프로세서가 각자 알아서 스케줄링 결정
- CPU들이 모두 대등한 상황. 각자 알아서 스케줄링하도록 함
- 대개 균일한 일(행렬곱 등)을 하는데 유용
Asymmetric Multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 그것을 따름.
- 대장 CPU가 데이터의 접근 공유를 관리함.
Real-Time Scheduling
주어진 시간 안에 꼭 처리가 되어야하는 상황.
- Hard real-time systems
Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야함.
데드라인을 어기지 않아야하는 상황
->offline으로 미리 스케줄링을 해두고 시스템이 따라가게 하는 경우가 많음.
offline: 프로세스들의 도착시간을 미리 알고 스케줄링해둠.
- Soft real-time computing
Soft real-time task 는 일반 프로세스에 비해 높은 priority를 갖도록 해야함.
real-time job들은 주기적인 경우가 많다.
데드라인을 어겼을 때 큰일나는 정도는 아닌. (동영상 스트리밍 같은)
Thread Scheduling
-
Local Scheduling
User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정.
운영체제는 스레드의 존재를 모르니,(유저 레벨 스레드이므로) 프로세스가 자율적으로 내부 스레드들에게 어떻게 CPU를 배분할지 스케줄링함. -
Global Scheduling
Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정.
운영체제가 스레드의 존재를 알고 CPU를 배분한다.
Algorithm Evaluation
Queueing models (이론적 계산)
- 확률 분포로 주어지는
arrival rate와service rate등을 통해 각종performance index값을 계산 arrival rate: CPU를 요청하는 작업이 큐에 도착하는 빈도.Service rate: 단위 시간 당 CPU가 처리할 수 있는 작업의 양.- 이를 통해 평균 대기 시간, 시스템 처리량 등의 성능 지표를 이론적으로 계산.
- 실 구현 없이 알고리즘 성능 예측이 가능하지만, 실제와 차이가 있을 수 있음.
Implementation(구현) & Measurement(성능 측정) (실제 구현과 측정)
- 실제 시스템에 알고리즘을 구현하여 실제 작업을 시켜보고 성능 측정값을 비교해본다.
- 스케줄링 알고리즘을 구현하는 일은 디버깅이 매우 어렵고 시간이 많이 걸린다.
Simulation (모의 실험)
- 실제 시스템의 동작을 모방하는 시뮬레이션 프로그램 작성
trace: 실제 시스템에서 추출한 데이터. 이걸로 알고리즘의 성능을 평가.- 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과를 비교
- 인위적으로 만든다면, 실제 시스템에서의 트레이스와 유사한 모델링을 거쳐 만듬(실제 시스템과의 유사성 고려)
- 시뮬레이션은 실제 구현보다 빠르고 쉬우나, 모델링의 정확성에 따라 결과의 신뢰성이 달라질 수 있음.
Process Synchronization
Race condition
- Race Condition은 여러 프로세스가 공유 데이터에 동시에 접근하여 발생하는 문제
- 공유 데이터에 대한 읽기, 수정, 쓰기 연산이 원자적으로 수행되지 않으면 발생
- 운영체제에서 Race Condition은 커널 모드에서 실행 중 인터럽트가 발생하거나, 프로세스가 시스템 콜을 수행하다 문맥 교환이 일어날 때 발생
컴퓨터 안에서 연산할 때는, 데이터를 읽어와서 연산하고 다시 데이터를 저장하게 되어있음.
메모리 -> CPU -> 메모리 , 하드디스크 -> CPU -> 하드디스크 등
무언가 데이터를 읽어들이고, 결과를 출력하는 구조.
이러한 데이터를 한 군데에서 읽어가서 연산하는게 아니라, 여러 프로세스에서 동시에 읽어가서 연산하게되면 문제가 될 수 있다.
count라는 변수를 A가 읽어가서 count++ 할 때, B 도 같이 count--를 하게된다면 ?
이론적으로는 +1 - 1 이므로 그대로여야하지만, 마이너스만 반영이 되는 경우가 발생한다.
하나의 공유 데이터를 여럿이 동시에 접근하는 이러한 상황을 Race condition이라고 한다.
여러 프로세스를 한번에 처리하게 되는 멀티 CPU의 상황이라면이런 문제가 쉽게 생길 수 있다.
CPU가 하나이더라도, 커널의 데이터는 공유되기때문에, 커널 데이터를 건들이는 과정에서 이런 데이터 컨디션 문제가 발생 가능.
OS에서 race condition 은 언제 발생하는가?
- kernel 수행 중 인터럽트 발생 시
운영체제는 인터럽트를 통해서도 커널 내 공유 데이터를 건들게 되면 데이터 컨디션 발생.
인터럽트 받는 타임을 on/off하여 인터럽트로 인해 데이터 컨디션이 발생하는 것을 방지
- Process 가 system call을 하여 kernel mode로 수행중인데 context switch가 일어나는 경우
두 프로세스의 주소 공간 상에는 공유 데이터가 없음.
하지만 시스템콜 시, 커널의 주소공간 내 데이터에 접근하게 됨. -> 해당 부분이 공유 데이터가 됨.
공유 데이터에 대한 작업 도중 CPU 제어를 빼앗기면(preempt) race condition 발생.
- 해결책 : 커널 모드에서 수행중일 때는 CPU를 preempt 하지 않음. 커널 모드에서 사용자 모드로 돌아갈 때 preempt 진행. 타이머 시간을 넘더라도, 커널모드의 작업은 다 완료시키고 CPU를 가져옴.
- Multiprocessor에서 shared memory 내의 kernel data
CPU가 여러개 있어도, 결국 운영체제가 실행될 때 문제가 된다.
공유변수를 건들이는 동안에는 인터럽트를 disable하는 방식을 썼으나, 다른 CPU가 존재하면 인터럽트를 막는 방식만으로 공유변수 접근을 막을 수 없다.
방법1) 한번에 하나의 CPU만 커널에 들어갈 수 있게 하는 방법.
문제의 원흉은 운영체제에 동시에 접근하기 때문에 발생하는 부분이었음.
-> 간단하지만 굉장히 큰 오버헤드가 발생.
방법2) 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법.
공유데이터 각각을 직접 관리하여 접근하려는 프로세스를 막는 방식. lock이 걸려 있다면 그 데이터가 unlock 될 때까지 접근하지 못함. 운영체제 코드를 여러 CPU 가 접근하게 하면서도, 오버헤드를 최소화하는 방식이 됨.
Process Synchronization 문제
-
공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킨다.
-
일관성 유지(consistency)를 위해서 협력 프로세스(cooperating process) 간의 실행 순서(orderly execution)를 정해주는 매커니즘이 필요
-
"Race condition"
여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐. -
Race condition을 막기 위해서는 공유 데이터를 동기화하는 방식이 필요.
프로세스들 간에는 주소 공간을 공유하지는 않지만 커널 상의 주소 공간을 공유하기에 이런 문제가 생겨난다.
Shared memory를 쓰게 되면, 여러 프로세스가 주소 공간을 공유하여 레이스 컨디션 생길 수 있다. 해당 방식은 코딩을 통해 공유 변수에 접근하지 못하도록 하는 방식이 필요하다.
The Critical-Section Problem
- n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
- 각 프로세스의 code segment. 에는 공유 데이터를 접근하는 코드인 critical section 이 존재.
- 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야함. -> lock / unlock 을 통해 critical section 진입을 제어하게 됨.
임계 구역 문제를 해결하기 위해서는 다음과 같은 요구사항이 필요합니다:
- 상호 배제(Mutual Exclusion): 한 프로세스가 임계 구역에 있을 때, 다른 프로세스는 임계 구역에 들어갈 수 없어야 합니다.
- 진행(Progress): 임계 구역에 들어가고자 하는 프로세스가 있다면, 언젠가는 임계 구역에 진입할 수 있어야 합니다.
