[OS] 디스크 사용 가능한 공간 관리와 디스크 공간 할당 방법 - 17

디스크 사용 가능한 공간 관리와 디스크 공간 할당 방법

디스크의 빈 공간을 OS가 어떻게 추적하는지, 그리고 파일에 디스크 블록을 배분하는 세부 기법들을 다룬다.

💡 핵심: 파일 시스템은 두 가지 문제를 동시에 풀어야 한다 — 어디가 비어 있는가(프리블록 관리), 그리고 그 공간에 파일을 어떻게 나눠 담을 것인가(공간 할당).

1. 디스크의 사용 가능한 공간 관리

디스크에서 비어 있는 블록을 프리블록(Free Block)¹이라고 한다. 파일을 새로 저장하려면 프리블록을 찾아야 하고, 파일을 삭제하면 해당 블록을 다시 프리블록으로 돌려줘야 한다. 이 과정을 OS가 어떻게 관리하느냐에 따라 탐색 속도와 관리 복잡도가 달라진다.

프리블록을 관리하는 대표적인 방법은 네 가지다 — 비트 벡터, 연결 리스트, 그룹핑, 카운팅.

비트 벡터(Bit Vector)

디스크의 각 블록에 1비트를 대응시켜, 0이면 비어 있고 1이면 할당된 상태임을 나타내는 방식이다. 비트 맵(Bit Map)이라고도 부른다. 구조가 단순하고, 연속된 프리블록 여러 개를 한꺼번에 찾는 데 효율적이다. 단점은 사용 중인 블록이 많을수록 원하는 n개의 프리블록을 발견하기까지 탐색 시간이 늘어난다는 점이다.

아래는 블록 0~15까지 있는 디스크에서 일부가 할당된 상태를 비트 벡터로 표현한 것이다.

1블록0

1블록1

0블록2

0블록3

1블록4

0블록5

1블록6

0블록7

1블록8

0블록9

0블록10

1블록11

0블록12

0블록13

1블록14

0블록15

■ 초록(1) = 할당됨  |  점선(0) = 비어 있음

연결 리스트(Linked List)

모든 프리블록을 하나의 연결 리스트²로 연결하는 방식이다. 헤드 포인터가 첫 번째 프리블록을 가리키고, 각 프리블록 안에 다음 프리블록의 주소가 담겨 있다. 빈 공간을 찾으려면 리스트를 순차적으로 탐색해야 하므로, 비트 벡터처럼 다수의 프리블록을 한 번에 파악하기는 어렵다.

블록2

→블록3

→

블록3

→블록5

→

블록5

→블록7

→

블록7

→블록9

→

NULL

그룹핑(Grouping)

연결 리스트 방식의 변형으로, 프리블록 자체를 하나씩 연결하는 대신 첫 번째 프리블록에 n개의 빈 블록 번지를 묶어서 저장하는 방식이다. 처음 n-1개는 실제로 비어 있는 블록 번지고, 마지막 n번째에는 다음 그룹의 첫 번째 블록 번지를 저장한다. 덕분에 한 번의 읽기로 여러 프리블록 주소를 얻을 수 있다는 것이 연결 리스트와의 핵심 차이다.

그룹1 블록
[B5,B7,B9,→그룹2]

→

그룹2 블록
[B12,B13,B15,→그룹3]

→

그룹3 블록
[..., NULL]

카운팅(Counting)

연결 리스트를 더 개선한 방식이다. 프리블록을 하나씩 연결하는 대신, 연속된 프리블록의 시작 번지와 개수를 한 쌍으로 저장한다. 예를 들어 블록 5부터 4개가 연속으로 비어 있다면 (5, 4)로 표현한다. 연속 할당이 자주 일어나는 환경에서 노드 수를 크게 줄일 수 있어 효율적이다.

(블록2, 개수:2)

→

(블록5, 개수:1)

→

(블록7, 개수:3)

→

NULL

방법	핵심 구조	장점	단점
비트 벡터	블록당 1bit 플래그	구현 단순, 연속 블록 탐색 효율적	사용 블록 多 → 탐색 느림
연결 리스트	프리블록 체인	구현 단순	순차 탐색만 가능
그룹핑	블록 번지 묶음 저장	한 번 읽기로 여러 주소 획득	연속 블록 관리는 어려움
카운팅	시작 번지 + 개수 쌍	연속 블록 환경에서 노드 수 절감	비연속 환경에선 이점 감소

2. 디스크 공간 할당 — 블록 단위 할당 세부 기법

연속 할당, 연결 할당, 색인 할당의 기본 개념은 이전 파일 시스템 포스팅에서 다뤘다. 여기서는 불연속 할당 중 블록 단위 할당의 세부 기법에 집중한다. 섹터³ 여러 개를 묶은 블록 단위로 할당하면 포인터 오버헤드⁴를 줄이고 I/O 효율을 높일 수 있다. 구체적인 구현 방식은 블록체인 기법, 색인 블록체인 기법, 블록 지향 파일 사상 기법으로 나뉜다.

블록체인 기법

할당된 블록들을 체인으로 연결하는 방식이다. 연결 할당과 구조가 유사하지만, 섹터 하나씩 연결하던 것을 블록 단위로 키웠기 때문에 포인터 오버헤드가 상대적으로 줄어든다. 다만 여전히 원하는 블록에 바로 접근하려면 첫 번째 블록부터 체인을 따라 순서대로 탐색해야 한다는 한계는 남아 있다.

블록A
→블록C

→

블록C
→블록F

→

블록F
→블록K

→

NULL

색인 블록체인 기법

블록 자체를 연결하는 것이 아니라, 프리블록의 번호만을 모아 별도의 색인 블록(Index Block)에 저장하는 방식이다. 색인 블록에 블록 번지 목록이 모여 있어 원하는 순번의 주소를 바로 꺼낼 수 있으며, 여러 개의 사용 가능한 블록 주소를 효율적으로 탐색할 수 있다. 단, 연속된 프리블록을 관리하기는 어렵다. 이전 포스팅에서 다룬 UNIX i-node의 직접 블록 구조와 같은 원리다.

📋 색인 블록

항목0 → 블록A

항목1 → 블록C

항목2 → 블록F

항목3 → 블록K

→

블록A (데이터)

블록C (데이터)

블록F (데이터)

블록K (데이터)

색인 블록에 번지 목록을 모아두고 항목 번호로 원하는 데이터 블록에 바로 접근한다.

블록 지향 파일 사상 기법

파일과 디스크 블록의 대응 관계를 파일 시스템 수준에서 별도로 관리하는 방식이다. 블록 번호 인덱스를 통해 특정 블록에 직접 접근할 수 있으며, 현대 파일 시스템 설계의 근간이 되는 개념이다. 이전 포스팅에서 다룬 FAT 파일 시스템이 이 방식의 대표적인 구현체다. FAT 테이블은 메모리에 캐시될 수 있어 임의 접근 속도도 개선됐고, 블록 하나가 손상돼도 테이블 자체는 별도로 보존되므로 순수 연결 할당의 연쇄 손상 문제를 해결한다.

FAT 테이블
[A→C, C→F, F→K, K→EOF]

→

블록A

블록C

블록F

블록K

기법	직접 접근	특징
블록체인 기법	❌ 불가	섹터 단위보다 오버헤드 감소, 순차 탐색만 가능
색인 블록체인 기법	✅ 가능	색인 블록으로 번지 직접 조회, i-node 직접 블록과 같은 원리
블록 지향 파일 사상	✅ 가능	FAT 테이블이 대표 구현, 테이블 메모리 캐시로 속도 개선

⚠️ 공통 트레이드오프: 불연속 할당 기반의 세 기법 모두 단편화가 없고 파일 크기 변화에 유연하다. 대신 파일이 불연속 공간에 저장되어 있어 논리적으로 연속적인 검색을 하는 경우 시간이 더 소요된다. 현대 파일 시스템(ext4, NTFS 등)은 불연속 할당을 기반으로 하되, 가능하면 연속 배치를 유도하는 방식으로 이 단점을 보완한다.

📎 용어 설명

1. 프리블록(Free Block) — 디스크에서 아직 어떤 파일에도 할당되지 않아 사용 가능한 상태의 블록
2. 연결 리스트(Linked List) — 각 데이터(노드)가 다음 데이터의 주소(포인터)를 포함해 체인처럼 연결된 자료구조. 헤드 포인터가 첫 번째 노드를 가리키고, 마지막 노드는 NULL을 저장해 끝을 표시한다
3. 섹터(Sector) — 디스크의 물리적인 최소 저장 단위. 일반적으로 512Byte 또는 4KB 크기를 가진다
4. 오버헤드(Overhead) — 실제 목적 외에 부가적으로 소모되는 자원(시간, 공간 등). 여기서는 각 블록마다 다음 주소를 저장하는 포인터가 차지하는 공간을 의미한다

운영체제 파일시스템 디스크 프리블록 비트벡터 블록체인 색인블록 FAT