13. Mass Storage Management

Dept. of Computer Science
Hanyang University

Physical Disk Structure

• 디스크는 얇은 금속 플래터(platter)로 구성되며,
  그 위를 읽기/쓰기 헤드가 비행하며 동작

• 디스크에서 읽기 위해 지정해야 할 요소:

  • cylinder #
  • surface #
  • sector #
  • transfer size
  • memory address

• 전송 시간(Transfer time)은 다음을 포함:

  • Seek time
  • Rotational delay
  • Transfer time

Disk Structure

• 디스크 드라이브는 논리 블록(logical block)의 1차원 배열로 주소 지정됨
  → 논리 블록은 전송의 최소 단위

• 이 1차원 배열은 디스크의 섹터들로 매핑됨

  • sector 0 = 최외곽 실린더의 첫 번째 트랙의 첫 번째 섹터
  • 매핑은 일반적으로 각 트랙을 순서대로 진행
    → 실린더 바깥쪽에서 안쪽으로 진행
    (실제 구현은 제품마다 다름)

Disk Scheduling

• 디스크 접근 시간은 두 가지 주요 요소로 구성됨:

  • Seek time: 디스크 헤드를 원하는 실린더로 이동하는 시간
  • Rotational latency: 원하는 섹터가 헤드 아래로 올 때까지의 대기 시간

• 목표: Seek time 최소화

  • Seek time ≈ Seek distance

• 디스크 대역폭:

  $$\text{Disk bandwidth} = \frac{\text{총 전송 바이트 수}}{\text{요청부터 완료까지 걸린 총 시간}}$$

Seek Time Benchmark

• 실린더 수에 따른 평균 seek time의 변화 그래프

• Seek time 모델:

  $$a + b\sqrt{d} \quad \text{(a, b: 상수, d: 실린더 간 거리)}$$

Disk Scheduling (Cont.)

• 디스크 I/O 요청을 처리하는 알고리즘은 다양함

• 예시 요청 큐 (0~199):

  98, 183, 37, 122, 14, 124, 65, 67
  

• 현재 헤드 위치: 53

FCFS

• First-Come, First-Served 디스크 스케줄링 방식
• 요청 순서대로 처리함
• 단순하지만, seek 이동이 비효율적
• 예시:

  queue = 98, 183, 37, 122, 14, 124, 65, 67
  head starts at 53
  
• 총 이동 거리: 640 cylinders

SSTF

• Shortest Seek Time First
• 현재 헤드 위치에서 가장 가까운 요청부터 처리
• SJF(Shortest Job First)의 일종으로, 일부 요청은 기아(starvation) 상태 발생 가능
• 성능은 예측 불가능
• 예시에서의 총 이동 거리: 236 cylinders

SSTF (Cont.)

• 같은 queue와 시작 위치에서
  SSTF 방식은 가장 가까운 요청부터 차례로 접근
  → 효율적이나, 편향된 요청은 무기한 대기할 수 있음

SCAN

• 디스크 암이 디스크의 한쪽 끝에서 시작하여 반대편 끝으로 이동하며 요청 처리

• 끝에 도달하면 방향을 바꿔 다시 이동하며 요청 처리

• 엘리베이터 알고리즘이라고도 불림:

  • 올라가면서 요청 처리
  • 내려오면서도 요청 처리

• 총 이동 거리: 208 cylinders

• 문제점:

  • 안쪽 트랙은 두 번 서비스됨 (편도마다 접근)
  • 외곽 트랙에 비해 불공정

C-SCAN

• SCAN보다 더 균등한 대기 시간 제공

• 디스크의 한쪽 끝에서 다른 끝까지 이동하며 요청 처리
  → 끝에 도달하면 되돌아오는 경로에서는 요청 처리하지 않음

• 원형 디스크 리스트(circular list)처럼 작동
  → 마지막 실린더에서 첫 번째 실린더로 점프

• 문제점:

  • 반대 방향으로 이동 중에도 요청이 없더라도 계속 진행

• C-SCAN 알고리즘의 디스크 헤드 이동 경로 시각화

• 한 방향으로 모든 요청을 처리한 후,
  되돌아가는 경로에서는 요청을 무시하고 처음 위치로 이동

C-LOOK

• C-SCAN의 변형 버전
• 디스크 끝까지 이동하지 않고, 요청이 있는 마지막 위치까지만 이동
• 그 후 즉시 반대 방향으로 전환
• 디스크 끝까지 가는 불필요한 이동 제거

C-LOOK (Cont.)

• 예시 queue:

  queue = 98, 183, 37, 122, 14, 124, 65, 67
  head starts at 53
  
• 요청이 있는 마지막 지점까지만 이동하고 되돌아옴
  → 보다 효율적인 이동 거리 확보

Arm Stickiness Problem

• SCAN, C-SCAN, SSTF는 Arm Stickiness 문제를 가질 수 있음

• 설명:

  • 특정 트랙에 접근 빈도가 높은 프로세스가 있을 경우
  • 해당 트랙에만 반복적으로 접근 요청을 보내면서 디스크 암을 그 위치에 고정시킴
  • 결과적으로 디스크 전체 사용이 비효율해짐

Disk Management

• 물리적 포맷(Physical formatting) 또는 저수준 포맷

  • 디스크를 섹터 단위로 나누어 컨트롤러가 읽고 쓸 수 있도록 함
  • 섹터 = 헤더 + 데이터(보통 512B) + 트레일러
  • 여분 섹터 또는 실린더는 bad block 대비용

• 파일 시스템 사용을 위한 논리 포맷(Logical formatting) 필요

  • OS가 파티션을 논리적인 단위로 구분
  • 파티션마다 파일 시스템 구조를 초기화

• 부팅 과정(Power-up)

  • 작은 bootstrap loader는 ROM에서 실행됨
  • 디스크의 부트 블록을 로딩하여 OS를 실행

RAID

• RAID (Redundant Array of Inexpensive Disks)

  • 다수의 디스크를 병렬로 구성하여 고용량 및 고속 제공
  • 신뢰성 향상: 데이터 중복 저장 → 일부 디스크 실패 시에도 복구 가능

• 이점:

  • 하나의 디스크가 고장날 확률 < 여러 디스크 중 일부가 고장날 확률
  • 하지만 RAID는 복구 가능성을 높여 전체 시스템 신뢰성을 향상시킴

• 예시:

  • 100개의 디스크를 가진 시스템
    • 각 디스크 MTTF: 100,000시간
    • 시스템 전체 MTTF는 약 1000시간 (41일)

• 대규모 디스크 시스템에서는 데이터 손실 방지 기술이 필수

Improvement of Reliability via Redundancy

• Redundancy: 디스크 고장 시 손실된 정보를 복구할 수 있는 추가 정보 저장
• 예시: Mirroring (shadowing)
  • 두 개의 물리 디스크에 동일한 논리 디스크 내용을 저장
  • 각 쓰기 작업은 두 디스크 모두에 수행됨
  • 읽기 요청은 어느 디스크에서든 처리 가능
• 장점:
  • 한 디스크가 고장 나더라도 다른 디스크에서 정보 복구 가능
  • 동시 고장 확률이 매우 낮음
• 단점:
  • 디스크 수 증가
• 평균 데이터 손실 시간 = 고장까지의 평균 시간 + 복구 시간
  • MTTF = 100,000시간, 복구 = 10시간 → RAID 1 구성 시 약 5천만 시간

Improvement in Performance via Parallelism

• 디스크 병렬성의 목표:
  1. 부하 분산 → 처리량 증가
  2. 병렬 접근 → 응답 시간 단축
• Bit-level striping
  • 각 바이트의 비트를 여러 디스크에 나눠 저장
  • 읽기 속도는 빠르지만, seek/latency는 단일 디스크보다 나쁠 수 있음
• Block-level striping
  • 블록 단위로 디스크에 분산 저장:
    • 예: 디스크 $k$에 저장 → $(i \mod n) + 1$
  • 연속된 블록 요청 시 여러 디스크에서 동시에 병렬 처리 가능

RAID Levels

• RAID는 디스크 스트라이핑 + 패리티를 통해 저비용으로 중복성 제공
• 다양한 RAID 레벨은 비용, 성능, 신뢰성 측면에서 차이를 보임
• RAID 0: 블록 스트라이핑, 중복 없음
  • 데이터 손실 허용 불가능한 환경에는 적합하지 않음
• RAID 1: 미러링 (복제 디스크)
  • 뛰어난 쓰기 성능 제공
  • 데이터베이스 시스템 등에 적합
• RAID 2: Bit-level striping + ECC 디스크
  • 각 비트 단위로 디스크 분산, ECC로 에러 복구 가능
• RAID 3: Byte-level striping + 패리티 전용 디스크
  • 전체 데이터를 바이트 단위로 나눠 여러 디스크에 저장
  • 패리티는 별도의 디스크에 저장됨
• RAID 4: Block-interleaved parity, block-level striping
  • 모든 디스크에서의 해당 블록들과 XOR하여 패리티 디스크에 저장
  • 패리티 블록은 병렬 쓰기 병목 현상의 원인이 될 수 있음
• RAID 5: Block-interleaved distributed parity, block-level striping
  • 데이터와 패리티를 모든 디스크에 분산 저장
  • 예: 디스크가 5개일 때,
    • $n$번째 블록의 패리티는 $(n \mod 5) + 1$번째 디스크에 저장
    • 나머지 4개 디스크에는 데이터 블록 저장
• 분산 패리티 → 병목 현상 줄임

Choice of RAID Level

• RAID 레벨 선택 시 고려 요소:

  • 비용 (Monetary cost)
  • 성능: 초당 I/O 연산 수, 정상 작동 중 대역폭
  • 장애 발생 시 성능
  • 디스크 복구 시 성능

• RAID 0: 데이터 안전이 중요하지 않을 때만 사용

  • 다른 소스로부터 데이터를 빠르게 복구할 수 있는 경우

• RAID 2, 3: 현재는 사용되지 않음

  • 비트/바이트 단위 striping은 모든 디스크 접근을 강제
  • 디스크 암 이동 낭비 → 블록 단위 striping이 이를 피함 (RAID 4, 5)

• RAID 4: RAID 5에 흡수되어 사용되지 않음

• → 실질적 선택지는 RAID 1 vs RAID 5

• RAID 1: RAID 5보다 훨씬 나은 쓰기 성능

  • RAID 5는 블록 1개 쓰기에도 최소 2개의 읽기 + 2개의 쓰기 필요
  • RAID 1은 블록 2개 쓰기만 필요
  • 로그 디스크 등 업데이트 빈도 높은 환경에 적합

• RAID 1의 단점: 저장 공간 요구량이 RAID 5보다 큼

  • 하지만 디스크 용량은 빠르게 증가 (연간 50%)
  • 디스크 접근 시간은 천천히 감소 (10년간 3배 수준)
  • 웹 서버 등에서 I/O 요구량이 매우 큼
  • 충분한 디스크를 확보해두었다면 여유 용량이 남는 경우도 많음
    → 이 경우 RAID 1도 추가 비용 없이 구성 가능

• RAID 5: 업데이트가 적고 대량의 데이터를 다루는 환경에 적합

• RAID 1: 그 외 모든 상황에 권장됨