10. Disk management and Scheduling

디스크의 구조

Logical block

디스크의 외부에서 보는 디스크의 단위 정보 저장 공간들

주소를 가진 1차원 배열처럼 취급한다
정보를 전송하는 최소 단위
내부에서는 logical block 단위로 접근

Sector

logical block이 저장되는 디스크 내의 물리적인 위치

디스크 내부에서 관리
디스크를 읽고 쓰는 요청은 disk controller가 수행
logical block이 물리적인 디스크에 매핑된 위치
sector 0은 가장 바깥쪽 실린더의 첫 트랙에 있는 첫 번째 섹터
sector 0에는 부팅과 관련된 정보가 담겨있다

디스크 관리

physical formatting (low-level formatting)

디스크를 컨트롤러가 읽고 쓸 수 있도록 섹터들로 나누는 과정

각 섹터는 header + 실제 data (보통 512bytes) + trailer로 구성
header와 trailer에는 부가적인 정보(일종의 메타데이터)가 저장됨
sector number, ECC(Error-Correcting Code)같은 것들이 저장되며 controller가 직접 접근 및 운영한다
*ECC: 데이터를 요약한 코드 같은 것

Partitioning

디스크를 하나 이상의 실린더 그룹으로 나누는 과정
OS에서는 독립적 disk로 취급 (logical disk)

logical formatting

파일시스템을 만드는 것
FAT, inode, free space 등의 구조 포함

부팅 절차 (간략)

1. ROM(전원이 꺼져도 내용이 유지됨)에 있는 'small bootstrap loader'의 실행
2. sector 0 (boot block)을 load하여 실행
3. sector 0은 'full bootstrap loader program'
4. OS를 디스크에서 load하여 실행

디스크 스케줄링

디스크는 마그네틱 원판으로 구성됨
한 디스크 안의 원판 개수는 하나일 수도 있고 여러 개일 수도 있다
각 원판은 트랙으로 구성되고 각 트랙은 섹터로 나뉘며 섹터에 최소한의 단위가 저장된다
여러 개의 원판에서 상대적 위치가 동일한 트랙들의 집합을 실린더(cylinder)라고 부른다
디스크에 데이터를 읽고 쓰기 위해서는 암(arm)이 해당 실린더로 이동한 후 원판이 회전하여 헤드가 저장된 섹터 위치로 가야 한다

access time의 구성

1. Seek time (가장 큰 시간 구성 요소)
   • 헤드를 해당 실린더로 움직이는데 걸리는 시간
2. Rotational latency
   • 헤드가 원하는 섹터에 도달하기까지 걸리는 회전지연시간
3. transfer time
   • 실제 데이터의 전송 시간

Disk bandwidth

단위 시간 당 전송된 바이트의 수
디스크의 성능을 나타낼 때 쓰는 표현

Disk scheduling

목표: seek time을 최소화하는 것

디스크 스케줄링 알고리즘

queue에 다음과 같이 요청이 들어왔다고 가정

99 183 37 122 14 124 14 124 65 67

현재 헤드는 53번 위치에 있다.
각각의 알고리즘에서 어떤 식으로 처리하는가?

FCFS (First Come First Serve)

먼저 온 순서대로 처리하는 알고리즘

head의 이동 거리 = 640 cylinders
비효율적이다

SSTF (Shortest Seek Time First)

큐에 들어온 요청 중에서 현재 헤드에 가장 가까운 위치부터 처리하는 알고리즘

헤드의 이동 거리가 줄어든다
계속 헤드와 가까운 주소의 요청이 들어오게 되면 멀리 있는 주소는 처리되지 않는 starvation의 발생 가능성이 있다

SCAN

디스크의 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길에 있는 모든 요청을 처리하는 알고리즘

가장 간단하고 획기적인 스케줄링 방법
다른쪽 끝에 도달했을 때 다시 돌아가면서 가는 길에 있는 요청을 처리한다
어떤 위치의 요청이 들어왔는지 신경쓰지 않는다
방식이 비슷하여 엘리베이터 알고리즘이라고도 부른다
실린더 위치에 따라 대기 시간의 편차가 생긴다는 문제점이 있다

C-SCAN (Circular SCAN)

SCAN 방식과 비슷하지만 다른쪽 끝에 도달했을 때 요청을 처리하지 않고 바로 출발점으로 이동하는 알고리즘

이동 거리는 다소 길어질 수 있지만 SCAN보다 균일한 대기 시간을 제공한다

그 외 알고리즘

N-SCAN

SCAN의 변형 알고리즘

arm이 한 방향으로 움직이기 시작하면 그 시점 이후에 도착한 요청은 되돌아올 때 처리한다

LOOK and C-LOOK

SCAN과 C-SCAN에서는 헤드가 디스크 끝에서 끝으로 이동한다
LOOK과 C-LOOK은 헤드가 움직이다가 그 방향에 더 이상 요청이 없으면 즉시 반대로 이동한다

디스크 스케줄링 알고리즘의 결정

SCAN, C-SCAN, LOOK, C-LOOK 등은 디스크 입출력이 많은 시스템에서 효율적인 것으로 알려졌다
file의 할당 방법(연속 할당, 비연속 할당)에 따라 디스크 요청이 영향 받음
디스크 스케줄링 알고리즘은 file 할당 방법에 따라 달라지기 때문에 필요할 경우 다른 알고리즘으로 쉽게 교체할 수 있도록 OS와 별도로 작성하는 것이 바람직하다

 

Swap-space Management

Disk를 사용하는 두 가지 이유 

메모리의 취약성을 보완하기 위함

1. 메모리의 휘발성 보완 -> 비휘발성의 디스크 사용
2. 메모리의 한정된 공간 -> 메모리의 연장 공간으로 디스크 사용 swap space (swap area)

Swap-space

• 가상 메모리 시스템에서는 디스크를 메모리의 연장 공간으로 사용한다
• swap space를 파일시스템 내부에 둘 수 있으나 별도의 파티션을 사용하는 것이 일반적이다
  • 공간 효율성보다는 속도 효율성을 높이는 것이 중요하다 (어차피 빨리 사라지기 때문)
  • 일반 파일보다 훨씬 짧은 시간만 존재하고 자주 참조된다
  • 블록의 크기 및 저장 방식이 일반 파일시스템과는 다르다

RAID

Redundant Array of Independant Disks
여러 개의 디스크를 묶어서 사용하는 것

사용 목적

• 디스크 처리 속도 향상
  • 여러 디스크에 블록의 내용을 분산 저장
  • 병렬적으로 읽어올 수 있기 때문에 속도가 향상된다 (striping, interleaving)
• 신뢰성 (reliability) 향상
  • 동일 정보를 여러 디스크에 중복 저장 
  • 한 디스크가 고장나면 다른 디스크에서 읽어오면 된다 (mirroring, shadowing)
  • 단순한 중복 저장이 아니라 일부 디스크에 parity를 저장하여 공간의 효율성을 높일 수 있다