디스크 스케줄링

파일 시스템 기술을 보기 전에 기반이 되는 디스크의 상세한 동작을 이해하도록 하자. 디스크 특성에 따른 디스크 스케줄링 알고리즘에 대해서도 알아본다.

하드 디스크 드라이브

• 외부에서는 디스크의 내부 구성요소를 모른다. 디스크 드라이브는 디스크의 단위 저장 공간들을 외부 블록(logical block)으로 추상화하여 단순한 인터페이스를 제공한다. 실제로 디스크는 수많은 섹터들로 구성되어 있다. 외부 블록으로 제어하는 방식을 Logical Block Addressing(LBA)라고 한다.
• 디스크 드라이브는 작은 크기의 메모리를 가지고 있어 드라이브가 디스크에서 읽거나 쓴 데이터를 보관한다. 디스크에서 하나의 섹터를 읽을 때 드라이브가 그 트랙 위의 모든 섹터를 다 읽어서 캐시에 저장할 수도 있다.

1. 구성 요소

1) 플래터(platter)

• 플래터는 단단한 물질(알루미늄 등)로 만들어지며 드라이브의 전원이 나가더라도 비트를 드라이브에 영구적으로 저장하기 위해 얇은 자성층으로 구성되어 있다.
• 플래터들은 회전축(spindle)로 고정되어 있어, 모터를 연결하면 플래터를 일정한 속도로 회전시킨다. 회전의 속도는 분당 회전 수(RPM, Rotate Per Minute)로 측정된다.

2) 트랙(track)

• 각 표면에 동심원을 따라 배치된 섹터들 위에 데이터는 부호화된다. 이때 동심원 하나를 트랙이라고 한다. 수백 개의 트랙들이 모여야 사람들의 머리카락 두께가 될 정도로 얇다.
• 플래터는 여러 개의 동심원 형태의 트랙으로 구성되어 있으며, 이 트랙들의 집합을 실린더라고 한다.

3) 디스크 헤드(disk head)

• 표면 위를 읽거나 쓸 때는 디스크의 자기적 패턴을 감지하거나 변형을 유도하는 기계적 장치가 필요하다. 읽기와 쓰기 동작은 디스크 헤드(disk head)라는 것을 통해 할 수 있으며 표면마다 그런 헤드가 하나씩 존재한다.

4) 디스크 암(disk arm)

• 디스크 헤드는 disk arm에 연결되어 있고, 이것을 통해서 헤드가 원하는 트랙 위에 위치하도록 이동시킬 수 있다.

2. Access Time

디스크에 필요한 데이터를 읽기 위해 필요한 시간을 접근 시간(Access Time)이라고 한다. 접근 시간은 다음과 같이 구성된다.

1) 탐색 시간(seek time)

• 디스크 헤드가 데이터가 저장된 플래터의 올바른 트랙(섹터가 있는 위치)으로 이동하는 데 걸리는 시간을 말한다. 헤드를 해당 실린더로 움직이는 데 걸리는 시간, 디스크 암을 올바른 트랙 위에 위치시키는 데 걸리는 시간 모두 같은 표현이다.
• 디스크의 암이 움직이기 시작하는 가속 단계, 디스크 암이 최고 속도로 움직이는 활주 단계, 디스크 암의 속도가 줄어드는 감속 단계 이후 안정화 단계에서 트랙 위에 헤드가 정확하게 위치한다. 안정화 시간은 매우 중요하며 0.5 ~ 2 msec 정도로 오래 걸린다.

2) 회전 지연(rotation latency)

• 디스크 헤드가 올바른 섹터를 가리키기 위해 플래터가 회전하는 데 걸리는 추가 시간을 말한다.
• 탐색과 더불어 회전은 가장 비싼 디스크 동작 중 하나이다.

3) 전송 시간(transfer time)

• 실제 데이터의 전송 시간을 말한다. 1, 2에 비해 아주 짧은 시간이다.
  

많은 하드 드라이브에서 트랙 간에 섹터의 시작 위치를 약간 비틀어 설계하는 방식(트랙 비틀림, tack skew)을 사용한다. 이는 다른 트랙으로 순차적으로 접근할 때 회전 지연을 줄여 접근 시간을 최소화할 수 있기 때문이다.

3. 워크로드에 따른 I/O 시간

• 아래 수식으로 총 디스크 접근 시간을 구할 수 있다.
  $T_{I/O} = T_{seek} + T_{rotation} + T_{transfer}$
• SCSI, SATA 드라이브 명세를 가지고 랜덤 워크로드와 순차 워크로드의 성능을 구해본다. 랜덤 워크로드는 디스크에 4KB 작은 읽기 요청을 발생시키고, 순차 워크로드는 헤드 이동없이 디스크에 연속되어 있는 섹터를 읽는다고 가정한다.
  
• 평균 회전 지연은 RPM에서 직접적으로 계산할 수 있다. 15,000 RPM은 250 RPS(초당 회전수)로 나타낼 수 있고 한 번의 회전은 4 msec가 된다. 전송 시간은 데이터 크기를 최대 전송 속도로 나눈 값이다. 이를 바탕으로 각각을 계산하면 다음과 같은 결과가 나온다.
  $T_{seek} = 4ms, T_{rotation} = 2ms, T_{transfer} = 30us$
• Cheetah의 경우 6ms, Barracuda는 13.2 msec가 나온다. I/O속도를 구하기 위해 전송 데이터의 크기를 평균 속도로 나누면 0.66MB/S, 0.31MB/S가 나온다. 최대 전송량과 200배 이상 차이가 난다는 것을 알 수 있다.

I/O 비용이 크기 때문에 역사적으로 운영체제는 디스크에 요청되는 I/O 순서를 결정하는 데 중요한 역할을 담당했었다. (현대에는 디스크 특성에 맞게 디스크 컨트롤러가 디스크 스케줄링을 한다)

디스크 스케줄링

• CPU 스케줄링과 다르게 디스크 스케줄링의 경우 디스크 요청 작업이 얼마나 길지 거의 정확하게 예측할 수 있다. 요청의 탐색과 회전 지연 정도를 예상할 수 있기 때문에 디스크 스케줄러는 가장 빠른 요청을 선택할 수 있다. 즉 SJF(Shortest Job First, 최단 작업 우선)원칙을 따른다.

1. 최단 탐색 시간 우선(Shortest Seek Time First, SSTF)

• SSTF는 트랙을 기준으로 I/O 요청 큐를 정렬하여 가장 가까운 트랙의 요청이 우선 처리되도록 한다.
• 드라이브의 구조가 운영체제에 공개되어 있지 않다면 운영체제는 그저 블록들의 배열로 인식한다. 이 문제는 SSTF를 사용하는 대신 가장 가까운 블록 우선(NBF, Nearest-Block-First) 방식을 사용하면 된다.
  
• 기아(starvation)문제가 발생한다.

2. SCAN

• 트랙의 순서에 따라 디스크를 앞뒤로 가로지르며 요청을 서비스한다. (마치 엘레베이터처럼 동작한다). 디스크를 한 번 가로지르는 것을 스위프(sweep)라고 하면, 어떤 요청이 이번 스위프에 이미 지나간 트랙에 대해 들어온다면 바로 처리하지 않고 다음번 스위프에서 처리되도록 큐에 대기한다.
  

3. SCAN 변형(C-SCAN, N-SCAN, LOCK, C-LOCK)

• C-SCAN: 다른 쪽 끝에 도달했으면 요청을 처리하지 않고 곧바로 출발점으로 다시 이동한다. SCAN보다 더 균일한 대기 시간을 제공한다.
• N-SCAN: disk arm이 한 방향으로 움직이기 시작하면 그 시점 이후에 도착한 job은 되돌아올 때 서비스한다.
• LOOK: SCAN 방식과 달리 헤드가 디스크 끝까지 이동하지 않고 기다리는 요청이 없으면 헤드의 이동 방향을 즉시 반대로 이동한다.
• C-LOCK: 다른쪽 끝에 도달했으면 요청을 처리하지 않고 곧바로 출발점으로 다시 이동한다.

SCAN, SSTF 방식은 아쉽게도 디스크 회전을 고려하지 않는다. 탐색과 회전을 모두 고려해야 더 정확한 스케줄링 알고리즘이 된다.

4. 최단 위치 잡기 우선(SPTF, Shortest Positioning Time First)

헤드가 30번에 있을 때, 중간 섹터 16번으로 이동해야 할까? 아니면 바깥 섹터 8번으로 이동해야 할까?

• 답은 상황에 따라 다르다. 탐색에 걸리는 시간과 회전에 걸리는 시간이 다르기 때문이다. 만약 탐색 시간이 회전 지연보다 더 크다면 16번으로 이동하는 게 낫고, 반대라면 8번의 요청을 먼저 처리하는 것이 더 빠르다.
• 현대 드라이브들은 대부분의 요청에서 탐색과 회전이 거의 비슷하기에 SPTF가 유용하고 성능을 개선할 수 있다. 하지만 트랙의 경계가 어디인지 현재 디스크 헤드가 어디에 있는지 운영체제에서 알 수 없기 때문에 드라이브 내부에서 실행된다.

스케줄링 관련 쟁점

1. I/O 병합(I/O merging)

• 스케줄러는 병합된 요청을 반영하기 위해 해당 요청을 재배치한다. 위의 그림에서 33번 요청과 34번 요청이 있으면 병합하여 두 블록 길이의 요청으로 만든다. 디스크로 내려보내는 요청의 개수를 줄이면 오버헤드를 줄일 수 있기에 운영체제에서 병합은 특히 중요하다.

2. 작업 비보전(non-work conserving)

• 디스크로 I/O를 내려보내기 전에 시스템은 얼마나 기다려야 하는가? 작업 보전(work-conserving) 방식은 시스템이 유효 상태가 되지 않도록 하나의 I/O만 있더라도 디스크로 즉시 내린다. 하지만 예측 디스크 스케줄링 연구에 따르면 때로는 잠시 기다리는 것이 성능상 더 좋을 수 있다는 것이다. 이를 작업 비보전 방식이라고 한다.

참고 자료

• 2014 이화여대 반효경 운영체제 강의
• 운영체제, 아주 쉬운 세 가지 이야기