secondary storage 보조 저장장치
주기억장치(primary memory) 외부에 있는 저장장치. 명령어를 직접 실행하거나 데이터를 직접 read/write할 수 없으며, 대용량·저가·비휘발성(전원 차단 후에도 데이터 유지)·저속(밀리초 단위 접근)이라는 특성을 가진다.
보조 저장장치 구조 · 디스크 스케줄링 · 현대 디스크
secondary storage는 주기억장치 외부에 위치하며 대용량·비휘발성·저속이라는 특성을 가진다. 대표적인 장치인 HDD는 회전하는 플래터 위를 읽기/쓰기 헤드가 이동하면서 데이터에 접근하며, 접근 시간은 seek time(헤드 이동), rotational latency(섹터 회전 대기), transfer time(데이터 전송)의 세 단계로 구성된다.
현대 디스크는 물리적 주소 대신 logical block address (LBA)를 사용해 디스크 내부 구조를 OS로부터 감춘다. disk scheduling은 헤드 이동 횟수를 줄여 대역폭을 높이기 위한 요청 순서 결정 정책으로, FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK 등이 있다.
OS의 I/O scheduler는 처리량 극대화, 기아(starvation) 방지, 공정성 보장, QoS 요건 충족을 목표로 한다. 한편 SSD·flash· NVM 기반의 현대 디스크는 지능형 컨트롤러를 내장하여 read-ahead, 캐싱, 불량 블록 재매핑 등을 자체적으로 수행한다.
주기억장치(primary memory) 외부에 있는 저장장치. 명령어를 직접 실행하거나 데이터를 직접 read/write할 수 없으며, 대용량·저가·비휘발성(전원 차단 후에도 데이터 유지)·저속(밀리초 단위 접근)이라는 특성을 가진다.
회전하는 자기 플래터와 기계적 암 어셈블리로 구성된 대표적 secondary storage. 디스크 컨트롤러, 버퍼, 호스트 인터페이스 등의 전자 부품도 내장한다.
HDD 내부의 원형 자기 디스크. 여러 장이 스핀들에 쌓여 함께 회전한다. 각 면(surface)마다 읽기/쓰기 헤드가 하나씩 존재한다.
플래터 표면 위의 동심원 하나. 데이터는 트랙에 연속으로 기록된다. 같은 번호의 트랙이 여러 플래터에 걸쳐 수직으로 쌓이면 cylinder를 이룬다.
트랙을 나눈 최소 저장 단위. 디스크 읽기/쓰기는 섹터 단위로 이루어진다. 현대 디스크는 섹터 크기가 균일하지 않을 수 있으며 내부적으로 재매핑된다.
모든 플래터에서 같은 반경에 있는 트랙들의 집합. 헤드를 이동하지 않고 같은 실린더 내 모든 트랙에 접근할 수 있어 I/O 최적화에 중요한 단위가 된다.
플래터 표면을 극히 가까운 거리(수 nm)에서 부유하며 자기 신호를 읽고 쓰는 부품. 헤드는 디스크 암(arm)에 의해 실린더 방향으로 이동하고, 회전은 플래터가 담당한다.
디스크 암을 목표 실린더로 이동하는 데 걸리는 시간. HDD 접근 시간에서 가장 큰 비중을 차지하며 디스크 스케줄링이 이를 줄이기 위해 존재한다.
헤드가 목표 실린더에 도달한 후 원하는 섹터가 헤드 아래까지 회전해 오는 데 걸리는 시간. 7200 RPM 디스크의 경우 최대 회전 지연은 약 8.3 ms이다.
섹터가 헤드 아래를 지나는 동안 데이터를 디스크 컨트롤러로 전송하는 시간. 디스크 밀도에 따라 결정되며 seek time·rotational latency에 비해 빠르다.
디스크가 자신의 데이터를 [0..N-1]의 논리 블록 배열로 외부에 제공하는 방식.
OS는 물리적 cylinder/surface/sector를 알 필요 없이 논리 블록 번호만 지정하면 된다.
디스크 큐에 쌓인 I/O 요청들의 처리 순서를 결정하는 정책. seek time이 매우 비싸기 때문에 헤드 이동 거리를 줄여 디스크 대역폭을 높이기 위해 사용된다.
요청이 들어온 순서대로 처리. 구현이 단순하고 공정하지만 헤드가 불필요하게 왕복할 수 있어 부하가 높을 때 대기 시간이 길어진다.
현재 헤드 위치에서 가장 가까운 요청을 먼저 처리. 암 이동을 최소화하지만 가운데 블록을 편향적으로 선호하여 양 끝 요청이 starvation을 겪을 수 있다.
SCAN(엘리베이터 알고리즘): 한 방향으로 끝까지 이동하며 요청을 처리하고 반전. C-SCAN: 한 방향으로만 서비스 후 반대쪽 끝으로 점프하여 균일한 대기 시간을 제공한다.
SCAN/C-SCAN의 개선판. 디스크 끝까지 이동하지 않고 해당 방향의 마지막 실제 요청 위치에서 반전 또는 점프한다. 불필요한 이동이 줄어든다.
OS 커널 내의 I/O 요청 관리 모듈. 요청을 병합(merge)하거나 재정렬(reorder)하여 처리량을 높이고, 기아(starvation)를 방지하며, 프로세스 간 공정성과 QoS를 보장한다.
기계적 움직임 없이 전기적으로 데이터를 저장하는 현대 저장 장치. 지능형 컨트롤러를 내장하여 read-ahead, 캐싱, 커맨드 큐잉, 불량 블록 재매핑 등을 자율적으로 수행한다.
secondary storage는 주기억장치(CPU가 직접 접근 가능한 RAM) 외부에 위치하는 모든 저장 장치를 말한다. 슬라이드는 다음 네 가지 특성으로 정의한다.
CPU는 secondary storage의 명령어를 직접 실행하거나 데이터를 직접 읽고 쓸 수 없다. 데이터는 반드시 주기억장치로 올린 뒤 사용해야 한다.
HDD는 기계적(mechanical) 부분과 전자적(electronics) 부분으로 구성된다.
디스크 레이아웃 용어
접근 시간 3단계
초기 디스크는 OS가 cylinder 번호, surface 번호, track 번호, sector 번호, 전송 크기 등을 모두 직접 지정해야 했다. 이는 OS가 각 디스크의 모든 물리적 파라미터를 알아야 한다는 의존성을 낳았다.
현대 디스크는 높은 수준의 인터페이스(예: SCSI)를 제공한다.
[0..N-1] 논리 블록(logical block) 배열로 추상화하여 노출한다.OS의 디스크 접근 계층 (슬라이드 Managing Disks (2))
OS의 역할은 디스크의 물리적 복잡함(오류, 불량 블록, seek 실패 등)을 상위 소프트웨어로부터 숨기는 것이다. 저수준 디바이스 드라이버가 실제 디스크 읽기 등을 처리하고, 파일·데이터베이스 등 고수준 추상화가 그 위에 쌓인다.
seek time이 매우 비싸기 때문에 I/O 요청이 들어오면 디스크가 바쁜 경우 큐(queue)에 쌓인다. 큐의 요청 처리 순서를 조정하면 디스크 대역폭을 높일 수 있다.
| 알고리즘 | 핵심 아이디어 | 장점 | 단점 |
|---|---|---|---|
| FCFS | 요청 도착 순서대로 처리 (do nothing) | 구현 단순, 공정 | 부하 시 대기 시간 길어짐 |
| SSTF | 현재 헤드에서 가장 가까운 요청 먼저 처리 | 암 이동 최소화, 처리율 높음 | 가운데 블록 편향, 양 끝 starvation 가능 |
| SCAN | 한 방향 끝까지 이동 후 반전 (엘리베이터) | SSTF보다 공정 | 대기 시간이 위치에 따라 불균일 |
| C-SCAN | 한 방향만 서비스, 끝 도달 시 반대 끝으로 점프 | 균일한 대기 시간 | 끝단 이동·점프 비용 발생 |
| LOOK | SCAN에서 마지막 요청 위치에서 반전 (끝까지 안 감) | 불필요한 끝단 이동 제거 | 대기 시간 위치 의존성 잔존 |
| C-LOOK | C-SCAN에서 마지막 요청 위치에서 최솟값 요청으로 점프 | 균일한 대기 + 불필요 이동 제거 | 구현 약간 복잡 |
알고리즘 선택 기준 (슬라이드 Disk Scheduling)
헤드 이동 계산 예제
요청 큐: [98, 183, 37, 122, 14, 124, 65, 67], 헤드 초기 위치: 53, 디스크 범위: 0–199. SCAN/LOOK 계열은 고번호(high) 방향으로 먼저 출발한다고 가정한다.
| 알고리즘 | 서비스 순서 | 총 이동량 (cylinders) |
|---|---|---|
| FCFS | 53→98→183→37→122→14→124→65→67 | 640 |
| SSTF | 53→65→67→37→14→98→122→124→183 | 236 |
| SCAN | 53→65→67→98→122→124→183→199(끝)→37→14 | 331 |
| C-SCAN | 53→65→67→98→122→124→183→199(끝)→0→14→37 | 382 |
| LOOK | 53→65→67→98→122→124→183(반전)→37→14 | 299 |
| C-LOOK | 53→65→67→98→122→124→183(점프)→14→37 | 322 |
OS 커널의 I/O scheduler는 단순 디스크 스케줄링을 넘어 다음 네 가지 목표를 동시에 추구한다.
현대 디스크(SSD, flash, NVM 포함)는 소형 CPU와 수 킬로바이트의 메모리를 탑재한 지능형 컨트롤러(intelligent controller)를 내장한다. 컨트롤러는 제조사가 작성한 펌웨어(firmware)를 실행하여 다음과 같은 기능을 자율적으로 수행한다.
Q1 HDD의 데이터 접근 시간을 구성하는 세 단계를 각각 설명하고, 이 중 disk scheduling이 주로 개선하고자 하는 단계와 그 이유를 서술하시오.
HDD 접근 시간은 세 단계로 구성된다. ① seek time: 디스크 암을 현재 실린더에서 목표 실린더로 이동하는 시간. 디스크 암의 물리적 이동 속도에 의존하며 세 단계 중 가장 느리다. ② rotational latency: 헤드가 목표 실린더에 도달한 후 원하는 섹터가 헤드 아래로 회전해 오는 대기 시간. 디스크 회전 속도에 의존한다. ③ transfer time: 섹터 데이터를 컨트롤러로 읽어 호스트로 전송하는 시간. 디스크 기록 밀도에 의존하며 세 단계 중 가장 빠르다.
disk scheduling은 주로 seek time을 최소화하기 위해 존재한다. seek가 가장 느리고 비용이 크기 때문에, 큐에 쌓인 요청들의 처리 순서를 조정하여 헤드 이동 총량을 줄이면 디스크 대역폭을 크게 향상시킬 수 있다.
Q2 초기 디스크와 현대 디스크의 주소 지정 방식 차이를 설명하고, LBA(logical block address)가 OS 설계에 미치는 영향을 서술하시오.
초기 디스크는 OS가 cylinder 번호, surface 번호, track 번호, sector 번호, 전송 크기 등 모든 물리적 파라미터를 직접 지정해야 했다. 이는 OS가 각 디스크의 내부 구조를 상세히 알아야 한다는 의존성을 낳았다.
현대 디스크는 SCSI 등의 고수준 인터페이스를 통해 데이터를 [0..N-1] 논리 블록 배열로 추상화한다.
OS는 LBA(논리 블록 주소)만 지정하면 되고, 디스크가 내부적으로 이를 cylinder/surface/sector로 매핑한다.
이를 통해 OS는 물리적 파라미터를 몰라도 되어 코드가 단순해지고, 디스크 제조사가 내부 구조를 자유롭게 변경·최적화할 수 있다.
Q3
다음 조건에서 FCFS, SSTF, SCAN
알고리즘의 총 헤드 이동량을 각각 계산하시오.
요청 큐: [98, 183, 37, 122, 14, 124, 65, 67], 초기 헤드 위치: 53, 디스크 범위: 0–199.
SCAN은 고번호(high) 방향으로 먼저 이동한다고 가정한다.
FCFS (도착 순서: 53→98→183→37→122→14→124→65→67)
45(53→98) + 85(98→183) + 146(183→37) + 85(37→122) + 108(122→14) + 110(14→124) + 59(124→65) + 2(65→67) = 640 cylinders
SSTF (가장 가까운 요청 순서: 53→65→67→37→14→98→122→124→183)
12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 cylinders
SCAN (고번호 방향 출발, 끝 199까지 이동: 53→65→67→98→122→124→183→199→37→14)
12(53→65) + 2(65→67) + 31(67→98) + 24(98→122) + 2(122→124) + 59(124→183) + 16(183→199) + 162(199→37) + 23(37→14) = 331 cylinders
Q4 위 예제(요청 큐: [98,183,37,122,14,124,65,67], 헤드=53, 범위 0–199)에서 C-SCAN과 C-LOOK의 총 헤드 이동량을 계산하고, 두 알고리즘의 차이를 설명하시오.
C-SCAN (고번호 방향, 끝(199)까지 이동 후 0으로 점프: 53→65→67→98→122→124→183→199→0→14→37)
12+2+31+24+2+59+16(183→199)+199(199→0, 점프)+14(0→14)+23(14→37) = 382 cylinders
C-LOOK (마지막 요청(183)에서 최솟값 요청(14)으로 점프: 53→65→67→98→122→124→183→14→37)
12+2+31+24+2+59+169(183→14, 점프)+23(14→37) = 322 cylinders
차이: C-SCAN은 디스크의 물리적 끝(199)까지 이동한 뒤 0으로 점프하므로 끝단까지의 불필요한 이동(183→199: 16)과 전체 점프 비용(199→0: 199)이 포함된다(합계 215). C-LOOK은 마지막 실제 요청 위치(183)에서 최솟값 실제 요청 위치(14)로 점프하여 불필요한 끝단 이동이 없어 총 이동량이 더 적다(382 vs 322).
Q5 SCAN과 LOOK의 차이를 설명하고, 같은 요청 큐(헤드=53, 고번호 방향 출발)에서 두 알고리즘의 총 헤드 이동량을 각각 계산하여 비교하시오.
SCAN은 헤드가 디스크의 물리적 끝(0 또는 N-1)까지 이동한 뒤 반전한다. LOOK은 SCAN과 유사하지만, 해당 방향의 마지막 실제 요청 위치에서 반전하므로 실제 요청이 없는 끝단까지 이동하는 낭비가 없다.
SCAN (53→65→67→98→122→124→183→199→37→14): 12+2+31+24+2+59+16+162+23 = 331 cylinders
LOOK (53→65→67→98→122→124→183→37→14): 12+2+31+24+2+59+146+23 = 299 cylinders
LOOK이 332−299 = 32 cylinders 적게 이동한다(183→199의 불필요한 이동 16 + 이로 인한 추가 반전 이동 차이 16). 슬라이드는 SSTF 또는 LOOK을 기본 알고리즘으로 권장한다.
Q6 OS의 I/O scheduler가 달성해야 할 네 가지 목표를 설명하고, 각 목표를 위해 사용하는 대표적 기법을 서술하시오.
① 처리량(throughput) 향상: 요청 병합(merge)으로 I/O 수를 줄이고, 재정렬(reorder/sort)로 seek time을 감소시킨다.
② 기아(starvation) 방지: 요청에 데드라인(deadline)을 부여하여 해당 시간 이전에 반드시 처리되도록 보장한다.
③ 공정성(fairness): 특정 프로세스가 I/O 자원을 독점하지 않도록 서로 다른 프로세스 간에 자원을 균등하게 배분한다.
④ QoS 보장: 실시간 또는 우선순위 높은 프로세스에 필요한 quality-of-service 요건(응답 시간, 대역폭 등)을 충족시킨다.
Q7 현대 디스크의 지능형 컨트롤러(intelligent controller)가 수행하는 주요 기능을 나열하고, 이것이 OS의 disk scheduling에 미치는 영향을 설명하시오.
현대 디스크 컨트롤러는 소형 CPU와 수 킬로바이트 메모리를 탑재하고 다음 기능을 수행한다.
이로 인해 현대 디스크는 OS가 수행한 스케줄링 순서를 무시하거나 다시 재배열할 수 있다. 디스크 자신이 내부 레이아웃을 가장 잘 알기 때문에 OS보다 더 효율적인 최적화가 가능하다. 따라서 OS 레벨의 disk scheduling은 현대 SSD/NVM 환경에서 그 효과가 제한될 수 있다.
Q8 SSTF의 starvation 문제를 예를 들어 설명하고, 이를 완화할 수 있는 대안 알고리즘과 그 동작 방식을 서술하시오.
SSTF는 항상 현재 헤드에서 가장 가까운 실린더의 요청을 먼저 처리한다. 예를 들어 헤드가 실린더 100 근방을 이동 중이고 요청이 지속적으로 90~110 범위에 들어온다면, 실린더 14나 183의 요청은 가까운 요청들에 밀려 무한정 대기(starvation)할 수 있다. 슬라이드는 SSTF가 가운데 블록을 불공정하게 선호한다(unfairly favors middle blocks)고 명시한다.
이를 완화하는 알고리즘은 SCAN 계열이다. SCAN은 한 방향으로 끝까지 이동하며 모든 요청을 처리하고 반전하기 때문에, 어떤 위치의 요청도 최대 1회 전체 왕복 이내에 서비스된다. 특히 LOOK은 마지막 요청 위치에서 반전하여 불필요한 이동을 줄이면서도 starvation을 방지한다. 슬라이드는 SSTF 또는 LOOK을 기본 알고리즘으로 권장한다.