[Operating System] Disk Scheduling

 

 

 

일반적으로 디바이스 스케쥴링은 먼저 온 순서대로 진행하는데, 디스크는 선입선출 방식을 사용하지 않는다. 

 

 

 

 

하나의 surface에는 20~1500개의 트랙이 있고, 디스크가 3장일 때 surface는 6개이다.

cylinder는 모든 surface에서 같은 번호로 구성된 트랙의 집합을 의미한다. 

 

그림에서 노란색으로 칠해진 트랙의 일부를 sector라고 부르고, 각 sector에는 checksum을 저장한다.

가장자리 쪽의 sector는 중심쪽 sector보다 물리적 크기는 크지만, 각 sector는 같은 크기의 정보를 저장할 수 있다. (각속도 조정)

checksum은 디스크에 접근할 때 오류를 계산할 때 사용된다. 

디스크가 데이터를 읽을 때, 저장된 checksum과 읽은 데이터의 checksum을 비교해 오류가 발생했는지 감지한다.

 

sector는 디스크 제조사가 정의한 정보 저장의 최소 단위지만 운영체제는 블럭 단위로 정보를 접근한다.

따라서 블럭을 sector와 매핑하는 작업이 필요하다. (1 sector = 32 ~ 4096byte)

sector와 블럭의 크기가 다르면 한 블럭에 접근하기 위해서 연속적인 sector를 함께 읽어서 운영체제에게 전달한다.

 

헤드가 surface를 스캔하면서 sector에 저장된 데이터를 읽는다.

 

 

sector에 번호를 매길 때도 cylinder단위를 사용해 이어서 넘버링하는데, 이렇게 넘버링된 데이터들을 나열하면 왼쪽처럼 일차원 배열로 넘버링 할 수 있다.

 

운영체제는 이 블럭 번호를 사용해 디바이스에게 데이터를 읽어오라고 명령한다.

 

실제 디스크는 surface 안의 track, track 안의 sector로 구성되어있으니 블럭 번호를 통해 n번 surface의 m번 track, m번 트랙의 k번 sector를 찾을 수 있다.

 

 

 

이런 디스크 구조의 특성 때문에 블럭에 접근할 때 블럭에 저장된 sector의 위치에 따라서 접근 시간이 다르다.

 

 

 

 

Seek Time - 디스크 암을 원하는 트랙으로 옮기는데 걸리는 시간

Rotational Delay - 원하는 sector까지 도달하는데 걸리는 시간 (디스크 회전)

Data Transfer Time - 실제로 데이터를 읽는데 걸리는 시간 

 

Rotational Delay는 평균적으로 0.5바퀴이고, 0.5바퀴를 도는데 걸리는 시간은 약 4ms정도 된다.

그런데.. 4ms 정도는 Seek Time에 비하면 매우 적다. 성능을 끌어올리려면 Seek Time을 줄여야한다.

 

좋은 모터를 써서 빠르게 움직이도록 하는 것도 가능하지만, 여기서 디스크 스케쥴링을 사용하면 성능을 끌어올릴 수 있다.

 

 

 

 

가장 기본적인 알고리즘은 선입선출이다.

들어온 순서대로 55 -> 58 -> 39 -> 19 -> 90 -> 160 -> 150 -> 38 -> 184 로 처리하게 되는데.. 

 

 

 

 

성능 비교 표를 보면 알 수 있듯 Seek Length가 가장 길다. 다른 알고리즘을 생각해보자.

 

SSTF

Shortest Seek Time First의 약자로 현재 위치에서 가장 가까운 순서대로 트랙을 탐색하지만, 우선순위가 낮은 요청은 느리게 처리하게 돼 starvation 문제가 발생한다. 

 

SCAN

Elevator Algorithm, Look Policy라고도 불린다.

트랙 0번부터 시작해서 안쪽에 있는 트랙까지 읽어가면서 서비스할 요소가 있으면 바로바로 서비스하는 방식이다. 

웬만하면 이 방식을 사용한다. 

 

CSCAN은 사용하지 않는다. 

 

 

---

 

 

 

 

디스크는 느린 저장장치이고, 메모리에 캐싱해서 사용하는 경우가 많다.

메모리는 빠르지만 크기가 작으니 캐싱하는 공간을 효율적으로 사용해야 하는데, 이 때 LRU, LFU 알고리즘을 사용한다.

 

Least Recently Used - 가장 오래 전에 사용했던 요소를 먼저 삭제한다. Stack, LinkedList 방식으로 구현한다. (시간 기록 X)

Least Frequency Used - 요청할 때 마다 카운트를 갱신해 자주 이용되지 않는 요소를 먼저 삭제한다.