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

개요

오늘은 디스크 스케줄링에 대해서 알아보도록 하겠습니다.

요즘 컴퓨터에서 사용하는 저장장치의 종류는 정말 다양해졌습니다.

과거에는 플로피 디스크라고 해서 오늘날의 ‘저장’ 버튼에 해당하는 저장장치부터 시작해서

하드 디스크, 그리고 SSD까지 시간이 지날수록 저장소의 저장 속도는 빨라졌고, 용량은 많아졌습니다.

 

이러한 눈부신 저장장치의 하드웨어적 발전 속에서,디스크 스케줄링은 다소 생소한 개념이 된 것 같습니다.

 

디스크 스케줄링은 컴퓨터 디스크에서 정보를 빠르고 효율적으로 입출력하기 위해 고안된 스케줄링 전략입니다.

 

지금까지 운영체제는 주로 CPU와 같이 비교적 비싼 자원에 대해서 어떻게 관리하고 있는지 소개했는데요.

 

오늘은 운영체제가 플로피 디스크부터 하드 디스크, SSD까지 외부 저장 장치를

어떻게 효율적으로 사용하는지에 대한 전략에 대해 알아보도록 하겠습니다.

---

 데이터가 기록되는 원리

플로피 디스크부터 하드 디스크까지 전통적으로

외부 저장 장치에 데이터 입출력을 담당하는 ‘헤드(head)’라는  구조물과

데이터가 실제로 저장되어 필요시 읽거나 쓰이는 물리적인 저장소, ‘트랙(track)’으로 구성되어 있는데요.

 

 

 

 

여기서 트랙 내의 저장될 정보는 블록(block)이라는 단위를 이루게 되고

이러한 블록이 하드웨어적으로 고정된 크기를 가질 때 우리는 이것을 섹터(sector)라고 부릅니다.

 

또한, 이러한 트랙 내에 정보는 기록되는 정보의 사이즈

즉 레코드 갭(record gap)에 의하여 분리된 가변 블록들로 구성되기도 합니다.

 

이동 헤드 디스크에서 이러한 블록의 크기는 설계상의 목적으로 고정된 크기의 블록을 가질 수도 있고,

가변적인 크기를 가질 수 도 있겠으나 소프트웨어적으로는 가변적일 지라도 고정된 크기의 블록을 이용하게 됩니다.

 

어느 경우에서나 기록된 정보는 ‘블록(block)’단위로 입력 및 출력이 되고,

레코드들의 블럭화 및 비블럭화는 물리적인 블록 크기가 고정인지 또는 가변적인지 쉽게 숨길 수 있도록 해줍니다. 

 

데이터는 일련의 자기 디스크(둥근 판)에 기록되는데,

이 판의 회전 속도는 매우 빨라서 어떤 축은 1분에 3600회 회전을 하기도 합니다.

데이터는 일련의 판독과 기록의 작업을 위한 헤드 즉, read-write 헤드(이하 헤드)에 의해 읽거나 쓰는 작업을 수행합니다.

 

이러한 헤드는 디스크 한 면당 하나씩 존재하며, 각각의 헤드는 자신에 인접한 데이터만을 접근할 수 있습니다.

 

그렇기에, 어떤 위치에 있는 데이터를 읽으려면 디스크에서 데이터가 있는 위치로 이동하도록 디스크를 회전해야하고,

이는 곧 하드 디스크가 데이터를 읽기 속도가 SSD에 비해 느린 이유입니다.

 

왜냐하면, 아무리 빠르게 회전해도 결국 전자기적으로 잘 설계된 SSD 만큼 빠른 속도를 낼 수는 없기 때문이죠.

 

 

 

그리고, 하드 디스크 등에서 데이터가 현재의 위치에서 헤드의 바로 아래까지 회전하는 데 걸리는 시간을

회전 시간(latency time)이라고 부르며, 이는 곧 하드 디스크의 중요한 성능 지표 중 하나가 됩니다.

 

이러한 저장장치의 구조상 고정축이 특정 위치에 있을 때,

모든 헤드에 의해 액세스할 수 있는 트랙의 모음이 존재하게 되는데, 이러한 트랙의 집단을 ‘수직 실린더’라고 부릅니다.

그리고 이러한 고정축을 새로운 ‘실린더’로 옮기는 과정을 탐색(seek) 작업이라고 합니다.

 

정리하자면, 하드 디스크와 같은 전통적인 저장장치에서 어떤 특정한 데이터에 접근하려면 아래와 같은 단계를 거쳐야 합니다.

 

① 해당 실린더로 고정축을 이동시킵니다.

② 데이터 레코드가 저장된 부분이 헤드의 바로 아래에 오도록 디스크를 회전시킵니다.

③ 임의의 크기를 가진 레코드(최대 트랙 전체)가 헤드에 의해서 읽거나 쓰도록 디스크를 회전시켜야 합니다.

 

그리고 위와 같이 세 단계를 거쳐 데이터의 입출력이 일어나는 시간을 전송시간(transmssion time)이라고 합니다.

놀랍게도 이러한 작업이 일어나는 데 걸리는 시간은 0.01초에서 0.1초로 아주 짧습니다.

하지만 CPU는 이보다 훨씬 빠른 성능을 가졌기 때문에

이와 비교하면 디스크의 저장 속도는 매우 느리다고 평가될 수밖에 없는 것입니다.

---

디스크 스케줄링의 목적

디스크 스케줄링의 목적은 많은 프로세스가 요청하는 디스크 읽고 쓰기 작업을 최적화하기 위함입니다.

아무리 CPU의 성능이 가장 좋고 빠르다고 해도, L3 캐시와 같은 비싼 저장장치로는 모든 데이터를 저장하기 어렵고,

가능하더라도 그 가격이 매우 비싸므로 소수만이 누릴 수 있는 자원으로 전락하고 말았을 것입니다.

 

그렇기에 앞서 설명한 디스크의 구조상 한계점이 존재하더라도,

운영체제가 많은 프로세스가 디스크에 빠르고 정확하게 데이터를 읽고 쓰는 작업을

수행하게 할 수 있다면 가장 경제적으로 컴퓨터 자원을 활용할 수 있습니다.

 

운영체제가 프로세스가 임의의 탐색 패턴(seek pattern)을 설정하여

프로세스의 요청에 따른 디스크 자원을 분배하는 과정을 ‘디스크 스케줄링’이라고 부릅니다.

 

디스크 스케줄링은 최소한의 기계적 움직임(헤드의 이동)을 통해 요청에 대한 서비스 할 수 있도록 고안되었는데,

이러한 스케줄링 기법에서 중요하게 생각하는 지표는 다음과 같습니다.

 

① 처리량(throughput)

② 평균 응답시간(mean response time)

③ 응답시간의 편차, 즉 예견성(predictability)

 

운영체제는 디스크를 적절히 관리하여 단위시간 당 서비스할 수 있는 요청의 수를

최대로 하는 것이 좋으므로 위와 같은 기준을 고려하여 최적의 디스크 스케줄링을 제공합니다.

---

디스크 스케줄링 기법의 종류

FCFS(First-Come-First-Served) 스케줄링

운영체제의 스케줄링 기법 중 FIFO와 유사한 디스크 스케줄링 기법입니다.

이름에서도 알 수 있듯이 먼저 들어온 요청에 대해서 먼저 서비스합니다.

 

FCFS에서는 요청에 디스크 표면에 균일하게(uniformly) 하게 분포되어 있을 때, 임의의 탐색 형태(seek pattern)를 보입니다.

이와 같은 조건에서, FCFS는 큐에서 대기 중인 요청 간의 위치 관련성을 무시합니다.

 

가령, 운영체제에 들어온 디스크 요청에 아래와 같다고 가정한다면,

 

68, 32, 42, 14, 125

 

디스크의 이동을 그림으로 도식화했을 때 아래와 같습니다.

 

 

---

SSTF(Shortest Seek Time First) 스케줄링

SSTF 스케줄링에서는 탐색 거리가 가장 짧은, 즉 탐색 시간이 가장 짧은 요청이 대기열의 가장 앞에 위치하게 됩니다.

설령, 큐에 앞에 위치하지 않아도 결과적으로 먼저 서비스받게 됩니다.

 

 

 

 

SSTF는 특정한 요청을 차별하는 경향이 있습니다. SSTF는 고도로 편중된 탐색 패턴을(seek pattern) 가지기 때문에

안쪽이나 바깥쪽 트랙이 가운데 트랙보다 훨씬 서비스를 덜 받는 결과를 낳는 경향이 있습니다.

 

SSTF는 FCFS보다 처리량이 더 많고, 보통의 부하 조건에서 평균 응답시간이 더 짧다는 이점을 가집니다.

 

하지만 안쪽과 바깥쪽의 트랙을 차별 대우하기 때문에 응답시간에 큰 편차가 생긴다는 단점이 있습니다.

 

이러한 단점은 오히려 한꺼번에 처리하는 시스템, 즉 배치(batch) 시스템에서는 무시될 수 있는 단점이기도 하지만,

응답시간의 편차가 중요한 시스템 즉 대화형 시스템에서는 SSTF를 채택할 수 없습니다.

 

SSTF는 근본적으로 SJF(Shortest-Job First)와 알고리즘 형태가 같으므로,

디스크 요청에 대한 기아(starvation) 현상을 일으킬 수 있습니다.

---

SCAN 스케줄링

데닝(Denning)이 개발한 SSTF의 개선된 스케줄링 전략입니다.

기존에 SSTF가 가지고 있던 응답 시간에서의 차별대우와 응답 시간의 편차를 극복하기 위해 고안된 디스크 스케줄링 전략입니다.

SCAN은 SSTF와 기본적인 동작은 유사하지만, ‘진행 방향’ 상의 가장 짧은 요청을 먼저 선택한다는 차이점이 있습니다.

즉 SSTF는 디스크 원판에서 방향의 구분이 없는 이동 거리를 계산하지만,

SCAN은 마치 벡터처럼 방향에 대한 정보를 반영했을 때 가장 짧은 거리에 있는 요청을 처리합니다.

 

 

SCAN은 FCFS에서의 속도를 개선한 SSTF에 차별 대우 까지 줄인 균형 잡힌 디스크 스케줄링으로 평가되었고,

실제 구현된 대부분의 스케줄링 시스템에 적용된 기본적인 스케줄링 전략이 되었습니다.

 

하지만, SCAN의 경우 헤드가 위치를 이동함에 따라, 바로 직전에 탐색했던 위치에 요청이 오더라도

진행 방향상에 위치하지 않으면 헤드가 디스크 끝까지 이동한 후 돌아올 때까지 기다려야 합니다.

그리고 이러한 방식은 마치 엘리베이터의 동작 방식과 유사하다고 하여, 엘리베이터 알고리즘이라고도 부릅니다.

 

SCAN에서 요청 밀도가 높은 쪽은 최초의 시작 지점 인근이며, 나중에 처리된 헤드 바로 뒷부분은 비교적 밀도가 낮습니다.

 

다시 말하자면, 초기 헤드의 위치를 기준으로 진행 방향상에 인접한 요청들은 빠른 처리 속도를 보장하지만,

진행 방향이 다르면 그 처리가 늦어지기 때문에,  오히려 밀도가 높은 쪽의 요청이 상당히 오랜 시간을 대기하는 단점이 있습니다.

---

N단계 SCAN 스케줄링

앞선 SCAN 스케줄링의 방법을 개선한 N 단계 스케줄링 방식도 있는데요.

SCAN의 경우, 요청이 들어올 때마다 헤드의 진행 방향과 요청의 위치에 따라 대기 시간의 불평등이 발생했습니다.

하지만, N 단계 SCAN의 경우 어떤 방향의 진행이 시작될 당시에 대기 중이던 요청만을 서비스합니다.

이를 그림으로 표현하면 아래와 같습니다.

 

 

 

위에서 검은색 점은 초기에 들어온 디스크 요청이고, 회식 점은 서비스가 시작된 이후에 들어온 요청을 의미합니다.

N-SCAN은 요청의 시점에 따라 서비스 받을 우선순위를 구분하기 때문에 진행방향 상에 존재하는 요청이라도 무시할 수 있습니다.

 

N단계 SCAN은 처리량과 평균 응답 시간에서 좋은 실행 효율을 보입니다.

가장 중요한 특징은 SSTF나 보통의 SCAN보다 응답시간의 편차가 작다는 점입니다.

N단계 SCAN은 SCAN의 장점에 단점을 보완하여, 요청이 계속 도착하는 경우 다른 요청에 무한히 기다릴 가능성을 배제해줍니다.

 

---

C-SCAN(Circular SCAN) 스케줄링

이외에도 SCAN 전략을 수정한 C-SCAN(Circular SCAN)이라는 스케줄링 방법이 있습니다.

SCAN은 C-SCAN이나 SCAN과 다르게 실린더를 하나로 연결된 원처럼 사용한다는 특징이 있습니다.

이것은 헤드를 디스크 실린더가 끝이 있는 것처럼 이동시키는 것이 아니라,

처음과 끝이 연결된 트랙으로 사용한다는 의미입니다.

 

C-SCAN에서 헤드는 항상 바깥쪽의 실린더에서 안쪽 실린더로 움직이며 가장 짧은 탐색 시간을 갖는 요청을 서비스합니다.

 

 

 

즉, 현재 헤드의 위치에서 다음 요청에 상대적 위치를 계산하여 더 짧은 거리에 있는 요청을 처리하게 합니다.

 

SCAN과 C-SCAN은 운영체제에 들어오는 요청의 크기에 따라 그 장점이 구분됩니다.

상대적으로 적은 요청이 발생하는, 부하가 적은 상황에서는 SCAN 방식이 우수합니다.

하지만, 부하가 많은 상황에서는 C-SCAN 방식으로 동작하는 것이 더 좋은 성능을 보입니다.

  

 이처럼 실린더에서 헤드가 다음 요청을 위해 이동하기 전 요청의 여부를 검사하는 방식을 LOOK이라고 하고,

C-SCAN에서처럼 하나로 이어진 공간으로 인지하여 헤드를 이동시키는 것을 C-LOCK이라고 합니다.

 

오늘날의 디스크 스케줄링 기법에서는 엄밀히 C-SCAN과 같은 방법 보다는.

헤드는 각 방향으로 요청에 따르는 거리만큼 이동하고, 현재 방향에서 더 요청이 없다면 방향을 바꾸는 방식을 채택합니다.

---

에센바흐 기법(Eschenbach scheme)

SCAN, C-SCAN과 같은 스케줄링 기법의 등장에도 불구하고,

매우 부하가 큰 시스템에서는 이 또한 성능의 개선이 요구되었습니다.

 

예컨대, 매우 부하가 큰 항공예약시스템 같은 경우 탐색 시간(seek time)뿐만 아니라,

회전 시간(rotational delay)까지 최적화하기 위해 고안된 스케줄링 기법입니다.

  

에센바흐 기법은 기본적으로 C-SCAN처럼 헤드가 움직입니다.

하지만, 모든 실린더는 실린더에 요청의 여부와 상관없이 전체 트랙이 한 바퀴 회전할 동안 서비스를 받습니다.

 

그리고, 한 실린더 내에서 회전 위치를 이용할 수 있도록 요청을 재배열합니다.

그러나 두 개의 요청이 실린더에서 같은 섹터에 있으면 한 방향으로 진행 시 한 개의 요청만을 서비스하는 방식입니다.

 

---

정리하며...

지금까지 소개한 스케줄링 기법은, 운영체제에 들어오는 요청의 크기와 형태에 따라 그 성능이 달라질 수 있습니다.

예컨대, 매우 적은 요청만 발생하는 시스템에서는 모든 디스크 스케줄링 기법의 성능이 서로 거의 비슷합니다.

 

그러나, 예를 들어 디스크에 연속적으로 할당된 파일을 읽는 작업을 수행한다면

디스크 상에 인접된 범위에서 많은 요청을 발생시키는 구조이므로, 헤드의 이동이 제한됩니다.

 

반면에 링크 파일이나 색인(Index) 파일의 경우 블록들이 디스크에 산재하여 있어서

헤드의 이동 거리가 증가할 수 있지만, 디스크의 사용 효율은 오히려 높아집니다.

 

따라서 이러한 점을 고려하면, 디스크에 저장되는 정보 중 디렉터리와 색인과 같은 정보는

디스크의 중간에 위치하여 양 끝으로 퍼져가는 형식이 헤드의 이동을 줄일 수 있습니다.

 

왜냐하면 어떤 파일이든 우선 오픈(open)되어야 읽을 수 있는데,

오픈(open)되려면 디렉터리 구조에 대한 정보를 먼저 알아야 하기 때문입니다.

 

따라서, 이와 같은 이유로 디스크 스케줄링 알고리즘은 운영체제상에서 별개의 하나의 모듈로 작성하고

필요에 따라 사용해온 스케줄링 알고리즘을 제거하고 다른 알고리즘으로 대체할 수도 있습니다.

 

---

참고자료

김완규, 고정국, 진광윤, 최신형, 하성권, 허덕행 | 핵심 운영 체제론 | 두양사