[운영체제] Disk Management and Scheduling

먼저 Disk란 흔히 알고있는 보조 기억 장치입니다.

하드디스크에 대해 많이 다뤄봤을 텐데, 하드디스크는 몇장의 디스크를 겹쳐 놓은 것으로 이해할 수 있습니다.

01. Disk 구조

디스크의 구조는 크게 두가지로 나눌 수 있습니다.

• Logical Block
  • 디스크의 외부에서 보는 디스크의 단위 정보 저장 공간들
  • 주소를 가진 1차원 배열처럼 취급
  • 정보를 전송하는 최소 단위
• Sector
  • 디스크를 관리하는 최소 단위 (물리적 단위)
  • Logical block이 물리적인 디스크에 매핑된 위치
  • Sector 0은 최외각 실린더의 첫 트랙에 있는 첫번째 sector입니다.

즉 Logical Block과 Sector는 서로 mapping 되어 있습니다.

02. Disk Management

디스크 관리에는 크게 4가지 단계가 있습니다.

• Physical formatting (Low-level formatting)
  • 디스크를 컨트롤러가 읽고 쓸 수 있도록 sector들로 나누는 과정
  • 각 sector는 header + 실제 data(보통 512 bytes) + trailer로 구성
  • header와 trailer는 sector number, ECC(Error-Correcting Code) 등의 정보가 저장되며 컨트롤러가 직접 접근 및 운영

Sector number : 디스크의 물리적 sector 고유 식별 숫자
ECC : 실제 data를 축약시켜 놓은 것으로, Sector의 데이터를 읽을 때
ECC와 실제 데이터를 비교하여 같다면 bad Sector가 아닌 것으로 판단합니다. (Error 판단)

• Partitioning
  • 디스크를 하나 이상의 실린더 그룹으로 나누는 과정
  • OS는 이것을 독립적 disk로 취급 (logical Disk)
• Logical formatting
  • 파일 시스템을 만드는 것
  • FAT, inode, free space 등의 구조 포함
• Booting
  • ROM에 있는 small bootstrap loader의 실행
  • Sector 0(boot block)을 로드하여 실행
  • Sector 0은 full bootstrap loader program
  • OS를 디스크에서 로드하여 실행

03. Disk Scheduling

• Access time의 구성
  • Seek time : 헤드를 해당 실린더로 움직이는 데 걸리는 시간
  • Rotational latency : 헤드가 원하는 섹터에 도달하기까지 걸리는 회전 지연 시간
  • Transfer time : 실제 데이터의 전송 시간

보통 Seek time이 가장 큰 시간 구성 요소입니다.
한번의 Seek로 가장 많은 양을 읽고 쓰면 굉장히 효율적이겠죠.

> Rotational latency는 보통 seek time의 1/10정도의 시간이 걸립니다.
> Transfer time은 실제 데이터의 전송 시간입니다. 굉장히 작은 시간 요소입니다.

• Disk bandwidth
  • 단위 시간 당 전송된 바이트의 수
• Disk scheduling
  • Seek time을 최소화하는 것이 목표
  • Seek time은 Seek distance와 근사합니다. (Seek time ≒ Seek distance)

04. Disk Scheduling Algorithm

큐에 다음과 같이 실린더 위치의 요청이 존재하는 경우, 디스크 헤드 53번에서 시작한 각 알고리즘의 수행 결과는? (실린더 위치는 0 ~ 199)

**Queue** = 98, 183, 37, 122, 14, 124, 65, 67
Head starts at **53**

실린더 번호를 기준으로 알고리즘을 설명하겠습니다.

04-1. FCFS (First Come First Service)

알고리즘 이름 그대로 처음 들어온 순서대로 요청을 처리합니다.

총 head의 이동 : 640 cylinders

04-2. SSTF (Shortest Seek Time First)

현재의 헤드 위치에서 가장 가까운 요청부터 처리합니다.

• 이는 Starvation 문제가 발생합니다.

총 head의 이동 : 236 cylinders

04-3. SCAN

Disk arm이 디스크의 한쪽 끝에서 다른 쪽 끝으로 이동하며 가는 길에 있는 모든 요청을 처리합니다.
다른 한쪽 끝에 도달하면 역방향으로 이동하며 오는 길에 있는 모든 요청을 처리하며 다시 반대쪽 끝으로 이동하는 알고리즘입니다.

• 엘레베이터 스케쥴링이라고도 불립니다.
• 실린더 위치에 따라 대기 시간이 다르다는 문제점이 있습니다.

총 head의 이동 : 208 cylinders

04-4. C-SCAN

헤드가 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리합니다.

다른쪽 끝에 도달했으면 요청을 처리하지 않고 곧바로 출발점으로 다시 이동하여
같은 방향으로 이동하며 가는 길목에 있는 모든 요청을 처리합니다.

SCAN은 지그재그 모양이었다면, 이는 같은 방향으로만 이동하는 모양이 되겠죠.

• SCAN보다 균일한 대기 시간을 제공합니다.

04-5. Other Algoritms

04-5-1. N-SCAN

SCAN의 변형 알고리즘입니다.

Disk arm이 한 방향으로 움직이기 시작하면, 그 시점 이후에 도착한 요청은 되돌아 올때 수행하게 됩니다.

04-5-2. LOOK and C-LOOK

SCAN이나 C-SCAN은 헤드가 디스크 끝에서 끝으로 이동합니다.

LOOK과 C-LOOK은 헤드가 진행 중이다가 그 방향에서 더 이상 기다리는 요청이 없다면

헤드의 진행 방향을 즉시 반대로 이동하게 됩니다.

04-6. Disk Scheduling Algorithm의 결정

• SCAN, C-SCAN 및 그 응용 알고리즘 LOOK, C-LOOK 등이 일반적으로
  디스크 입출력이 많은 시스템에서 효율적인 것으로 알려져 있습니다.
• File의 할당 방법에 따라 디스크 요청이 영향을 받습니다.
• 디스크 스케쥴링 알고리즘은 필요할 경우 다른 알고리즘으로 쉽게 교체할 수 있도록 OS와 별도의 모듈로 작성되는 것이 바람직합니다.

05. Swap Space Management

우선 디스크를 사용하는 두 가지 이유가 무엇일까요?

• Memory의 volatile(휘발성) 특성 때문에 file system을 사용하기 위해서입니다.
• 프로그램 실행을 위한 Memory 공간의 부족 문제를 해결하기 위해 swap space(area) 로 사용하기 위해서입니다.

이때 swap space에 대해 더 알아보도록 하겠습니다.

Swap space

• Virtual memory system에서는 디스크를 memory의 연장 공간으로 사용
• 파일시스템의 내부에 둘 수도 있으나, 별도 partition 사용이 일반적
  • 공간 효율성보다는 속도 효율성이 우선 (프로세스가 끝나면 어차피 사라질 내용이기 때문입니다. )
  • 일반 파일보다 훨씬 짧은 시간만 존재하고 자주 참조됨
  • 따라서 block의 크기 및 저장 방식이 일반 파일시스템과 다름

06. RAID

RAID (Redundant Array of Independent Disks)는 여러개의 디스크를 묶어서 사용하는 것 입니다.

그렇다면 RAID를 왜 사용할까요?

• 디스크 처리 속도 향상
  • 여러 디스크에 block의 내용을 분산 저장
  • 병렬적으로 읽어옴 (interleaving, striping)
• 신뢰성(reliability) 향상
  • 동일 정보를 여러 디스크에 중복 저장
  • 하나의 디스크가 고장(failure) 시 다른 디스크에서 읽어옴 (mirroring, shadowing)
  • 단순한 중복 저장이 아니라, 일부 디스크에 parity를 저장하여 공간의 효율성을 높입니다.

Parity bit
정보의 전달 과정에서 오류가 생겼는지를 검사하기 위해 추가된 비트입니다.

추가로 학습할 내용 > 추가 예정

https://www.stevenjlee.net/2020/03/01/이해하기-raid-구현-방식과-종류에-대하여/

reference

---

운영체제와 정보 기술의 원리 - 반효경