파처 ch6) Organizing Files for Performance

삭제된 공간을 재활용

 

Data Compression (데이터 압축)

1. 파일 사이즈가 작아짐

  (1) 더 적은 공간을 사용해서 cost saving이 된다

  (2) 접근 시간이 줄어들고 빠르게 전송 가능

  (3) 순차적으로 빠르게 접근 가능

 

2. 단점은 별도의 인코딩, 디코딩 작업이 필요함

 

1. Using a Differnt Notation

1. 압축 기법의 하나로, 더 간결한 표기를 찾아 비트 수를 줄이는 방식

  (중복 제거(redundancy reduction)에 해당하는 압축 방식)

 

ex) state : 2bytes -> 6bits 사용

 

50개의 데이터

'L''A' -> 0

'N''Y' -> 1

...

'C''Y' -> 49

는 2^6 = 64개의 조합으로 모든 주를 표현 가능

 

2. Suppressing Repeating Sequences

1. Run-length encoding

  (1) 같은 값이 연속해서 반복되는 데이터를 압축하는 방식

     -> 반복 구간을 축약하여 저장

 

  (2) 작동 방식

       1) 픽셀 값을 순서대로 복사(단, 반복되는 값은 제외)

       2) 반복되는 값이 있다면 아래 세 바이트로 대체 :

              - 0xff : 반복이 시작됨을 알리는 특수 코드

              - 반복되는 값 자체

              - 그 값이 반복된 횟수 (최대 256)

 

3. Assigning Variable-length Codes (가변 길이 부호화)

1. Morse Code (모스 부호)

  -점(.)과 대시(-)의 조합으로 알파벳을 표현

  

2. Huffman Code (허프만 부호)

  - 자주 등장하는 문자는 짧은 이진 코드로, 덜 등장하는 문자는 긴 이진 코드로 인코딩

  - 결과적으로 전체 데이터의 평균 비트 수를 최소화

 

 

4. Others

1. Irrecversible compression

 

2. Compression in UNIX

  - pack and unpack (*.z)

  - compress and uncompress (*.Z)

  - gzip and gnuzip (*.gz)

 

Reclaming Space in Files (공간 회수)

1. Record Deletion and Storage Compaction

 

1. Storgae Compaction

  - 파일 크기를 줄이는 작업

  - 일반적으로 레코드를 삭제 후에 수행

  - 삭제된 레코드로 생긴 공간의 낭비를 제거

 

방법 :

  1. 간단한 방법

       (1) 삭제된 레코드를 건너뛰며 새 파일로 복사하는 방식

       (2) 빠르고 단순함 (공간 여유 필요)

 

  2. 복잡한 방법

        (1) 파일 내부에서 직접 압축 (in-place compaction)

        (2) 더 많은 시간과 관리 복잡도 요구

 

주기적으로 삭제된 레코드로 생긴 공간을 회수함

 

-> 삭제된 공간을 *로 마킹을 함

 

2. Deleting Fixed-Length Record

1. 작동 방식

  - 레코드 삭제 시, 특별한 방법으로 삭제 표시함

  - 재사용 시, 파일을 처음부터 한 레코드씩 탐색해서 삭제된 레코드를 사용

2. 문제점

  - 삭제된 레코드를 찾기 위해 전체 파일을 순차 탐색해야 함 (오래 걸림)

3. 개선 방안

  - Linked List로 삭제된 파일을 관리해 바로 접근이 가능하게 설계

 

-> head에는 최근에 들어온 노드의 번호를 저장 ( 최근에 들어온 노드는 이전에 헤드였던 노드 값을 넣어줌)

 

구성 방식 :

 (1) RRN (Relative Record Number) 사용

    -> 다음 삭제 레코드 위치를 가리킴 (첫 번째 삭제 레코드는 파일 헤더에 저장)

 (2) 삭제된 레코드는 '*' 등 특수문자로 삭제 표시 (이어서 다음 삭제 레코드의 RRN 저장)

 

삭제된 레코드 재사용 방법 :

  (1) 헤더에 있는 첫 번째 삭제 레코드의 RRN을 읽음

  (2) 그 위치에 새 레코드를 저장

  (3) 헤더의 RRN을 업데이트 -> 다음삭제 레코드를 새로운 리스트 헤드로 설정

 

3. Deleting Variable-Length Record

1. 어려운 점

  (1) 가변 길이는 고정 길이보다 삭제 및 관리가 더 복잡

  (2) RRN를 사용할 수 없기 때문에, "바이트 오프셋"으로 연결해야 함

 

2. 삭제된 레코드를 재사용하려면 ?

  (1) 삭제된 공간의 크기가 새로 추가할 레코드를 담을 만큼 충분히 커야 함

  (2) 공간 부족 : 맞는 크기가 없으면 파일 끝에 새 레코드 추가

 

3. 리스트 레코드에 추가와 삭제하는 방법 ?

   (1) 삭제 시 : 해당 레코드에 *와 다음 available 레코드의 오프셋 저장 -> 헤더 갱신

   (2) 추가 시 : 첫 available 오프셋에서 삽입 후, 링크 업데이트

 

 

-> 삭제되는 노드의 위치를 head에 저장

4. Storgae Fragmentation

1. internal fragmentation : 레코드 내부에 낭비되는 공간

(a) 각 레코드는 64바이트 고정 ( 내용이 짧으면 남은 공간은 공백으로 낭비)

   -> 이 낭비된 공간이 internal fragmentation

 

(b) 앞 숫자는 각 레코드의 총 길이(byte 수)를 나타냄 (실제 내용에 맞게 저장 -> 남는 공간 없음)

   -> 내부 단편화 없음, 저장 공간 절약

가변길이 레코드의 fagmentation 설명

(a) 레코드 삭제 후

 - 두 번째 레코드(64바이트)가 삭제됨

 - HEAD.FIRST_AVAIL = 43

  -> 현재 재사용 가능한 첫 번째 빈 공간의 오프셋

 

(b) 삭제된 공간에 새로운 레코드 추가

  -> 이 레코드는 삭제된 64바이트 공간에 정확히 들어감

  - HEAD.FIRST_AVAIL = -1 (현재 사용 가능한 삭제 공간이 없음)

 

 

내부 단편화 없이 공간을 재활용하되, 삭제된 슬롯에서 남은 공간은 avil list에 등록해 낭비 없이 관리

(a) Ham 레코드 삽입 후

 - 기존 삭제 공간 : 35바이트 (Ham 레코드 : 27바이트)

 - 남은 8바이트 공간은 여전히 avail list에 등록됨

 - HEAD.FIRST_AVAIL = 43 -> 8바이트 빈 공간의 시작 위치 

(내부 단편화 없음-공간 재활용 + 남은 공간 추적)

 

(b) Lee 레코드 삽입 후

 - Lee 레코드 : 25바이트 (8바이트 공간을 먼저 소모)

 - 이후 27바이트 공간에서 25바이트만 사용

 - 남은 2바이트는 너무 작아서 재사용 불가능

=> 이처럼 생긴 작고 쓸 수 없는 공간이 외부 단편화

 

 

2. external fragmentation : 빈 공간이 존재하지만, 이 공간이 너무 작아서 새로운 데이터를 저장할 수 없는 상황

해결방법

(1) storage compaction (압축)

 - 외부 단편화가 심각할 경우, 파일 전체를 재구성하여 빈 공간을 한쪽으로 몰아주는 방식

 - 단점 :처리 비용이 큼(많은 복수 및 재배치 필요)

 

(2) coalescing (인접 공간 병합)

 - avail list에 있는 서로 인접한 빈 슬롯들을 합쳐 더 큰 하나의 슬롯으로 만듦

 

(3) placement strategy (배치 전략)

 - 처음부터 단편화가 생기지 않도록 적절한 위치를 골라 삽입

 

5. Placement Strategies

1. first-fit (최초 적합)

 - avail list에서 처음으로 맞는 공간을 바로 선택

 - 빠르지만, 단편화 관리에는 비효율적일 수 있음

 

2. best-fit (최적 적합)

 - 가장 작은 적절한 공간을 찾기 위해 avail list를 크기 오름차순으로 정렬

 - 삭제된 공간을 다시 넣을 때도 리스트 정렬 유지 필요

단점 : 

 - 외부 단편화 발생 가능 (공간이 쪼개져 작은 조각들만 남는 경우가 많음)

 - 리스트 검색 시간 증가 ( 오래될수록 리스트가 커지고 검색도 느려짐)

 

3. worst-fit (최악 적합)

 - 가장 큰 공간을 항상 선택 (avail list를 크기 내림차순으로 정렬)

장점 :

 - 공간을 크게 쪼갤 수 있어 작은 조각(단편화)를 줄임

 - 삭제 리스트 관리가 간단함 (항상 앞에서 가져오면 되기 때문에 정렬은 유지되나 검색은 간단)