Disk Management & Scheduling

이화여자대학교 반효경 교수님의 2014년 Operating System 강의를 시청한 후 정리한 내용이다.

 

http://kocw.net/home/cview.do?cid=3646706b4347ef09

운영체제

 

 

Disk Structure

Abraham Silberschatz, Operating System Concepts 10th ed.

• Logical Block: 디스크 외부에서 디스크로 접근할 때의 최소 정보 단위. 1차원 배열로 다룬다.
• Sector: Logical Block이 실제 disk에 mapping된 정보 저장 단위. 0번 sector는 최외곽 실린더의 첫 트랙의 첫 섹터를 말한다^[각주:1].
• Platter: 정보를 저장하는 마그네틱 원판
• Track: platter 위에 있는 동심원. sector로 구성되어 있다.
• Cylinder: 모든 platter에 같은 위치의 track들의 집합
• Read-Write Head: platter의 마그네틱 패턴을 감지하여 데이터를 읽거나 쓰는 부분

Disk Management

• Physical Formatting(Low-Level Formatting): 디스크를 sector들로 나누어 디스크 컨트롤러가 읽고 쓸 수 있도록 하는 과정이다. 실제 데이터를 저장할 때 sector 내에만 저장하는 것이 아닌, sector의 앞, 뒤에 각각 header와 link를 두어 sector의 번호나 ECC^[각주:2]등을 저장하여 운영한다.
• Logical Formatting: 파일 시스템을 만드는 것을 말한다.
• Partitioning: 한 개의 디스크를 두 개 이상의 partition으로 나누는 과정으로, OS 에서는 partition 1개를 하나의 독립적인 디스크로 본다.
• Booting
  1. 전원이 공급되면, CPU가 real mode로 동작하여 reset vector^[각주:3]을 실행한다. 이 명령은 ROM의 BIOS firmware의 entry point로 jump한다.
  2. BIOS는 POST(Power-On Self-Test)과정을 거치는데, 주변 장치를 검사하고 초기화한다. 그리고 disk와 같은 비휘발성 기억 장치 중 부팅 가능한 장치를 찾는다.
  3. BIOS가 부팅 가능한 장치를 발견하면, 해당 장치의 boot sector인 MBR code를 실행한다. MBR은 자신이 속한 장치의 다른 partition에 부팅 가능한 partition을 찾고, 해당 partiton의 boot sector인 VBR(Volume Boot Record)의 code를 실행한다.
  4. VBR code는 OS의 부팅 이미지를 메모리에 올리는데. 이 부팅 이미지는 second-stage boot loader로써 kernel을 메모리에 올린다.

Access Time

disk에서 데이터를 읽거나 쓸 때 걸리는 Access Time은 3개의 요소로 나눌 수 있다.

• Seek Time: head가 해당 cylinder로 이동하는 시간. 이 시간이 3가지 요소 중에서 많은 비중을 차지한다.
• Rotational latency: head가 원하는 sector에 접근하기 위해 platter가 회전하는 시간
• Transfer Time: 데이터를 sector에 실질적으로 읽고 쓰는 시간

데이터가 읽고 쓰일 때 이러한 접근 시간이 소모되는데, 단위 시간 당 읽고 쓰인 바이트의 수를 Disk Bandwidth이라 한다. 결국 disk scheduling에서는 가장 시간을 많이 소요하는 seek time을 줄이는 것이 목표이다.

Disk Scheduling Algorithm

disk를 scheduling하는 주체는 OS이므로 logical block 번호를 이용하여 scheduling한다. 그러나 이 강의에서는 cylinder 번호(0~199번)로 설명하였다. 이때 기술되는 각 알고리즘들은 요청 큐에 98, 183, 122, 14, 124, 65, 67 번호가 있고 head가 53번에서 시작할 때를 가정하여 설명한다.

Disk Scheduling Algorithm #1: FCFS (First Come First Serve)

Abraham Silberschatz, Operating System Concepts 10th ed.

FCFS는 먼저 요청된 cylinder 번호에 먼저 접근하는 알고리즘이다. 위 그림에서, 53번을 가리킨 head가 98번, 183번 등 순서대로 head를 이동한 것을 볼 수 있다. 이 알고리즘을 적용하면 총 640번 cylinder을 이동하게 되며, 불필요하게 head의 이동이 많아지게 된다.

Disk Scheduling Algorithm #2: SSTF (Shortest Seek Time First)

Abraham Silberschatz, Operating System Concepts 9th ed.

SSTF는 현재 head 위치에서 요청 중 제일 가까운 cylinder로 이동하는 알고리즘이다. 현재 53번 cylinder에서, 요청 queue 중 가장 가까운 cylinder는 65번이므로 해당 cylinder로 이동한 것을 볼 수 있다. 이 알고리즘을 적용하면 head는 총 cylinder를 236번 이동한다. 현재 위치에서 가장 가까운 cylinder로 이동하므로 이동 거리가 짧아지지만, 번호가 낮은 cylinder로 head가 이동하고 낮은 위치의 cylinder들의 요청이 계속 들어오면, 높은 번호의 cylinder의 접근 요청을 받지 못하는 Starvation이 발생한다.

Disk Scheduling Algorithm #3: SCAN

Abraham Silberschatz, Operating System Concepts 10th ed.

elevator scheduling이라고도 불리는 이 알고리즘은 head를 한 방향으로 끝까지 이동하여 중간의 요청을 처리한다. 만약 한쪽 끝에 도달했다면 다시 반대로 이동하여 동일한 동작을 수행한다. 위 그림에서, 53번부터 시작하여 낮은 번호의 방향으로 이동하며 37, 14번의 요청을 처리하다가, 0번 cylinder에 도달한 후 다시 반대 방향으로 이동하는 것을 볼 수 있다. 이 알고리즘을 사용하면 head를 일정하게 한 방향으로만 움직이므로  head의 이동 거리가 짧아지며, starvation 문제가 발생하지 않는다. 그러나 cylinder의 위치에 따라 요청을 기다리는 시간이 다르다는 것이 문제인데, 14번 요청은 짧은 시간 내에 처리되지만, 두 번째로 일찍 들어온 183번 요청은 head 이동 방향과 반대에 위치하므로 제일 마지막에 처리된다.

Disk Scheduling Algorithm #4: C-SCAN (Circular SCAN)

Abraham Silberschatz, Operating System Concepts 10th ed.

SCAN의 변형인 C-SCAN은 head를 일정한 방향으로만 이동하는 대신, 요청을 처리하는 방향은 오직 한 가지로만 정해져 있다. 즉, 한 방향으로 가면서 요청을 처리했다면, 반대 방향으로 이동할 때는 요청을 처리하지 않고 출발점까지 다시 이동한다. 이 알고리즘을 사용하면 SCAN보다 요청 대기시간이 더욱 균일해진다.

Disk Scheduling Algorithm #5: N-SCAN

SCAN과 마찬가지로 head가 한 방향씩 끝까지 이동하면서 요청을 처리하지만, 이동 중 발생하는 요청은 처리하지 않고, 끝 지점에서 다시 돌아올 때 처리한다. 이 알고리즘을 사용하면 queue에 있는 요청들의 대기 시간을 줄일 수 있다.

Disk Scheduling Algorithm #6: C-LOOK (Circular LOOK)

Abraham Silberschatz, Operating System Concepts 9th ed.

SCAN의 단점을 보완한 알고리즘으로, 무조건 끝까지 head를 이동하는 SCAN과 달리, 해당 head의 위치에서 다음 이동할 cylinder들에 대한 요청이 없을 경우 방향을 전환하는 것이 LOOK Scheduling이다. 위 예시를 보면, head가 183번까지 이동한 상태에서 그 위의 cylinder에 대한 요청이 없으므로 해당 위치에서 방향을 바꾼다. 그러나 Circular LOOK이므로 반대 방향으로 이동할 때 요청을 처리하지 않는 것을 볼 수 있다. 또한 반대 방향의 경우에도, 처리해야할 요청 cylinder들 중 가장 낮은 14번에서 방향을 전환하며 요청을 처리하는 것도 확인할 수 있다.

Selection of a Disk Scheduling Algorithm

SCAN 알고리즘은 disk head의 이동 시간을 줄이며 starvation을 해결함로, 현대의 스케쥴링 알고리즘은 SCAN에 기반한다. 그러나 디스크 요청 시간은 이러한 알고리즘 뿐만 아니라 file system의 디스크 할당 방식의 영향을 받는데, 연속 및 불연속 할당에 따라 head의 이동 시간이 변하기 때문이다. 또한 여러 요청을 한번에 merging하여 I/O를 처리하여 효율성을 높이는 방법도 있는데, 이렇게 디스크의 용도와 상황에 따라 쉽게 다른 알고리즘으로 교체 가능하도록, 스케쥴링 알고리즘 모듈을 OS와 별도로 작성되는 것이 바람직하다.

Swap Space Management

swap area는 부족한 DRAM을 대신하여 page를 저장하는 영역이다. 그런데 page는 프로세스가 메모리에 올라가는 데이터들이므로, 프로세스가 종료하면 해당 데이터들은 소멸된다. 즉 swap area에서 공간 효율성은 중요하지 않다. 무엇보다 프로세스의 특정 page에 접근할 때 page fault가 발생하면 최대한 빨리 swap area의 page를 제공하는 것이 응답성과 프로세스 동작 속도 측면에서 좋으므로, swap area는 속도 효율성을 우선시한다. 따라서 seek time을 줄이기 위해, file system에서와 달리 swap area에서의 디스크 할당은 큰 단위(512KB, 128KB, 64KB, 32KB, 16KB)로 진행되어, 한 번의 seek로 최대한 많은 데이터에 접근할 수 있도록 한다.

RAID

RAID(Redundant Array of Independent Disks)는 여러 디스크를 묶어 사용하여 데이터들을 중복, 분산 저장하는 방식이다. 데이터를 분산 저장하면, 추후에 해당 데이터들을 요청할 때 여러 디스크에서 분산된 데이터를 병렬적으로 제공하므로 디스크의 처리 속도를 향상시킨다. 이렇게 데이터를 여러 디스크에 분산 저장하는 방법을 Interleaving, Striping이라 한다. 그리고 데이터를 중복 저장할 경우, 여러 디스크 중 하나가 고장이 발생해도 다른 디스크로부터 데이터를 제공받을 수 있어 신뢰성이 향상된다. 이렇게 데이터를 여러 디스크에 중복 저장하는 방법을 Mirroring, Shadowing이라 한다. 또한 단순 중복 저장 뿐만 아니라, Parity정보도 같이 저장하여 일부 저장된 정보만으로 오류를 검출하고 복구가 가능하도록 한다.

 

 

참고한 자료

>> book

Abraham Silberschatz, Operating System Concepts 10th edition

Abraham Silberschatz, Operating System Concepts 9h edition

>> Disk Structure

https://whitesnake1004.tistory.com/273

https://jhnyang.tistory.com/105

>> Booting

https://www.computerhope.com/jargon/b/bootload.htm

https://en.wikipedia.org/wiki/Booting#Boot_sequence

https://say2.tistory.com/entry/MBR-VBR%EC%97%90-%EA%B4%80%ED%95%98%EC%97%AC

 

 

 

1. MBR(Master Boot Record)라 한다. [본문으로]
2. Error-Correcting Code로, head, trailer의 ECC와 data에서 생성된ECC가 같은지 비교하여, 정상적으로 I/O됐는지 확인한다. [본문으로]
3. x86, x86-64에서는 물리 메모리 상 reset vector의 위치가 0xFFFFFFFF0에 있다. [본문으로]