Linux scheduling은 Turnaround Time 계산을 어떻게하죠?
points
[우선 제생각에는 SCHED_FIFO 방법은 P1,P2,P3순으로 들어오는 순서대로 계산을 하면 되고,
SCHED_RR도 SCHED_FIFO 방법과 같아서 P1,P2,P3순으로 들어오는 순서대로 계산을 하면되고
SCHED_OTHRER은 라운드로빈 방식으로 2시간씩 할당 받는 p1(2) p2(2) p3(2) p1(2) p2(2) p3(1)
p1(2) p2(1) P1(1) 이런식으로 계산을 하면될꺼 같은데,
SCHED_FIFO 방법은 확실히 알겠는데 SCHED_RR의 결과값이 SCHED_FIFO와 진정 같은건지
그리고 SCHED_OTHRER방법이 라운드로빈 방식으로 단순히 계산을 하면 되는건지 알고 싶습니다.
구글에서 검색을 해봐도 SRJ, RR, SRT 등의 계산 방식은 있는데 이 방법을 찾을 수 없어서 올려봅니다.
======================================================================================
프로세스들이 아래와 같이 도착한다고 가정하고 아래 두 가지 스케줄링 알고리즘에 대해 숙지한 후 질문에서 요구한 대로 CPU 스케줄링을 하는 과정을 Gantt chart를 그려 나타내고 평균대기시간(Average Waiting Time)과 평균반환시간(Average Turnaround Ttime)을 계산
프로세스/////도착 시간///////버스트 시간
P1//////////////0///////////////7
P2//////////////1///////////////5
P3//////////////2///////////////3
Linux에서는 SCHED_FIFO, SCHED_RR, SCHED_OTHER라는 세가지 유형의 스케줄링 클래스가 있다. SCHED_FIFO는 실시간 클래스이며 선점 불가능하다. SCHED_RR은 실시간 순환할당 클래스이며 선점 가능하다. SCHED_OTHER는 비실시간 순환할당 클래스이며 시분할 방식으로 스케줄링된다. SCHED_OTHER 클래스의 태스크들은 변수 priority(초기값 20)와 변수 counter에 의해 스케줄링 순서가 결정된다(두 변수의 합이 클수록 우선순위가 높다). 태스크가 생성되면 그 counter 값은 그 태스크의 priority 값으로 설정된다. 커널은 클락 인터럽트가 발생할 때마다 실행 중인 태스크의 counter 값을 1씩 감소시키다가 모든 태스크들의 counter 값이 0이면 각 태스크의 counter 값을 그 태스크의 priority 값으로 재설정한다. Linux에서는 시간 할당을 받으면 counter 값이 0이 될 때까지 실행될 수 있다. 클록 인터럽트는 매 10ms 마다 발생한다. 그러므로 1 시간 할당량은 20번의 클록 인터럽트가 발생하는 시간(200ms)이다. 할당시간이 끝날 때마다 우선순위가 가장 높은 프로세스를 스케줄 한다. Unix에서는 우선순위 값이 적은 것이 높은 우선순위를 가진다. 우선순위가 같을 때는 먼저 도착한 작업에게 우선권을 준다.
points
흠
최근 이 스케쥴링 문제를 자주 보게 되는군요.
학교 시험하고, 기사 자격시험 예상문제 하고...
우선 Linux의 특성은 배제하고 'Operating System Concepts'에 나오는 방식대로 접근하시면
될 것 같습니다.
몇 가지 스케쥴링 기법이 있는데,
1. FCFS(First Come First Served) => 선착순
2. Priority Scheduling => 우선순위 스케쥴링
'급한 불부터 끈다', '응급환자부터 처리한다' 이렇게 이해하시면 될 듯 합니다.
3. SJF(Shortest Job First) => 스케쥴링이 발생하는 시간 기준으로 버스트 시간이 가장 작업부터 스케쥴링
4. RR(Round Robin) => 돌아가면서 Time Slice만큼 사용하고 반환
이 때, 몇 가지 스케쥴링 기법은 선점형과 비선점형을 고려해 줘야 합니다.
FCFS는 가장 먼저 도착한 녀석이 실행되면 다른 녀석들이 그 자리를 빼앗지 못합니다. 비선점형입니다.
Priority Scheduling은 선점형과 비선점형 두 가지로 나뉠 수 있을 것입니다. 스케쥴링 발생시점 기준으로
가장 우선순위가 높은 녀석부터 실행한 뒤, 그것이 끝날 때 다시 그 시점에서 가장 우선순위가 높은 녀석을 실행시키는
비선점형과, 매 CPU시간마다 그 시점에서 가장 우선순위가 높은 녀석을 실행해서 기존의 녀석을 밀어낼 수 있는
선점형으로 말이죠.
SJF 역시 마찬가지입니다. 매 CPU시간마다 체크해서 그 시점에서 가장 버스트 시간이 적은 녀석을 실행시키는 선점형과
일단 실행되고 나면 다른 녀석이 그 자리를 빼앗지 못하는 비선점형으로 나뉘어 집니다.
(이 때 남은 버스트 시간이 동일한 두 녀석이 있다면 보통 FCFS로 먼저 도착한 녀석을 실행해 주지요)
RR은 Time Slice가 지나면 무조건 빼앗아 다음 녀석에게 넘겨주기를 반복하기에(기다리는 녀석이 더 이상 없으면 혼자 실행)
선점형입니다. 다음 실행할 녀석을 고를 때는 먼저 도착한 순서대로 뺑뺑이 도는 것입니다.
사전지식 정리는 이 정도로 하고, 문제 분석으로 넘어가서
SCHED_FIFO는 FCFS를 의미하고, SCHED_RR은 선점형 RR, SCHED_OTHER는 복잡한 설명을 붙여놨는데,
결국은 RR Scheduling에, 다음 녀석을 선택할 때 FCFS가 아니라 Priority로 하겠다는 것입니다.
RR은 실시간 순환할당을 사용한다고 하였고, OTHER는 비실시간 순환할당을 사용한다고 하였는데,
실시간 순환할당에서는 우선순위가 바뀌지 않아야 하므로 에이징(Aging)을 사용하지 않고, 비실시간 순환할당에서는 에이징을
사용하여 우선순위가 바뀌는 것을 말합니다.
에이징은 시간이 지남에 따라 starvation에 대처하기 위해 오래 대기한 녀석의 우선순위를 높여주는 작업입니다.
여기서는 실행 중인 태스크의 counter를 감소시킴으로써 처리하였네요.
Gantt Chart 계산하는 방법부터 각각 계산하는 것은 직접 해보시기 바랍니다.
-----------------------------------
Go to the U-City
points
이렇게 하는게 맞을까요?
|P1|P2|P3| : SCHED_FIFO
0//7//12/15
|P1|P2|P3|p1|p2|p3|p1|p2|p1| : SCHED_RR
0//2///4//6///8//10/11/13//14/15
SCHED_OTHER이 우선순위를 알아야 하는데
//SCHED_OTHER 클래스의 태스크들은 변수 priority(초기값 20)와 변수 counter에 의해 스케줄링 순서가 결정된다(두 변수의 합이 클수록 우선순위가 높다).//
이 의미를 정확히 알수 없어서 모르겠고, 에이징을 사용한다는 의미는 우선순위가 바뀐다는 것인데
에이징을 적용을 시켜야 한다면 어떤식으로 적용되는것인지 알고 싶습니다.
혹시P1 P2 P3가 초기값과변수를 각각 20으로 설정받고
10milisecond가 지나면
p1만 초기값20 변수 10으로 바뀌고 p2,p3는 초기값변수 둘다 20을 유지하여 반복적으로 하면
그다음 p2가 변수가 10으로 줄어들고 그다음은 p3의 변수가 10으로 줄어드는 방식인가요?
처음 p1부터 우선순위가 높고 그다음은 p2 ,그 다음은 p3 다시 돌아와서 p1 결국에는
순차적으로 순위가 돌아가는게 맞나요?
결국에는
|p1|p2|p3|p1|p2|p3|p1|p2|p1|
0//2//4///6///8//10/11/13/14/15