1. Physical Disk Structure
Disk는 얇은 금속 Platter로 구성되며, 그 위를 Read/Write head가 지나다니며 데이터를 읽고 쓴다.
1.1 디스크 구성 요소
| 구성 요소 | 설명 |
|---|---|
| Platter | 데이터가 기록되는 금속 원판 (양면 사용 가능) |
| Spindle | Platter를 회전시키는 축 |
| Read/Write Head | 각 Platter 표면 위에 위치하여 데이터를 읽고 씀 |
| Track | Platter 표면 위의 동심원 형태의 데이터 경로 |
| Sector | Track을 나눈 최소 단위 영역 |
| Cylinder | 모든 Platter에서 같은 위치에 있는 Track의 집합 |
1.2 디스크 읽기에 필요한 정보
디스크에서 데이터를 읽으려면 다음을 지정해야 한다:
- Cylinder # (어떤 실린더인지)
- Surface # (어떤 표면인지)
- Sector # (어떤 섹터인지)
- Transfer size (전송할 데이터 크기)
- Memory address (데이터를 저장할 메모리 주소)
1.3 Transfer Time 구성
Transfer Time = Seek Time + Rotational Delay + Data Transfer Time
| 구성 요소 | 설명 |
|---|---|
| Seek Time | Head를 원하는 Cylinder로 이동시키는 시간 |
| Rotational Delay (Latency) | 원하는 Sector가 Head 아래로 회전해 올 때까지의 대기 시간 |
| Data Transfer Time | 실제 데이터를 읽거나 쓰는 시간 |
2. Disk Structure (논리적 구조)
- Disk drive는 Logical block의 큰 1차원 배열로 주소가 지정됨
- Logical block은 전송의 최소 단위
- 이 1차원 배열은 Disk의 Sector로 매핑됨
2.1 매핑 순서
- Sector 0: 가장 바깥쪽 Cylinder의 첫 번째 Track의 첫 번째 Sector
- 해당 Track의 나머지 Sector를 순서대로 매핑
- 같은 Cylinder의 나머지 Track을 순서대로 매핑
- 바깥쪽에서 안쪽으로 나머지 Cylinder를 순서대로 매핑
실제 제품마다 매핑 방식은 크게 다를 수 있다.
3. Disk Scheduling
3.1 Access Time의 구성
| 구성 요소 | 설명 |
|---|---|
| Seek time | Head를 원하는 Sector가 있는 Cylinder로 이동시키는 시간 |
| Rotational latency | Disk가 회전하여 원하는 Sector가 Head 아래에 도달하기까지의 추가 대기 시간 |
- Seek time 최소화가 Disk scheduling의 핵심 목표
- Seek time은 Seek distance에 비례
3.2 Disk Bandwidth
Disk Bandwidth = 전송된 총 바이트 수 / (요청 ~ 완료까지의 총 시간)
3.3 Seek Time 모델
Seek Time = a + b * sqrt(d)
a,b: 상수d: 이동해야 할 Cylinder 수 (distance)
4. Disk Scheduling Algorithms
다양한 Disk I/O 요청 스케줄링 알고리즘이 존재한다.
예제 공통 조건
- Cylinder 범위: 0 ~ 199
- Request queue: 98, 183, 37, 122, 14, 124, 65, 67
- 현재 Head 위치: 53
4.1 FCFS (First-Come, First-Served)
- 요청이 들어온 순서대로 처리
- 구현이 가장 단순
- 총 Head 이동량: 640 cylinders
처리 순서: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
이동량 계산:
|53-98| + |98-183| + |183-37| + |37-122| + |122-14| + |14-124| + |124-65| + |65-67|
= 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2
= 640
4.2 SSTF (Shortest Seek Time First)
- 현재 Head 위치에서 Seek time이 가장 짧은 (가장 가까운) 요청을 먼저 처리
- SJF (Shortest Job First) scheduling의 Disk 버전
- 총 Head 이동량: 236 cylinders
특징:
- 성능이 FCFS보다 좋지만, Starvation 발생 가능
- 예측 불가능한 성능 (Unpredictable performance)
- 먼 위치의 요청이 계속 뒤로 밀릴 수 있음
처리 순서: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
4.3 SCAN (Elevator Algorithm)
- Disk arm이 디스크의 한쪽 끝에서 다른 쪽 끝까지 이동하면서 지나가는 요청을 처리
- 끝에 도달하면 방향을 반전하여 반대 방향으로 이동하면서 처리
- 엘리베이터 알고리즘이라고도 불림
- 총 Head 이동량: 208 cylinders
동작 방식:
- 한쪽 방향(예: 증가 방향)으로 이동하면서 모든 요청 처리
- 끝에 도달하면 방향 전환
- 반대 방향으로 이동하면서 나머지 요청 처리
문제점:
- 안쪽 Track은 바깥쪽 Track에 비해 2배 자주 서비스됨
- 대기 시간이 불균등 (Unfair wait time)
4.4 C-SCAN (Circular SCAN)
- SCAN보다 균일한 대기 시간을 제공
- Head가 한쪽 끝에서 다른 쪽 끝까지 이동하면서 요청을 처리
- 끝에 도달하면 요청을 처리하지 않고 즉시 반대쪽 시작점으로 복귀
- Cylinder를 원형 리스트(Circular list)로 취급 (마지막 → 처음으로 연결)
문제점:
- 해당 방향에 더 이상 처리할 요청이 없어도 끝까지 이동
4.5 C-LOOK
- C-SCAN의 개선 버전
- “Look-for-Request before continuing” 방식
- Arm이 각 방향에서 마지막 요청이 있는 위치까지만 이동
- 더 이상 요청이 없으면 즉시 방향을 전환
- 디스크 끝까지 불필요하게 이동하지 않음
4.6 알고리즘 비교 요약
| 알고리즘 | Head 이동량 (예제) | Starvation | 대기 시간 균등성 | 특징 |
|---|---|---|---|---|
| FCFS | 640 | 없음 | 보통 | 가장 단순, 성능 낮음 |
| SSTF | 236 | 있음 | 낮음 | SJF와 유사, 성능 좋으나 불공정 |
| SCAN | 208 | 없음 | 보통 | Elevator 알고리즘, 안쪽 편향 |
| C-SCAN | - | 없음 | 높음 | 균일한 대기 시간 |
| C-LOOK | - | 없음 | 높음 | C-SCAN 개선, 불필요한 이동 제거 |
5. Arm Stickiness Problem
- SCAN, C-SCAN, SSTF 모두 이 문제에 취약
- 하나 또는 소수의 프로세스가 특정 Track에 높은 빈도로 접근하는 경우 발생
- 해당 Track에 대한 요청을 반복하여 디스크 장치 전체를 독점할 수 있음
예시:
요청 큐: 15, 15, 6, 15, 15, 15, 15, 15, 15, 15, ...
-> Track 15에 대한 요청이 계속 들어오면 Track 6의 요청은 처리되지 못함
6. Disk Management
6.1 Physical Formatting (Low-level Formatting)
- 디스크를 Disk controller가 읽고 쓸 수 있는 Sector로 분할
- 각 Sector의 구조:
[ Header | Data (일반적으로 512 Bytes) | Trailer ]
| 영역 | 내용 |
|---|---|
| Header | Sector number |
| Trailer | ECC (Error-Correcting Code) - Controller가 사용 |
| Spare sectors | 각 Cylinder에 Bad block 대체용으로 예약 |
6.2 OS의 디스크 사용 준비
디스크를 파일 저장에 사용하려면 OS가 자체 데이터 구조를 기록해야 한다:
- Partitioning: 디스크를 하나 이상의 Cylinder 그룹으로 분할
- OS는 각 Partition을 독립적인 디스크로 취급
- Logical Formatting (“making a file system”): OS가 사용할 파일 시스템 데이터 구조를 초기화
6.3 부팅 과정 (Power-up)
ROM의 Small Bootstrap Loader
-> Sector 0 (Boot block) 로드
-> Full Bootstrap Loader Program 실행
-> OS를 디스크에서 로드
- ROM에 있는 Small bootstrap loader 실행 (유일한 역할: Boot block 로드)
- Boot disk의 Sector 0 (Boot block) 을 읽어옴
- Boot block에 있는 Full bootstrap loader program 실행
- OS를 디스크에서 메모리로 로드
7. RAID (Redundant Array of Inexpensive/Independent Disks)
RAID는 대량의 디스크를 관리하는 기술로, 단일 디스크처럼 보이는 뷰를 제공한다.
7.1 RAID의 목표
| 목표 | 방법 |
|---|---|
| 높은 용량 & 높은 속도 | 여러 디스크를 병렬로 사용 |
| 높은 신뢰성 | 데이터를 중복 저장하여 디스크 장애 시에도 복구 가능 |
7.2 디스크 고장 확률
- N개의 디스크 중 하나라도 고장날 확률은 단일 디스크 고장 확률보다 훨씬 높음
- 예: 100개 디스크, 각각 MTTF 100,000시간 (약 11년)
- 시스템 MTTF = 1,000시간 (약 41일)
- 대규모 디스크 환경에서는 Redundancy 기법이 필수적
8. Redundancy를 통한 신뢰성 향상
8.1 Mirroring (Shadowing)
- 모든 디스크를 이중화 (Logical disk = 2개의 Physical disk)
- 모든 Write는 양쪽 디스크 모두에 수행
- Read는 어느 쪽이든 가능
- 한쪽 디스크가 고장나도 다른 쪽에서 데이터 접근 가능
데이터 손실 조건:
- 한 디스크가 고장나고, 수리가 완료되기 전에 Mirror 디스크도 고장
- 이 확률은 매우 낮음 (종속적 장애 모드 제외: 화재, 건물 붕괴, 전력 서지 등)
8.2 Mean Time to Data Loss 계산
MTTF = 100,000시간, 평균 수리 시간 = 10시간일 때
Mean Time to Data Loss = 500 x 10^6 시간 (약 57,000년)
(Mirrored pair 기준, 종속적 장애 모드 무시)
9. Parallelism을 통한 성능 향상
9.1 병렬화의 두 가지 목표
- Load balancing: 다수의 작은 접근 요청을 분산하여 Throughput 증가
- 대용량 접근 병렬화: 여러 디스크에 걸쳐 데이터를 분산하여 Response time 감소 (Transfer rate 향상)
9.2 Bit-level Striping
- 각 Byte의 비트를 여러 디스크에 분산
- 예: 8개 디스크 배열에서 각 Byte의 Bit i를 Disk i에 저장
- 각 접근이 단일 디스크의 8배 속도로 데이터를 읽을 수 있음
- 하지만 Seek/Access time은 단일 디스크보다 나쁨
- 현재는 거의 사용되지 않음
9.3 Block-level Striping
- n개의 디스크가 있을 때, 파일의 Block i는 Disk (i mod n) + 1에 저장
- 서로 다른 Block에 대한 요청이 서로 다른 디스크에 있으면 병렬 처리 가능
- 긴 연속 Block 요청 시 모든 디스크를 병렬로 활용 가능
10. RAID Levels
Redundancy를 낮은 비용으로 제공하기 위해 Disk striping과 Parity bit를 조합한 다양한 구성 방식이 있다. 각 RAID level은 비용, 성능, 신뢰성이 서로 다르다.
10.1 RAID Level 0 - Block Striping, Non-redundancy
- Block-level striping만 사용, Redundancy 없음
- 데이터 손실이 크리티컬하지 않은 고성능 애플리케이션에 사용
10.2 RAID Level 1 - Mirrored Disks with Block Striping
- Block striping + 디스크 미러링
- 최고의 Write 성능 제공
- 데이터베이스 시스템의 Log 파일 저장 등에 사용
10.3 RAID Level 2 - Bit-level Striping with ECC Disks
- Bit-level striping + 별도의 ECC (Error-Correcting Code) 디스크
- Data disk와 ECC disk로 구성
- 현재는 거의 사용되지 않음
10.4 RAID Level 3 - Byte-level Striping with Dedicated Parity Disk
- Byte-level striping + 전용 Parity disk 1개
- Data disk 3개 + Parity disk 1개 구성 예시
- 현재는 거의 사용되지 않음
10.5 RAID Level 4 - Block-interleaved Parity
- Block-level striping + 별도 디스크에 Parity block 저장
- N개의 다른 디스크에서 대응하는 Block들의 Parity block을 별도 디스크에 보관
동작:
- 데이터 Block 쓰기 시 대응하는 Parity block도 재계산하여 기록
- 손상된 Block 복구: 나머지 Block들(Parity block 포함)의 XOR 연산으로 값 산출
문제점:
- 모든 Block write가 Parity disk에도 기록되므로 Parity disk가 Bottleneck이 됨
10.6 RAID Level 5 - Block-interleaved Distributed Parity
- Block-level striping + Parity를 모든 N+1개 디스크에 분산
- RAID 4의 Parity bottleneck 문제를 해결
- 예: 5개 디스크에서 n번째 Block 세트의 Parity block은 Disk (n mod 5) + 1에 저장
- 나머지 데이터 Block은 다른 4개 디스크에 저장
분산 Parity 예시 (5개 디스크):
| Disk 0 | Disk 1 | Disk 2 | Disk 3 | Disk 4 |
|---|---|---|---|---|
| P0 | 0 | 1 | 2 | 3 |
| 4 | P1 | 5 | 6 | 7 |
| 8 | 9 | P2 | 10 | 11 |
| 12 | 13 | 14 | P3 | 15 |
| 16 | 17 | 18 | 19 | P4 |
11. RAID Level 선택 기준
11.1 고려 요소
| 요소 | 설명 |
|---|---|
| 비용 (Monetary cost) | 추가 디스크 비용 |
| 정상 운영 시 성능 | IOPS (초당 I/O 수), Bandwidth |
| 장애 시 성능 | 디스크 고장 상태에서의 성능 저하 |
| 복구 시 성능 | 고장 디스크 Rebuild 중 성능 |
11.2 실제 사용 현황
| RAID Level | 현황 | 이유 |
|---|---|---|
| RAID 0 | 데이터 안전이 중요하지 않을 때만 사용 | 다른 소스에서 빠르게 복구 가능한 경우 |
| RAID 2, 3 | 더 이상 사용하지 않음 | Bit/Byte striping은 단일 Block 읽기 시에도 모든 디스크를 접근해야 함 → Disk arm 이동 낭비 |
| RAID 4 | 사용하지 않음 | RAID 5에 의해 완전히 대체됨 |
| RAID 1 | 고빈도 Update 환경에서 선호 | Log disk 등 |
| RAID 5 | 낮은 Update 빈도 + 대용량 데이터에 선호 |
11.3 RAID 1 vs RAID 5 상세 비교
| 비교 항목 | RAID 1 | RAID 5 |
|---|---|---|
| 단일 Block Write | 2번의 Block write | 최소 2번의 Block read + 2번의 Block write |
| Write 성능 | 훨씬 우수 | 상대적으로 느림 |
| 저장 비용 | 높음 (100% 오버헤드) | 낮음 (1/N 오버헤드) |
| 적합한 용도 | 고빈도 Update (Log disk 등) | 낮은 Update + 대용량 데이터 |
현실적 고려:
- 디스크 용량 증가 속도: 매년 약 50%
- 디스크 접근 시간 감소 속도: 10년에 약 3배 (용량 증가보다 훨씬 느림)
- I/O 요구량 크게 증가 (예: Web server)
- 필요한 I/O 성능을 충족하기 위해 구매한 디스크들이 종종 여유 저장 용량을 가짐
- 따라서 RAID 1의 추가 비용이 실질적으로 0인 경우가 많음
12. 핵심 정리
Disk Scheduling 알고리즘 선택 가이드
단순 구현 필요 -> FCFS
최적 Seek time 필요 -> SSTF (but Starvation 주의)
균일한 대기 시간 필요 -> C-SCAN 또는 C-LOOK
실용적 최적 -> C-LOOK (C-SCAN의 불필요한 이동 제거)
RAID 선택 가이드
데이터 안전 불필요 + 최고 성능 -> RAID 0
고빈도 Write + 높은 신뢰성 -> RAID 1
대용량 + 낮은 Update 빈도 -> RAID 5
중요 공식
Transfer Time = Seek Time + Rotational Delay + Data Transfer Time
Seek Time = a + b * sqrt(d) (d: distance in # of cylinders)
Disk Bandwidth = Total Bytes Transferred / Total Time
MTTF(시스템) = MTTF(단일 디스크) / N (N: 디스크 수)