운영체제 10장-2 - Multiprocessor and Real-Time Scheduling
Real-Time system의 스케줄링의 예시
실시간으로 처리하는 시스템들을 이야기함
논리적 결과와 제한된 시간내 성과를 내는걸 요구
이벤트에 대해 즉각적으로 반응해서 실시간으로 결과를 만들어내야
Hard real time task - deadline을 지키지 않으면 치명적
soft - 치명적이진 않음
task는 주기적인것과 간헐적인 것이 있다.
real time system의 특징 5가지
determinism
responsiveness
user controll
reliability
fail-soft operation
determinism
운영체제가 어떤 인터럽트에 응답하기 위해 운영체제가 얼마나 딜레이를 가져야 하는지
제한된 시간내, 미리 알수 있는 시간내에 반응하도록 해야 한다
여러개 프로세스가 동작하는 상황에서 시스템이 deterministic하게 동작하긴 어렵다
인터럽트에 대한 처리속도와 cpu 자체가 그것을 처리하기 위한 충분한 역량을 갖고 있는지가 중요
responsiveness 반응성
우리는 반응이 즉각 일어나길 바람
interrupt service routine을 시작하는데 걸리는 시간과 그것을 처리하는데 걸리는 시간, 그리고 interrupt nesting을 어떻게 잘 처리할 것인가가 중요
user controll
일반적인 OS는 실행시키면 task scheduling을 자동으로 하게 되어 있는데
실시간 운영체제는 그것보단 좀더 fine-grained control을 할수 있는것이 필요
그래서 보통 api를 사용해서 task의 우선순위를 구분을 시켜줄수 있도록 한다
그리고 실시간성을 보장하기 위해서 페이징, 스왑핑을 할지말지
어떤 프로세스가 메인메모리에 계속 존재해야 하는지
디스크의 transfer 알고리즘을 뭘 사용해야 하는지 - 로깅을 하는 파일 시스템과 실시간으로 데이터를 주고받는 task는 서로 이런 IO를 위한 다른 transfer알고리즘이 적합할수 있다
priority band를 선택할수 있게 한다거나
reliability 신뢰성
실시간 시스템은 임베디드 되는 경우가 많기 때문에, 실제로 물리적 세계에 결과를 낳는 장치에 포함된 경우가 많다.
신뢰성이 중요, 실패시 치명적 결과
fail-soft operation
사람이 만든것이 완전할수 없기 떄문에, 시간이 지나면서 고장이 날수 있기 때문에,
fail이 생긴 경우, 높은 우선순위를 갖는 task가 실패하는게 아니고
대신 낮은 task가 실패하거나 플랜 B가 실행되는 이런 fail soft operation이 필요
real time operating system의 특징
빠른 프로세스, 스레드 스위칭 제공
작은 사이즈의 메모리 요구(임베디드)
외부의 인터럽트에 빠르게 반응
inter-process communication을 갖고 Multitasking하는 기능 제공
보통은 로그 기능이 필요(자동차 장치 기록 등...), special sequential files을 저장할수 있는 능력 제공
preemption 할수있는 스케줄링 기능을 갖고 있다, 우선순위를 갖고있다
interrupt를 disable 시키는 구간이 kernel 안에서 최소화 된다
task를 delay 시킨다던지 이런 시간을 조절할수 있는 primitives를 제공해야
타임 정보가 중요하기에, 알람과 타임아웃 제공
실시간 시스템이 빠르게 반응하면서 시간에 deterministic 하게 동작하기 위해서는 기존의 스케줄러와 다른 기능을 제공해야 한다
기능은 preemption을 의미
기존의 유닉스와 같은 round-robin preemptive scheduler의 경우에는
real time process에 대한 request가 도착했을떄, 라운드 로빈이므로 한턴을 다 돌때까지 늦춰서 실행되게 된다
priority-driven nonpreemptive scheduler의 경우에는 인터럽트를 받았을때, nonpreemptive이므로 그 프로세스가 끝날때까지 다음 프로세스를 실행 하지 못한다
preemption이 가능한 scheduler의 경우에는 critical section을 벗어날때까지만 지연하면, 그 뒤는 preemption해서 real time task를 실행시킬 수 있다.
심지어는 커널 안의 서비스도 그렇게 될수 있도록 해야 한다.
실시간 시스템이 동작하기 위해서는 실시간 스케줄링이 중요한 문제다
스케줄링 방법은 크게 두가지
하나는 스케줄이 가능한지 분석하고, 가능하다면 정적으로 또는 동적으로 스케줄을 해서 실행한다
다른 하나는 정적으로 모든 task를 알수 없을때 동적으로 스케줄을 하여 실행
이러한 실시간 스케줄링 방법을 세분화 해보면
static table-driven approaches
미리 테이블을 정해서 feasible한 스케줄 방법대로 dispatching 해서 실행
static priority-driven preemptive approaches
정적으로 실행되어야 할 task를 분석해서, 간접적으로 staitc하게 우선순위를 주고 preemptive하게 스케줄링 되도록 하는 방법
우선순위를 주었을때 리소스가 있다면 충분히 실행될수 있을때 사용하는 방법
dynamic planning-based approaches
offline으로 모든 task의 실행되는것을 알수 없을때
실행시간에 feasiblity를 결정해서 실행하도록 하는 방법
실시간에 실행될수 없다고 판단되면, 덜 중요한 task를 중단 시키고 나머지로 실행을 완료하도록 한다
dynamic best effort approaches
feasiblility test 없이 실행하도록 한다
일반적인 보통의 운영체제를 사용하는 방법, deadline을 지킬수 없다면 abort 시킬수 있다.
실시간 운영체제의 스케줄링은 다른 이름으로 deadline scheduling이라고 함
현실적으로 좋은 방법은 임베디드 시스템 특성상 생성될수 있는 task의 종류나 개수가 정해져 있고, 그것을 충분히 수용할수 있는 cpu의 용량을 확보하는것
스케줄링 하는데 필요한 정보들
Fixed-priority scheduling A, B 각각 우선순위 갖는 경우 - 데드라인을 놓치는 경우가 발생한다
Earliest deadline first scheduling 알고리즘을 사용시 데드라인을 놓치지 않게 된다
똑같은 자원이라도 어떻게 스케줄링 하느냐에 따라 데드라인을 놓치거나 놓치지 않는 결과를 낳는다
주기적이지 않은 task와 starting deadline을 갖는 경우
nonpreemptive라면 - 시작 데드라인을 놓치게 된다 (2번째)
비주기적인 task지만 언제 시작하고 언제 데드라인인지 미리 알수 있다면
A가 도착함에도 불구하고 A를 시작하지 않는 방법을 사용해서 데드라인을 놓치지 않을수 있다. (3번째)
FCFS - 도착 순서로 실행되므로 B가 데드라인을 놓치고, 뒤에서 E도 데드라인을 놓친다. (4번째)
실시간 스케줄링은 근본적으로 충분한 cpu자원을 사용하고 우선순위를 줌으로서 스케줄링이 가능하다.
Rate Monotonic Scheduling - 주기적이고 빈번한 task를 높은 우선순위, 덜 빈번한 task를 낮은 우선순위, cpu용량의 0.693정도만 이러한 task로 채운다면 실시간을 언제나 보장할수 있다
이때 리소스의 공유는 없어야 한다, 독립적으로 돌아가는 경우에만 성립
최대성능이 그렇게 된다는걸 증명하는 과정은
주기적인 task를 전체 cpu 할당량에 채우다보면, 전체의 약 70%에 해당되는 용량만 사용한다면 실시간을 보장할수 있다
우선순위 역전
priority-based preemptive scheduling을 사용하는 경우 자원을 공유하는 경우에 문제가 발생한다
패스파인더 로봇을 화성에 발사했을때 발생한 문제
높은 우선순위 task가 낮은 우선순위 task를 기다리는 경우가 발생한다
priority inversion 문제
패스파인더에는 T1,T2,T3 task가 돌고 있었다
T3가 먼저 시작, 자원 상태를 점검하기 위해 S라는 세마포어를 잡음,
그상태에서 T1이 동작되면, T3는 S를 잡은 상태에서 블럭된다
T1이 실행되는데, T1은 자원 S를 확인하려고 세마포어를 잡는 시도를 함
그런데 이미 락이 잡혀있기 때문에 낮은 우선순위를 가진 T3을 기다리게 된다
cpu자원이 여유가 있기 때문에 T3가 다시 실행되고
실행되다가 T2가 실행되면 그동안 중단된다
T2가 IO를 하는 동안 다시 T3가 실행되는데 t7시점이 되어야지 unlock을 하고, T1이 lock을 잡을수 있었다
만약 T2가 작업이 길어지면
T3은 실행이 못되고, unlock은 늦춰진다
그래서 T1이 락을 잡지 못해서, 시스템을 체크하는 task가 실패를 해서 timeout되어 전체를 reset하는것이 반복된다.
낮은 우선순위를 갖는 T2를 T1의 task가 기다리는 상황이 발생한것이다
이것을 해결하기 위해 priority inheritance가 고안됨
아까와 똑같은 상황에서
높은 우선순위를 갖는 Task가 똑같은 자원을 요구한다면 (T1이 T3이 잡은걸 요구)
이 Task는 낮은 우선순위가 아닌 높은 우선순위를 상속받아서 (T1의 우선순위를 상속받아서)
실행하도록, 그래서 빨리 자원을 놓을수 있도록 만드는 방법이다
이 priority inheritance는 실시간 운영체제에서 api로 제공되고 있다
리눅스 스케줄링
task를 3가지 클래스로 분류하고 스케줄링
리눅스의 스케줄링을 위해 사용하는 자료구조
우선순위 큐가 많이 있기 때문에 그 큐를 다 검색해서 10ms안에 새로운 프로세스를 선택해서 실행해야 한다
각 큐가 task를 담고있는지 여부를 나타내는 bit map이 있고
그 bit map 들은 각각 active인 경우 각각 큐를 담게 된다, 그 큐에는 ready 상태의 task들이 들어가 있는것
expired queue에는 직전에 cpu time을 모두 쓴 task들을 담고 있다
유닉스 SVR5에서
리눅스와 유사, 실시간 프로세스에 가장 높은 우선순위
그다음은 커널모드, 가장 낮은게 유저모드
우선순위를 높은것과 낮은것 분리해서 각각을 큐를 만들고
그 큐를 위에서 아래로 스캔하면서 들어간 task를 선택
이 real time task는 kernel과 time shared이전에 실행이 되고
만약 idle 상태에서 뒤에것이 실행된다면, preemption을 사용해서 실행되도록 구현되어 있다
두가지 종류의 thread migration을 제공, 이것을 사용해서 프로세서간의 로드 밸런싱을 한다
pull 매커니즘
자발적으로 idle 프로세서가 nonidle 프로세서에 있는 스레드를 가져오는것, 성능의 증가
push 매커니즘
스케줄러가 주기적으로 동작해서 부하를 측정하고, 부하가 많으면 밀어냄
윈도우즈 스케줄링
두가지 밴드의 클래스를 갖는다
real time priority class - 고정 우선순위를 갖는 task를 동작시켜서 task를 스케줄링, 라운드로빈 큐
variable priority class - 초기 우선순위로 실행하면서, 우선순위가 계속 바뀜
0 댓글