Disk Scheduling
태그 :
- 개념
- 사용할 데이터가 디스크 상의 여러 곳에 저장되어 있을 경우, 데이터를 엑세스하기 위해 디스크 헤드가 움직이는 최적의 경로를 결정하는 기법
I. Disk Scheduling의 개요
가. Disk Scheduling의 정의
- 사용할 데이터가 디스크 상의 여러 곳에 저장되어 있을 경우, 데이터를 엑세스하기 위해 디스크 헤드가 움직이는 최적의 경로를 결정하는 기법
나. Disk Scheduling의 일반적인 목표
- 디스크 접근시간의 최적화: 디스크 I/O에 걸리는 시간 최적화 (암의 이동 최소화)
- Throughput의 최대화: 일정시간 내 I/O 서비스 처리 최대화
- 응답시간 최소화: 요청부터 응답까지의 시간 최소화
- 응답시간 편차 최소화: 각 요청의 응답시간과 응답시간 평균 간 편차 최소화
II. 이동디스크와 고정디스크의 자료 접근시간
가. Data Access를 위한 Disk I/O시간의 구성
Disk |
유형 |
설명 |
|
탐색시간 |
- 헤드 지정된 트랙 도달 시간 |
회전지연시간 |
- 원하는 섹터까지의 이동시간 |
|
전송시간 |
- Data를 전송 소요 시간 |
나. 이동디스크와 고정디스크의 자료 접근시간
구분 |
이동디스크 |
고정디스크 |
개념도 |
|
|
특징 |
- 각 디스크 표면마다 하나의 read-write 헤드를 가지고 있으며, access arm을 움직여 원하는 위치를 찾음 (floppy disk) |
- 각 디스크 표면의 트랙마다 지정된 read-write 헤드를 가지고 있음 (Hard disk) |
자료 접근 시간 |
- 탐색시간+회전지연시간+전송시간 (탐색시간 >> 회전지연시간 > 전송시간) |
- 회전지연시간+전송시간 (회전지연시간 > 전송시간) |
III. 이동디스크와 고정디스크에 적합한 디스크 스케줄링 알고리즘 유형 및 특성
가. 디스크 스케줄링의 유형
유형 |
설명 |
기법 |
Seek Time 최적화 |
- Disk I/O를 위한 실린더 또는 트랙 접근시간, 접근경로 최적화 - 이동디스크에 적합 |
- SSTF - SCAN 등 |
Latency 최적화 |
- 섹터까지의 이동시간, 이동경로 최적화 - 고정디스크에 적합 |
- SLTF - Sector Queuing 등 |
나. 이동디스크에 적합한 디스크 스케줄링 알고리즘 및 유형
유형 |
개념도 |
특성 |
FCFS (First Come First Served) |
(현재헤드:53 입력순서: 98,183,37,122,14,124,65,67)
|
1) 개념: 요청큐에 들어온 순서대로 처리
2) 장점: 알고리즘 단순, 구현용이, 공정한 스케줄링 기법
3) 단점: 비효율적
|
SSTF (Shortest Seek Time First) |
(현재헤드:53 입력순서: 98,183,37,122,14,124,65,67)
|
1) 개념: 현재 헤드 위치에서 가장 가까운 트랙의 요청 처리
2) 장점: Seek Time최소화, Throughput 극대화
3) 단점: 안쪽, 바깥쪽 트랙 Starvation가능성, 응답시간 편차 큼
|
SCAN |
(현재헤드:53 입력순서: 98,183,37,122,14,124,65,67)
|
1) 개념: 진행 방향 상의 가장 가까운 트랙의 요청을 먼저 서비스
2) 장점: SSTF의 기아현상을 해결, SSTF의 응답시간의 편차 줄임
3) 단점: 양쪽 끝 트랙은 가운데 위치한 트랙보다 대기시간 길어짐
|
C-SCAN (Circular) |
(현재헤드:53 입력순서: 98,183,37,122,14,124,65,67)
|
1) 개념: 항상 바깥쪽에서 안쪽으로 SCAN 수행
2) 장점: 응답시간의 편차가 매우 적음
3) 단점: 안쪽이나 바깥쪽으로 처리할 요청이 없어도 끝까지 진행
|
Look |
(현재헤드:53 입력순서: 98,183,37,122,14,124,65,67)
|
1) 개념: SCAN과 같이 처리하되 처리할 블록이 없으면 끝까지 가지않고 돌아옴
2) 장점: 불필요한 헤드이동시간 제거
3) 단점: 진행여부 결정을 위한 오버헤드
|
C-Look |
(현재헤드:181 입력순서:100,73,156,69,57,138,175,138,57,38,100)
|
1) 개념: C-SCAN과 같이 처리하되 처리할 블록이 없으면 끝까지 가지않고 돌아옴
2) 장점: 불필요한 헤드이동시간 제거
3) 단점: 진행여부 결정을 위한 오버헤드
|
다. 고정디스크에 적합한 디스크 스케줄링 알고리즘 및 유형
유형 |
특성 |
SLTF |
- Shortest Latency Time First - 회전시간 최적화 기법 - 모든 요청은 디스크 주위의 섹터 위치에 따라 대기 행렬에 정렬되고 가장 가까운 섹터가 우선적으로 서비스 - 주로 드럼과 같은 고정 헤드 장치를 스케줄링 할 때 사용 즉, 헤드의 이동이 거의 없는 경우에 사용 - 헤드가 특정 실린더로 오면 헤드를 더 이상 움직이지 않고 이 실린더에 대한 모든 요청을 서비스 |
Sector Queuing |
- 고정헤드 디스크 알고리즘 - Sector 번호에 의한 회전시간만 고려 |
Ⅳ. 디스크 스케줄링 기법 간 효율성 비교와 알고리즘 선택 시 고려사항
가. 디스크 스케줄링 기법 간 효율성 비교
구분 |
효율성 |
평균 Seek Time 효율성 |
SSTF -> SCAN -> C-SCAN -> FCFS |
Fairness 효율성 |
FCFS -> C-SCAN -> SCAN -> SSTF |
Disk Heavy Load인 경우 |
C-SCAN -> SCAN -> SSTF |
나. 디스크의 효율적 관리를 위한 디스크 스케줄링 알고리즘 선택 시 고려사항
- Disk 서비스 요구사항: Throughput, Response Time 등
- Disk 공간 할당 방법: 연속할당, 연결할당, 인덱스할당 등