운영체제 HDD 및 Linux의 I/O Scheduler
컴퓨터엔 보조 기억장치로 하드디스크가 있다. 최근들어 SSD도 나오고, 상위호환으로 NVMe SSD도 나오는 추세이지만 아직까지 HDD도 많이 쓰이고 있다.
HDD에 저장된 데이터를 읽는 방식은 마치 옛날 영화에 나오는 레코드판 음악 장치를 보는 것과 비슷하다.
spindle이 회전판인 platter를 제어하여 디스크 헤드가 track을 읽을 수 있도록 조절한다.
그렇다면 디스크의 대략적인 성능도 표현해보자
크게 seek, rotation, transfer로 구분된다.
- seek time
- 디스크 헤드를 조절하여 목표 sector의 track을 읽는데 걸리는 시간
- rotation delay
- platter를 회전하여 디스크 헤드가 목표 sector까지 도달하도록 하는데 걸리는 시간
- transfer time
- 디스크가 데이터를 전송하는 시간
무작위 작업은 random access, 랜덤하게 흩어진 데이터를 읽을 때를 가정했고, 연속으로 데이터를 읽는 경우 데이터가 연속으로 이어진 경우를 가정했다.
Rotation 딜레이에서 RPM은 분당 회전 수인데, 2를 추가로 나눠준 이유는 디스크의 회전 방향을 다르게 하여 회전 수를 반으로 줄일 수 있기 때문이다.
디스크 스케줄링 알고리즘은 디스크가 어떻게 작업을 수행할 지를 결정한다. 보통 새로운 작업이 들어오면 Disk driver내에 Request Queue에 쌓여 순서를 대기하다 앞의 작업이 모두 수행되면 그제서야 수행한다.
앞서 디스크엔 track이란 단위로 데이터를 저장한다고 했다. 그렇다면 운영체제에서는 이 track들을 어떻게 인식하는걸까
운영체제는 track들을 1차원 배열로 인식하며 인덱싱에 따라 어느 cylinder의 track에 저장할 지 결정한다.
이제 디스크 헤드의 현재 위치가 어디고 어떤 알고리즘에 따라 작업을 수행할 지를 알아보자
FCFS (First Com First Served)
가장 간단한 디스크 스케줄링 알고리즘으로 queue이다.
먼저 들어온게 먼저 나오는 형식으로 거리가 먼 request들이 들어오면 퍼포먼스가 낮아진다는 단점이 있다.
SSTF (Shortest Seek Time First)
가장 짧은 요청시간을 가진 작업부터 먼저 처리하는 방식이다.
단, 상대적으로 긴 요청시간을 가진 작업들은 후순위로 밀려나기 때문에 기아 (starvation)문제가 발생할 수 있다는 단점이 있다.
SCAN
디스크 헤드가 좌우 끝까지 이동하는 과정에 있는 작업들을 처리하는 방식이다.
elevator algorithm이라고도 불린다.
C-SCAN
디스크 헤드가 한 방향 끝까지 가면 다시 원래 시작지점으로 돌아오고 작업을 수행하는 방식이다.
공평성을 위해 고안된 알고리즘이다.
C-LOOK
앞선 작업들은 디스크의 끝 방향에 작업이 있든 없든 가기 때문에 불필요한 움직임이 생길 수 있다.
그래서 방향의 끝에 작업이 없으면 다시 원래 지점으로 돌아오는 방식이다.
Linux I/O Scheduler
리눅스에도 입출력 스케줄러가 존재하는데, queue에서 대기하는 작업들을 Merging, Sorting하는 역할을 한다.
Elevator scheduler
Linux Kernel 2.4에서 사용되며, 디스크 헤드의 이동 방향을 고려하여 동작한다.
Deadline I/O Scheduler
모든 요청에 마감시간 (Deadline)을 두어 처리한다.
4개의 큐를 사용한다, 각각 졍렬된 읽기 큐, 정렬된 쓰기 큐, 입력 FIFO 큐, 출력 FIFO 큐이다.
작업 대기 시간에 Deadline이 지난 요청이 없을 경우에 정렬된 큐에서 요청을 꺼내어 처리한다.
만약 Deadline이 지난다면, FIFO 큐에 있는 요청을 꺼내어 처리한다.
Anticipatory I/O Scheduler
Deadline I/O Scheduler에 기반한 알고리즘이다.
locality 특성 : 인접한 위치에서 짧은 시간 간격으로 읽기 요청을 하는 경우가 빈번하기 때문에 읽기 요청을 처리한 후, 헤드를 이동하지 않고 잠시동안 새로운 요청을 기다린다.
하지만 이 Scheduler는 기본적으로 성능저하가 따를 수 밖에 없으며, 현재는 CFQ scheduler가 Linux 기본 scheduler로 채택되었고, Anticipatory Scheduler는 kernel 2.6.33 이후 버전부터 kernel 에서 제외되었다.
CFQ(Complete Fair Queueing) I/O Scheduler
입출력을 요청하는 모든 프로세스들에 대해 디스크 I/O 대역폭을 공평하게 할당하는 것을 보장한다.
- I/O를 요청한 프로세스 별로 큐를 할당한다.
- 각 프로세스에 대한 큐는 섹터 순으로 정렬한다.
- 각 큐는 라운드 로빈 알고리즘으로 처리된다.
NOOP I/O Scheduler
NO OPeration I/O scheduler 란 의미이다.
인접한 요청 병합만 수행하고 그 외에 아무 작업도 하지 않는다.
Request FIFO 큐만 유지한다.
Random Access를 하는 Device들을 위한 스케줄러이다. 간단하게, 탐색에 대한 부담이 없기 때문에 정렬이 필요 없다.
플래쉬 메모리에서 주로 사용된다.
특히 SSD에서는 random access 시간이 동일하기 때문에 HDD의 디스크 헤드를 고려할 필요가 없다. 따라서 NOOP을 사용하면 성능이 더 좋아질 수 있다.
리눅스에서 현재 사용 중인 I/O 스케줄러를 확인하는 방법은 다음과 같다.
cat /sys/block/sda/queue/scheduler
그런데.. 18.04 LTS 버전은 deadline이나 cfq가 없다고 한다. 16.04 LTS로 바꾸면 잘 나온다!
만약 입출력 스케줄러를 바꾸고 싶다면 echo [스케줄러 이름] | sudo tee /sys/block/sda/queue/scheduler로 수정할 수 있다.