[Chapter 12. 대용량 저장장치 구조] 디스크와 디스크 스케줄링(FCFS, SSTF, SCAN, LOOK)

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

자기 디스크 (Magnetic Disk)

---

 

플래터(platter) : 원형 평판 모양으로, 정보를 플래터 상에 자기적으로 기록하여 저장한다.

 

읽기-쓰기 헤드(read-write head)는 모든 플래터의 각 표면 바로 위에서 움직이며

헤드는 모든 헤드를 한꺼번에 이동시키는 디스크 암(disk arm)에 부착되어 있다.

디스크 암 : 읽기나 쓰기를 수행해야 하는 트랙을 찾아가는 역할

 

동일한 암 위치에 있는 트랙의 집합은 하나의 실린더(cylinder)를 형성한다.

 

 

플래터의 표면은 원형 트랙(track)으로 논리적으로 나뉘어 있고, 이것은 섹터(sector)로 나뉘어 있다.

* 섹터 : 디스크의 입출력 단위

 

 

디스크의 3가지 시간 지연 요소

플래터에서 작업(읽기 또는 쓰기)을 수행하기 위해서는

1. 헤드를 트랙으로 움직이고 2. 트랙 상에서 원하는 섹터가 올 때까지 기다려야

작업을 진행해야 하는 섹터에서 작업을 수행할 수 있게 된다.

 

 

이에 디스크의 속도는 다음의 3가지 항목에 의해 영향을 받게 된다.

 

1. 탐색 시간 (seek time)

디스크 암이 헤드를 원하는 실린더로 움직이는 데 걸리는 시간

 

2. 회전 지연 시간 (rotational latency)

디스크 헤드가 원하는 섹터 위치로 도달하기까지 회전하는 데 필요한 시간

 

3. 전송 시간 (transfer time)

드라이브와 컴퓨터 간의 데이터 흐름 비율

 

 

디스크 스케줄링

---

운영체제는 효율적인 하드웨어 사용을 위하여 디스크 드라이브에게 빠른 접근 시간과 높은 전송량을 제공해야 한다.

 

프로세스가 입출력을 필요로 할 때마다 운영체제에 시스템 호출을 하는데, 이 호출에는 여러 인수가 주어진다.

 

• 입력 / 출력
• 디스크 주소
• 메모리 주소
• 전송될 섹터의 수

 

디스크 드라이브와 제어기가 쉬고 있는 상태라면 이 요청은 즉시 시작되지만

만약 이미 다른 작업을 수행 중이라면 이 요청은 드라이브의 큐(queue)에 들어가 기다려야 한다.

 

즉, 시분할 시스템에서는 동시에 수행 중인 프로세스들에 의해 발생되는 요청이 수시로 디스크 입출력 요청 큐에 도착하게 된다.

 

 

디스크 스케줄링이란, 디스크 입출력 요청 큐에 도착한 프로세스의 요청들 중

어느 것을 먼저 선택하여 실행할 것인지 순서를 결정하는 것이다.

 

디스크 스케줄링의 목적은 처리율의 극대화이다.

1. 평균 반응 시간 줄이기

어떤 요청이 디스크 구동기에 전해질 때부터 그 결과가 나올 때까지의 시간의 평균값을 줄이는 것

 

2. 반응 시간의 분산 줄이기

디스크 입출력 시간의 예측성을 향상하는 것

 

 

따라서 효율적인 디스크 스케줄링을 통해 접근 시간과 디스크 대역폭을 모두 향상할 수 있다.

* 디스크 대역폭(bandwidth) : 단위 시간당 전송되는 총 바이트 수

 

선입 선처리 스케줄링 (FCFS Scheduling)

FCFS : First-Come First-Served

 

먼저 도착한 요청이 우선적으로 서비스받게 되는 기법이다.

 

대기 큐를 재배열하지 않으며, 탐색 패턴을 최적화하려는 시도가 없다.

따라서 더 높은 우선순위를 가진 요청이 늦게 도착하더라도 요청의 순서가 유지된다.

 

 

장점

요청 큐에 먼저 도착한 요청이 우선적으로 서비스받게 되므로 근본적인 공평성이 보장되고 프로그래밍이 용이하다.

 

단점

요청이 많아질 경우 평균 응답 시간이 길어지게 된다. (효율이 낮음)

 

최소 탐색 시간 우선 스케줄링 (SSTF Scheduling)

SSTF : Shortest-Seek-Time-First

 

현재 헤드 위치에서 출발하여 탐색 시간이 가장 짧은 요청을 먼저 서비스하는 기법이다.

 

헤드가 어떤 요청들을 처리하기 위해 먼 곳까지 이동하기 전에

현재의 헤드 위치에서 최소의 탐색 시간을 요하는 요청을 골라 먼저 처리해나가는 것이다.

 

장점

FCFS 스케줄링보다 처리량이 많고 평균 응답 시간이 짧다.

 

단점

안쪽이나 바깥쪽의 트랙과 가운데에 위치한 트랙 간 응답 시간에 편차가 생길 수 있다.

 

가운데에 있는 트랙은 서비스 빈도가 높지만,

제일 안쪽과 바깥쪽 트랙에 대한 요청은 서비스를 덜 받게 되어 기아 현상이 발생할 수 있다.

 

 

SSTF는 처리량이 주요 목표인 일괄 처리 시스템에 유용하고, 응답 시간의 편차가 크기 때문에 대화형 시스템에는 부적합하다.

 

SCAN 스케줄링 & LOOK 스케줄링

헤드 진행 방향(sweep direction) 상의 가장 짧은 거리에 있는 요청을 먼저 서비스하는 기법이다.

디스크 암이 디스크의 한 끝에서 시작하여 다른 끝으로 이동하며, 가는 길에 있는 요청을 모두 처리하는 것이다.

 

SCAN 방식은 SSTF가 갖는 응답 시간 편차에 있어서 차별대우와 큰 편차를 극복하기 위해 개발되었고,

엘리베이터 알고리즘이라도도 부른다.

 

SCAN 스케줄링

 

* SCAN과 LOOK 스케줄링의 차이

 

SCAN

움직이는 방향으로 더 이상 요청이 없으면

인위적으로 헤드를 디스크 끝까지 이동한 후에 반대 방향으로 헤드를 움직이게 된다.

 

LOOK

움직이는 방향으로 더 이상 요청이 없으면

끝까지 가지 않고, 그 자리에서 반대 방향으로 헤드를 움직이게 된다.

 

 

이들은 대기 큐의 동적인 특성을 효율적으로 반영했으며, SSTF에서 발생하는 차별 대우(반응시간의 편차)를 많이 없앴다. 

 

 

단점

응답 시간의 편차는 여전히 존재한다.

 

헤드 진행 도중, 새로 도착한 요청도 함께 서비스를 받게 되므로

안쪽과 바깥쪽 트랙은 가운데 트랙보다 더 적은 서비스를 받을 수 있다는 문제점은 고쳐지지 않았다.

 

각 트랙에 대한 요청 분포가 균일하다고 가정하자.

헤드가 한쪽 끝에 이르러 방향을 바꾸어야 할 시점을 보았을 때

요청 밀도가 높은 쪽은 반대편 시작 부분이며, 현재 헤드 근처 부분은 비교적 밀도가 낮다.

 

따라서 밀도가 높은 쪽의 요청은 처리될 때까지 상당히 오랜 시간을 대기하게 된다.

 

C-SCAN 스케줄링

C-SCAN은 각 요청에 대한 대기 시간을 좀 더 균등하게 하기 위해 SCAN 방식을 변형한 기법이다.

 

한쪽 방향으로 헤드를 이동해 가면서 요청을 처리하지만,

한쪽 끝에 다다르면 반대 방향으로 헤드를 이동하여 서비스를 하는 것이 아니라

처음 시작했던 자리로 다시 되돌아가서 서비스를 시작한다.

 

 

이 방식은 복귀 시간이 필요하나, 요청마다의 처리 시간이 공평하다.