[OS] Lec 12-2. Disk Scheduling

Disk Scheduling

• Disk access 요청들의 처리 순서를 결정
• Disk system의 성능을 향상함

 

- 평가기준

• Throughput: 단위 시간당 처리량
• Mean response time: 평균 응답 시간
• Predictability: 응답 시간의 예측성, 요청이 무기한 연기(starvation) 되지 않도록 방지)

 

Disk access time (디스크가 데이터를 읽어오는 시간)

1. Seek time: 디스크 head 를 필요한 cylinder 로 이동하는 시간
2. Rotational delay: 1) 이후에서 부터 필요한 sector가 head 위치로 도착하는 시간
3. Data transmission time: 2) 이후에서 부터 해당 sector 를 읽어서 전송(or 기록) 하는 시간

 

---

Disk Scheduling 기법

• Optimizing seek time
  
  • FCFS (First Come First Service)
  • SSTF (Shortest Seek Time First)
  • Scan
  • C-Scan (Circular Scan)
  • Look
• Optimizing rotational delay
  
  • Sector queueing (SLTF, Shortest Latency Time Frist)
• SPTF (Shortest Positioning Time First)

 

Optimizing seek time

---

First Come First Service (FCFS)

• 먼저 disk access를 요구하는 요청이 도착한 순서에 따라 처리
• Disk access 부하가 적은 경우에 적합

 

- 장점

• 간단함 (Low scheduling overhead)
• 공평한 처리 기법 (무한 대기 방지)

- 단점

• 최적 성능 달성에 대해 고려가 없음

 

- Example

• 총 256 개의 cylinder 으로 구성
• Head 의 시작 위치 : 100 번 cylinder
• Access request queue는 다음과 같다.

Total seek distance = 690

1. Head는 100번에 위치함
2. 요청 1번(160) 이므로 160으로 헤드가 이동한다. (이동거리: 60)
3. 그 다음은 2번(200) 이므로 200으로 헤드가 이동한다 (이동거리:40)
4. ... 요청 8번(13) 까지 반복하면 헤드의 이동거리는 다음과 같다.

FCFS는 최적의 성능을 고려하지 않았음

이 이동거리를 기준으로 다른 알고리즘이 얼마나 잘 동작하는지 알아보자.

 

---

Shortest Seek Time First (SSTF)

• 현재 head 위치에서 가장 가까운 요청 먼저 처리
• 일괄처리 시스템에 적합

- 장점

• 이동거리가 적어지므로 단위시간당 처리량이 많아짐 (Throughput 높음)
• 평균 응답시간이 줄어든다 (응답이 빠르다)

- 단점

• 한쪽에 요청들이 몰려있으면 상대적으로 멀리 떨어진 요청이 언제 서비스를 받을지 모름 (예측이 불가능함)
• Starvation 현상 발생 가능

 

- Example

• 총 256 개의 cylinder 으로 구성
• Head 의 시작 위치 : 100 번 cylinder
• Access request queue는 다음과 같다.

Total seek distance = 300

1. Head는 100번에 위치함
2. Head는 들어온 요청들 중에서 가장 가까운 거리의 Head로 이동하게 됨
3. 3번 요청(90)으로 Head 이동 (이동거리: 10)
4. 그 다음에는 7번 요청(120) 까지의 거리가 가장 가까우므로 Head 이동 (이동거리: 30)
5. 가장 가까운 Head로 이동함..

Total seek distance는 FCFS보다 더 짧아 효율적이다.

하지만 요청5번(20)은 계속 기다려서 starvation 문제가 발생한다.

 

---

Scan Scheduling

• SSTF의 starvation 문제를 해결한 알고리즘
• 현재 head 의 진행 방향에서, head 와 가장 가까운 요청 먼저 처리
• (진행방향 기준) 마지막 cylinder 도착 후 반대 방향으로 진행

 

- 장점

• SSTF 의 starvation 문제 해결
• Throughput 및 평균 응답시간 우수 (가까운 것을 먼저 처리하므로 

- 단점

• 진행 방향 반대쪽 끝의 요청들의 응답시간 커짐 (응답이 느려짐)

 

- Example

• 총 256 개의 cylinder 으로 구성
• Head 의 시작 위치 : 100 번 cylinder
• Access request queue는 다음과 같다.

Total seek distance = 300

 

---

C-Scan Scheduling

• Scan scheduling 기법과 유사
• Head가 미리 정해진 방향으로만 이동: 마지막 cylinder 도착 후 , 시작 cylinder 로 이동 후 재시작
• (위의 Scan scheduling 기법에서 200쪽에 서비스가 더 많음에도 불구하고 왼쪽으로 진행되어 200입장에서 불공평해 보인다.)

 

- 장점

• Scan 대비 균등한 기회 제공

 

- Example

• 총 256 개의 cylinder 으로 구성
• Head 의 시작 위치 : 100 번 cylinder
• Access request queue는 다음과 같다.

Total seek distance = 490

 

---

Look Scheduling

• Elevator algorithm
• Scan (C Scan) 에서 현재 진행 방향에 요청이 없으면 방향 전환
  • 마지막 cylinder 까지 이동하지 않음
  • Scan (C Scan) 의 실제 구현 방법

 

- 장점

• Scan 의 불필요한 head 이동 제거

 

- Example

• 총 256 개의 cylinder 으로 구성
• Head 의 시작 위치 : 100 번 cylinder
• Access request queue는 다음과 같다.

Total seek distance = 260

더 효율적으로 돌아간다.

 

Optimizing Rotational Delay

---

Shortest Latency Time First (SLTF)

• Optimizing Seek Time과 다르게 디스크가 돌아가는 시간을 줄이는 것.
• Fixed head disk 시스템에 사용 (앞서 본 디스크들은 움직였다)
• 모든 실린더에 헤드가 미리 들어가 있는 것
• Head 의 이동이 없음

• Sector queuing algorithm
  
  • 각 sector 별 queue 유지
  • 같은 실린더에 속한 요청을 읽고 queue에 넣음
  • Head 아래 도착한 sector 의 queue 에 있는 요청을 먼저 처리 함

 

그림으로 표현하면 다음과 같다. 

1. 섹터들이 나누어져 있고 각 섹터마다 queue가 있다.
2. 각각 몇번 째 트랙을 읽어야 하는지 queue에 저장함.
3. 섹터가 이동하다가 head가 섹터 위에 올라오게 된다면
4. ex) S5에 head가 도착하면 Q5에 있는 요청을 처리하게 된다.

head의 이동시간을 없애고 디스크를 읽는 시간을 최소로 함으로써 필요한 데이터 access를 할 수 있다.

 

---

Shortest Positioning Time First (SPTF)

• 내가 원하는 위치에 Head를 가져다 놓음
• Positioning time = Seek time + rotational delay
• Positioning time 이 가장 작은 요청 먼저 처리

 

- 장점

• 처리량 증가(Throughput), 평균 응답시간 짧아짐

- 단점

• 가장 안쪽과 바깥쪽 cylinder의 요청에 대해 starvation 현상 발생 가능
• (한 영역에 요청이 많으면 멀리있는 요청은 서비스를 받을 확률이 낮아짐 => starvation 문제가 발생할 수 있다)

 

Eschenbach scheduling

• 위의 starvation 단점을 해결하는 스케줄링
• Positioning time 최적화 시도
• Disk가 1 회전 하는 동안 최대한 많은 요청을 처리할 수 있도록 요청을 정렬

 

- 단점

• 한 cylinder 내 track, sector 들에 대한 다수의 요청이 있는 경우, 다음 회전에 처리 됨
• = 한 요청을 처리하고 한바퀴 돌고 다음 회전에 다음 요청을 처리함
• 특정 영역에 몰려있는경우 성능저하 발생

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---