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 공간 할당 방법: 연속할당, 연결할당, 인덱스할당 등

댓글