스케쥴링 목적은?
-> CPU 활용도를 올리기 위해.
계산 위주의 프로세스와 IO 위주의 프로세스를 적절히 섞는것.
스케쥴링의 종류는?
-> batch : 모았다가 한번에.
interactive : 입력이 들어올 떄마다.
real time : 시간 내에 완료해야 되는 시스템에서 씀.
ex) 10초 후에 정확히 오차없이 알려달라는 작업 등이 있을 때.
스케쥴링의 목적은?
->
모든 시스템 -
Fairness : 공평하게 CPU시간 할당
Policy enforcement : 사용자에게 CPU 시간을 더 주는 것같은 특정 목적이 우선
Balance : 모두가 적당히.
모두 적용할 수 없으면 우선 순위를 정한다.
batch 시스템 -
Throughput : CPU 활용을 높이기.
Turnaround time : 작업요청 후 응답까지 시간.
CPU utilization : Job 단위 얼마나 활용도 높았는지.
Interactive systems-
Response time : 프로세스가 실행 중에도 응답까지 걸리는 시간.
Proportionality : 뭐....어쩄든 이 두개는 중요하지 않음.
Real-time systems-
Meeting deadlines : 데드라인 지킬 수 있는지.
Batch
배치 시스템 스케쥴링 중류는?
->
• First-come first-served :
• Shortest job first : turn around time을 줄이기 위함. return 평균 시간 줄이기.
단 실행 시간이 예측 가능하다는 가정이 있어야 함.
• Shortest remaining Time next : 중간 중간 잔여 시간을 체크.
A(8초), B(4초) 작업이 있을 때 A가 2초후 B가 오면 B로 대체됨.
Interactive
->
• Round-robin scheduling
시간을 동일하게 quantum 단위로 쪼개서 프로세스에 할당.
우선 순위 부여에 문제가 있음.
• Priority scheduling
프로세스마다 우선순위를 1~4까지 부여했다면... 4가 끝나야 3이 실행되는 방법은
우선순위 1이 starvation에 빠질 수 있다.
우선순위 4를 실행 후 3 뒤에 붙이는 방법은
우선 순위 개념이 없어진다. 이것을 해결한 것이 멀티플 큐.
• Multiple queues : 책 읽어봐야 함.
• Shortest process next :
리스폰 타임을 줄이기 위한 것이지만.. 실행 시간 예측은 힘들다.
• Guaranteed scheduling :
어떤 놈에게 2배의 시간을 준다. 약속을 보장한다.
단 이건 해당 프로세스가 현제 CPU시간을 얼마나 먹었는지 등의 기록이 필요하다.
• Lottery scheduling :
게런티 방법의 보장을 근사치로 해결.
2배의 시간을 약속 한 것은 복권을 2장. 3배의 시간은 3장을 줌.(순서대로 적힌 종이)
그리고 번호를 뽑아서 해당 번호를 가진 프로세스가 실행.
-> 게런티와 로터리 방법은 공평하지 않게 의도된 것이다.
• Fair-share scheduling :
A유저는 프로세스 1개, B유저는 프로세스 5개면 B유저가 더 유리한 것이 문제
그래서 유저 간의 공평성을 고려함.
이 방법 시험에 나옴!! 영어 스펠링 안 틀리게 주의.
Real-time systems
• Hard / Soft real time
hard : 시간 내 못하면죽임.
soft : 주기 놓침을 한 두 번은 용서. 멀티미디어 원리. 영상이 갑자기 확 움직이는 현상 같은 것.
• Given m periodic events a system is "schedulable" if
ex) (이벤트 처리 시간) / (이벤트 발생 주기) 라고 하면,
0.5 / 0.1 이건 발생 주기보다 처리 시간이 길어서 안되는 작업.
0.05 / 0.1 이건 됨.
0.05/0.1 + 0.2 / 0.2 이건 합이 1보다 커서 0.2 / 0.2은 안되는 작업.
0.05/0.1 + 0.1/0.2 이건 되는 작업.
• Policy and Mechanism
메카니즘 : 스케쥴링 알고리즘
폴리시 : 메카니즘 선택 방법. 정책.
퀀텀 높이면 리스폰 타임은 줄어든다. 인자를 통해 폴리시 결정.
메카니즘과 폴리시를 구분한 것은 좀 더 유연한 시스템을 위해서 이다.
실시간 운영체제 RTOS의 기본적인 정의와 표준화 작업, RTOS와 Interface, Porting 방법과 RTOS 장점을 기술한다.
3.1 RTOS 의 정의
실시간 시스템은 원격통신, 멀티미디어, 미사일 추적, 자동화 시스템, 산업용 로봇, 항공 제어 등의 여러 분야로 확대 응용되고 있다. 이 시스템의 정확성이 논리적 정확성뿐만 아니라 결과를 마감시간(Dead Line)에 맞추는 시간적 정확성이 크게 작용하는 시스템이다. RTOS(실시간 운영체제)에서 사용하는 실시간 스케줄링은 실시간 태스크가 마감시간에 맞추어 실행될 수 있도록 태스크를 프로세서에 할당하는 역할을 하며, 이는 실시간 RTOS에 시간적 정확성 제공하는 중요한 부분이다. 실시간 스케줄링 알고리즘은 선점가능(Preemptive)하고 동적인 우선순위를 가져야 한다. 정적인 우선순위(Static priorities)방법은 프로세서의 이용률과 긴급한 비주기 태스크의 처리에 대한 보장이 안 된다는 단점이 있다. 이 두 가지를 가진 스케줄링 알고리즘으로 최소 여유시간 우선Least Laxity First 알고리즘과 Earliest Deadline First 알고리즘이 있으며, Least Laxity First 알고리즘은 멀티프로세서에서 최적화되어 최고의 프로세서 사용률을 보인다. 최소 여유시간 우선(Least Laxity First) 스케줄링 알고리즘은 여유시간이 적은 테스크가 높은 우선순위를 갖는 동적 우선순위 스케줄링 방법이다 여유시간이란 태스크가 시간 t부터 선점 당하지 않는다고 가정하고 수행을 마쳤을 때 마감시간까지의 여분시간을 말한다.
Least Laxity First 스케줄링 알고리즘은 여유시간에 의해 태스크의 수행이 결정되고, 각각의 경우는 다음과 같다. 최소 여유시간인 태스크가 수행되며, 여유시간이 0이라면 이 태스크는 선점 당하지 않고 종료될 때까지 수행되어야 마감시간을 놓치지 않는다. 음수의 여유시간을 갖는 태스크는 마감시간보다 잔여 수행시간이 더 크므로 이미 마감시간을 보장할 수 없는 태스크이므로 수행되지 않는다. Least Laxity First의 단점은 스케줄링 알고리즘은 시간이 변함에 따라 많은 Context Switch가 일어나게 된다. 어느 시점에 최소 여유시간을 갖는 태스크가 두 개 이상 존재하게 되어 여유시간 충돌이 발생하면, 이 충돌된 태스크들은 스케줄링 시점마다 번갈아 수행되게 되고 결국 하나의 태스크가 종료되기 전까지 수많은 Context Switch가 일어나게 되는 단점이 있다. 이를 보완하기 위해 일정시간에서 여유시간 역전을 허용하는 방법, Context Switch의 Overhead를 줄이기 위해 많은 Register set을 갖는 방법이 있다.
RTOS에서 지원되는 기능들은 다음과 같다.
• run time library
• multi tasking
• inter-task communication
• socket/ streams network library
• Telnet, SNMP와 같은 응용 API
'OS' 카테고리의 다른 글
| 모놀리식 커널 (0) | 2014.10.17 |
|---|---|
| 가상메모리 사용 이유 (0) | 2014.10.17 |
| 캐시메모리 적중률(Hit Rate) (0) | 2014.10.17 |
| Deadlock (0) | 2014.10.17 |
| 선점형 비선점형 알고리즘 (0) | 2014.10.17 |