[운영체제] 디스크 스케쥴링(Disk Scheduling)

1. 디스크 스케줄링

디스크 접근 시간

디스크 접근 시간은 Seek Time + Rotational Delay + Transfer Time 이다.

이 중 다음 실린더를 탐색하는 시간인 Seek Time이 가장 오래걸린다.

 

 

다중 프로그래밍 환경

다중 프로그래밍 환경에서 디스크 큐(disk queue)에는 많은 요청(request)들이 쌓여있다. 프로세스들이 계속해서 디스크에 읽기, 쓰기 요청을 하기 때문이다.  어떻게 요청들을 처리하면 탐색시간을 줄일 수 있을까?

 

 

2. 디스크 스케줄링 알고리즘

디스크 스케줄링 알고리즘은 사용할 데이터가 디스크 여러 곳에 저장되어 있는 경우 데이터를 액세스하기 위해 디스크 헤드가 움직이는 경로를 결정하는 기법이다.

 

디스크 스케줄링의 목적은 처리량 최대화, 평균 응답시간 최소화, 응답 시간 편차의 최소화이다.

 

1) First Come First Served (FCFS)

FCFS는 가장 간단한 방법이다. 이름에서 알 수 있듯이, 디스크 큐에 가장 먼저 들어온 트랙에 대한 요청을 먼저 서비스하는 방법이다.

우선순위 높은 요청이 입력되어 순서과 바뀌지 않아 공평성이 보장된다. 

예시)

200 cylinder disk, 0 ... 199

디스크 큐 : 98 183 37 122 14 124 65 67

현재 헤드 위치 : 53

FCFS 헤드 움직임

전체 헤드 움직임 : 640 실린더

헤드 움직임이 매우 비효율적이다.  

 

 

2) Shortest Seek Time First (SSTF)

SSTF는 헤더를 가능한 적게 움직일 수 있는 곳을 먼저 탐색하는 방법이다.

 

 

예시)

200 cylinder disk, 0 ... 199

디스크 큐 : 98 183 37 122 14 124 65 67

현재 헤드 위치 : 53

SSTF 헤드 움직임

총 헤드 움직임 : 236

예제에서는 SSTF 방식이 FCFS 방식보다 효율적이었다.

그러나 SSTF 방식에도 2가지 문제점이 있다. 

가까운 요청만 우선 처리하게되면 계속 밀리는 요청이 발생할 수 있는데, 이로 인한 기아현상이 발생할 수 있다는 점이고,

최적의 방법이 아니다는 점이다. 

 

3) SCAN Scheduling (= Elevator Algorithm)

스캔 알고리즘은 디스크의 요청을 계속해서  디스크를 가로질러 앞뒤로 스캔하는 방법이다. 한쪽의 양 끝 방향으로 갔다가, 반대 끝 방향으로 갔다가.. 반복하는 방법이다.(full swing)

 

예시)

200 cylinder disk, 0 ... 199

디스크 큐 : 98 183 37 122 14 124 65 67

현재 헤드 위치 : 53

SCAN 헤드 움직임

총 헤드 움직임 : 236 실린더 = 53(시작 위치)+183(맨 끝 위치)

 

프로세스가 많다면, 요청은 골고루 분포되어있을 것이다. (라고 가정한다.)

 

SCAN 방식의 문제점은

끝 점(0 혹은 199)에 도착 후, 반대방향으로 갈 때, 시작점(53)까지는 처리해야하는 요청이 없다는 점, 

요청이 없어도 양 끝 점(0, 199)까지 갔다가 반대 방향으로 간다는 점에서 비효율 적이다.

이를 해결항 방법이 각각 C-SCAN, LOOK 스케줄링이고, 두 한계점을 보완항 방식이 C-LOOK 스케줄링이다.

 

 

3) SCAN Scheduling 변종

(1) C-SCAN

C-SCAN 헤드 움직임

C-SCAN 방식에서 끝에 도착 후(0혹은 199), 반대방향으로 갈 때, 시작점(53)까지는 처리해야하는 요청이 없다. C-SCAN은 이 부분을 개선해끝 점을 찍으면, 반대 끝 지점으로 넘어가 한 방향으로 탐색하는 방식을 말한다. (C는 Circurlar의 약자이다)

총 움직인 거리는 걸지만 시간은 SCAN보다 빠르다.

 

(2) LOOK

LOOK 헤드 움직임

SCAN 방식에서는 요청이 없어도 양 끝 점(0, 199)까지 갔다가 반대 방향으로 간다. LOOK은 이 방법을 개선했는데 끝 점 까지 않고, 해당 방향의 마지막 점에서 방향을 바꾸는 방식이다.

 

 

(3) C-LOOK

C-LOOK 헤드 움직임

C-LOOK 방식은 양 끝 점(0 혹은 199) 까지 않고, 방향의 맨 끝 요청까지 갔다가 반대쪽 맨 끝 요청으로 가는 방식이다.