[운영체제] 디스크 스케줄링

디스크의 구성

• 중심에는 스핀들(spindle)이 있어 시계방향으로 돌아간다. 용량이 큰 서버용 디스크는 면이 여러개이다. 여기서 면은 플래터(platter)라고 부른다. 이러한 플래터 상에는 섹터(sector)들이 모여 하나의 원을 형성하고, 이 원을 트랙(track)이라고 한다. 트랙이 안 쪽에 있든 바깥쪽에 있든 한 트랙의 섹터 수는 동일하다. 각 플래터 상의 동일한 트랙들을 통합해 실린더(cylinder)라고 부른다.
• 디스크가 입출력을 하는 단위는 섹터이다. 디스크에 읽기와 쓰기를 실행하는 헤드가 목표하는 섹터를 찾아가기 위해 디스크 암은 해당 트랙을 찾아가주고, 스핀들은 디스크를 회전시킨다. 일반적으로 하드디스크의 한 섹터 크기는 512바이트이다.
• 헤드를 움직여 특정 트랙의 특정 섹터를 찾아가 읽기 혹은 쓰기 작업을 한다. 이러한 움직임은 물리적 움직임을 포함하고 있기 때문에 매우 효율적으로 이루어져야 한다.
• 디스크에서 읽기 혹은 쓰기의 작업을 하기 위해서는 3가지 시간 지연 요소를 고려해야 한다. (탐색시간 / 회전지연시간 / 전송시간)
• 섹터의 위치에 따라 읽기의 순서를 변경하여 처리하기도 하는데, 이렇게 디스크 입출력 순서를 정하는 작업이 디스크 스케줄링이다.

디스크 스케줄링

• 디스크 공간할당 기법을 생각해보면, 일반적으로 한 파일의 블록들에 해당하는 섹터는 디스크 상에 물리적으로 순차적이게 저장되지 않는다.
• 시분할 시스템에서 동시에 수행 중인 프로세스들에 의해 발생되는 요청이 수시로 디스크 입출력 요청 큐에 도착하기 때문에, 이를 순서화할 필요가 있다.
• 리눅스의 경우 이러한 스케줄링이 I/O 서브 시스템의 I/O 스케줄러에 의해 이루어진다.
• 요청을 순서화 시키는데 있어 가장 중요한 것은 처리율의 극대화이다. 평균 반응시간과 반응시간의 분산을 줄이는 작업이 되어야 한다. 평균 반응시간을 줄이는 것는 각 요청이 디스크 구동기에 전달되어진 순간부터 그 결과가 나올 때까지 걸리는 시간의 평균값을 최소화하는 것이고, 반응시간의 분산을 줄이는 것은 어느 곳에 위치한 섹터이든 각 섹터에 대한 반응시간에 편차를 최소화하여 반응의 예측성을 높이도록 한다는 것이다.

FCFS 스케줄링

• FCFS(Firt come first served) 스케줄링은 가장 간단한 형태의 스케줄링으로, 먼저 도착한 요청을 우선적으로 서비스하게 하는 기법이다. 실질적으로 순서를 재구성하지 않아 NOOP(NO OPeration) 스케줄러라고도 부른다.
• 특징 : 대기 큐를 재배열하지않고, 탐색 패턴을 최적화하려는 시도가 없다. 더 높은 우선순위를 가진 요청이 뒤늦게 도착해도 요청의 순서가 유지된다.
• 장점 : 요청 큐에 먼저 도착한 요청이 우선적으로 서비스를 받게되므로, 근본적인 형평성이 보장되면서 프로그래밍이 용이해진다.
• 단점 : 요청이 적은 경우엔 큰 차이가 없지만 요청이 많아지면 평균 응답 시간이 길어진다. 일반적으로 효율이 낮다.

SSTF 스케줄링

• SSTF(Shortest Seek First) 스케줄링은 트랙을 찾아가는 거리가 짧은 요청부터 먼저 서비스하는 기법이다.
• 특징 : 헤드가 어떤 요청을 처리하기 위해 먼 곳까지 이동하기 전에 현재 헤드위치에서 최소 탐색 시간을 요하는 요청을 골라 먼저 처리한다.
• 장점 : FCFS보다 처리량이 많고 평균 응답시간이 짧다.
• 단점 : 안쪽과 바깥쪽 트랙이 가운데 트랙에 비해 훨씬 서비스를 덜 받아 응답시간에 편차가 생길 수 있다. (안쪽과 바깥쪽 트랙에 기아현상까지 발생할 수 있다.)
• 결론 : 처리량이 주요 목표인 일괄 처리 시스템에 유용하고, 응답시간이 중요한 대화형 시스템에서는 부적합하다.

SCAN 및 LOCK 스케줄링

• 두 방법 모두 기본적으로 SSTF와 같이 동작한다. 하지만 헤드 진행 방향(sweep direction) 상의 가장 짧은 거리에 있는 요청을 먼저 서비스한다.
• SCAN 방법은 엘리베이터 알고리즘이라고도 불린다. 헤드가 53번 트랙에서 0번 트랙방향을 향하고 있었다면 더 가까운 65번 트랙이 있어도 방향을 유지하도록 하는 37번으로 이동한다. 그렇게 더 이상의 요청이 없어도 이동방향의 끝인 0번 트랙까지 간다. 그 후 반대 방향에 대해 서비스를 한다.
• SCAN과 LOCK의 차이는 LOCK의 경우 움직이는 방향으로 더 이상 요청이 없으면 끝까지는 가지 않고 반대 방향으로 헤드를 움직인다는 점이다.
• 두 방법 모두 SSTF와 같이 처리량과 평균 응답시간을 개선하면서도 아울러 SSTF에서 발생하는 반응시간의 편차를 많이 개선했다고 할 수 있다.
• 그러나 응답시간 편차는 여전히 존재한다. (헤드 진행 도중 도착한 요청도 함께 서비스를 받게 되므로, 밖에 위치하는 트랙은 가운데 트랙보다 더 적은 서비스를 받을 수도 있다. 각 트랙의 요청 분포가 균일하다고 해도, 헤드가 한 쪽 끝에 이르러 방향을 바꾸는 시점을 생각해보면 요청 밀도가 높은 쪽은 반대편이 되며, 현재 헤드 근처 부분은 밀도가 낮아진다. 따라서 요청 밀도가 높은 양 끝의 요청은 상당히 오랜 시간을 대기할 수밖에 없게 된다. 반면 중간 지점의 트랙은 오가며 처리되니 처리율이 높다.)
• 그럼에도 SSTF 방법에서처럼 높은 편차를 갖고 움직이는 경우는 없어지기 때문에 실제로 구현되는 대부분의 디스크 스케줄링의 기본 전략이 되었다.

C-SCAN 스케줄링

• SCAN을 조금 변형한 방법으로, Circular Elevator Algorithm으로도 알려져 있다.
• SCAN이 한 쪽 끝까지 가서 그대로 유턴하여 방향을 바꾸는 것과 다르게 항상 한쪽 끝으로 점프하여 다시 시작한다는 것이 차이점이다.
• C-SCAN 방식은 양끝과 가운데 부분의 요청밀도에 편차를 줄일 수 있어, 대기시간을 좀 더 균등하게 제공할 수 있다.
• 복귀시간이 필요하지만 처리시간이 훨씬 공평해진다.

회전지연시간 최적화

• 모든 스케줄링 방법은 트랙을 찾아가는 시간인 탐색시간(seek time)의 최적화만을 다루고 있다. 초창기엔 회전지연시간보다 헤드암을 구동하는데 걸리는 시간이 훨씬 커서 탐색시간의 최적화가 더 중요했다.
• 하지만 최근엔 회전지연시간에 대한 최적화도 중요해졌다. 특히, 한 트랙 내 여러 곳에 분산된 섹터중 일부만 요구하는 요청이 많을 경우 회전지연시간을 최적화하여 성능을 개선해야한다.
• 이러한 최적화 알고리즘에는 SLTF, SPTF, SATF 등이 있다.
• SLTF(Shortest-Latency-Time-First) 스케줄링 : 회전하는 방향 상 가까운 순서로 서비스해준다. 트랙상 서비스할 섹터들이 도열되어 있다는 의미에서 섹터큐잉(Sector Queueing)이라고도 불린다. 이론적으로 회전지연시간을 최소화한다는 측면에서 최적전략에 근접하고, 구현하기 쉽다.
• SPTF(Shortest-Positioning-Time-First) 스케줄링 : 탐색시간과 회전지연시간의 합인 '위치 결정시간(Positioning time)'이 가장 짧은 요청을 다음 서비스 대상으로 선택한다. 처리량이 많고 평균 반응시간도 짧지만, SSTF와 같이 가장 안쪽과 바깥쪽 실린더가 기아상태에 빠질 위험이 있다.
• SATF(Shortest-Access-Time-First) 스케줄링 : 위치결정시간과 전송시간의 합인 '접근 시간(Access time)'이 가장 짧은 요청을 다음 서비스 대상으로 선택한다. 3가지 시간지연요소를 모두 고려한다는 점과 SPTF보다 처리량이 많다는 장점이 있지만, 작은 크기의 요청이 연속으로 요청될 때는 큰 크기의 요청이 기아 상태에 빠질 위험이 있다.

RPM의 한계

• 디스크의 성능을 높이는 가장 직접적인 방법은 디스크의 회전속도를 물리적으로 높이는 것이다.
• 하지만 열,소음,전력소비 등의 문제로 RPM은 지난 수십년 동안 겨우 몇% 수준으로밖에 증가하지 못했다.
• 이러한 흐름에 따라 대안으로 등장한 것이 RAID이다.