18. 파일 할당4

4) 색인 할당(Indexed Allocation)
  * 파일 1개당 1개의 인덱스 블럭을 지정한다.
  * 인덱스 블럭에 해당 파일에 대한 포인터 정보를 저장해 놓는다.
  * 디렉토리는 인덱스 블럭을 가리키고 있는다.
    (연결 할당에서는 최초 위치의 블럭을 가리키고 있음)
  * Unix, Linux 등에서 사용하고 있다.

  * 장점
   : 순차 접근(sequential access)이 가능하다.
   : 직접 접근(Direct access)이 가능하다.
   : 외부 단편화가 없다.

 * 단점
  : 파일 마다 인덱스 블록을 할당해야 하기 때문에 부수적 저장공간의 손실이 있다.
   1 byte 파일 저장하기 위해
    => 데이터 블록 1개 + 인덱스 블록 1개가 필요하다. 즉, 내부 단편화가 크다.

 * 파일의 최대 크기
   : 만약 1 block이 512 byte 이고 인덱스 1개가 4 byte 라면
     512 / 4 = 128개의 인덱스를 가질 수 있다.
    그렇다면 최대 파일 사이즈는 128 X 512 = 64 KB 가 된다.
   : 해결 방법: Linked, Multilevel index, Combined 등으로 인덱스 블럭을 다수개 두고 서로 연결 지어 놓는다.

18. 파일 할당3

2) 연결 할당(Linked Allocation)

  * 파일 => 데이터가 저장된 블럭들의 연결된 집함
  * 파일 디렉토리(directory)는 제일 처음(시작) 블록만 가리킨다.
   그리고 각 블록들은 다음 블럭의 위치(포인터)를 가지고 있다.

  * 장점
   : 새로운 파일 생성시 비어있는 임의의 블록을 첫 블록으로 결정한다.
   : 파일이 커지면 다른 블록을 할당하고 연결을 지어준다.
   : 따라서 외부 단편화가 없다.

  * 단점
   : 순차 접근(sequential access)만 가능하고 직접 접근(Direct access)은 불가하다.
   : 포인터 저장을 위해 4바이트 이상 손실이 있다.
   : 낮은 신뢰성 - 중간 블럭에 bad sector가 발생하여 포인터가 끊어지면 그 이하는 접근이 불가능 하다.
   : 느린 속도 - 디스크 헤더가 블럭들을 읽기 위해 많이 움직여야 한다.

 * FAT 시스템
   : MS사에서 연결할당을 응용하여 속도가 느리고 낮은 신뢰성을 보안하여 자체적으로개발한 파일 시스템이다.
   : MS-DOS, OS/2, Windows 등에서 사용
   : FAT = File Allocation Table
     즉, 파일의 pointer를 모아둔 테이블
   : 포인터들만 모은 테이블 (FAT) 을 별도 블록에 저장
   : 직접 접근(Direct access)이 가능하다.
     FAT의 포인터를 찾아서 해당 디스크위치로 해드를 이동해서 원하는 데이터를 읽는다.
   : FAT은 일반적으로 메모리 캐싱 즉, 부팅시에 FAT이 메모리에 로드된다.
    따라서 FAT을 읽는 속도는 빠르고 수시로 업데이트된다.
   : FAT 내용만 있으면 중간에 bad sector가 있어도 다 읽을 수 있습니다.
   : FAT이 소실될 것을 대비하여  FAT 복사 본을 따로 저장해 둔다.
     즉, 기본적으로 FAT은  2개 이다.
   : 파일을 디스크에서 읽는 속도는 느릴 수 밖에 없다. 그러나 외부 단편화는 해결된다.
   : FAT 을 위해 어느 정도 공간을 할당하느냐에 따라 FAT 12, FAT 16, FAT 32 로 구분

18. 파일 할당2

1) 연속 할당(Contiguous Allocation)

  * 각 파일에 대해 디스크 상의 연속된 블록을 할당
   즉, 같은 파일은 연속된 블럭에 저장이 되어진다.
  * 옛날 IBM 에서 사용

  * 장점
   : 디스크 헤더의 이동 최소화 = 빠른 i/o 성능
   : 동영상, 음악, VOD 등에 적합
   : 순차 접근 즉, 순서적으로 읽을 수 있음 (Sequential access)
   : 직접 접근 즉, 특정 부분을 바로 읽을 수 있음(Direct access)
     순서적으로 저장되어져 있기 때문에 바로 원하는 위치에 접근이 가능하다는 의미임.

 * 단점
   : First-fit, Best-fit, Worst-fit 문제 발생
   : 외부 단편화가 심하다. 사용할 수 없이 버려지는 공간이 많아지게 된다.
   : 압축(compaction) 가능하지만 시간이 오래 걸림(초창기 MS-Dos)
   : 파일의 사이즈가 계속 커질 경우 처리하기 어렵다.

 참고) 이러한 단점 때문에 대안으로 연결 할당 출현.

18. 파일 할당1

1) 파일 시스템 개요

 * 1 sector size = 512 bytes
 * cluster : 여러 개의 섹터(sector, 하드디스크의 물리적 최소 단위)를 묶은 단위
 * cluster = block
 * 1 block size
   : 보통 4 KB (= 8 sectors) : 디스크에 블럭 단위로 읽기/쓰기 실행함.
   : 4 MB (4,096 KB) File 저장 => 1,024개의 Block 사용
   : block device 의 특징 - sector 단위로 처리하면 너무 작아서 읽고/쓰기 어려움
                             - block 단위로 처리하면 저장 공간의 손실이 발생한다.
                             - 아래 이미지 => 1 byte 저장을 위해 1 block = 4 KB 디스크 할당

참고) NTFS에서는 700 byte 이하 작은 파일은 MFT(Master File Table) 엔트리에 직접 저장해서 디스크 할당이 0 byte가 된다. 700 byte 초과 부터 블럭(클러스터)을 할당한다.

 * Disk = pool of free blocks
 * directory

   파일 속성(File Attribute)
    < 보이는 정보 >
    - 파일 이름 : 사용자들이 이해할 수 있는 형태로 붙여짐.
    - 파일 타입 : 다양한 파일 형식을 지원하는 시스템의 경우 필요함.
    - 파일 크기 : 파일의 크기
    - 파일 소유자 : 파일에 대한 읽기, 쓰기, 실행 권한(액세스)의 제어
    - 저장 위치 : 파일이 저장된 장치
    - 생성 날짜 : 파일이 만들어진 일시
   < 보이지 않는 정보 >
    - 시작 블록 번호: 파일이 저장된 블럭들의 시작 블럭 번호

17. 페이지 크기

* 가상 메모리의 요구 페이징에서 페이지 크기는 어느 정도가 적당한가?
  : 명확히 정해진 크기가 있지는 않다. 즉, 꼭 커야 좋다거나 작아야 좋다는 결론을 얻을 수는 없다.

  : 그러나 하나의 프로세스 크기가 점차 커지고 있기 때문에 오늘날 페이지 크기도 점차 크게 설정하는 경향이 있다. 즉, 프로세스가 커지면 페이지도 커지게 된다.
  : 512 byte, 1 Kb, 2 Kb, 4Kb → 4MB, 16 MB

 * 페이지 크기를 결정하는 기준
   : 내부 단편화(Internal Fragmentation)
   : Page-in, page-out 시간 - I/O Overhead
   : 페이지 테이블(Page Table) 크기
   : 메모리 해상도(Memory resolution) - 필요한 내용만 메모리에 담을 수 있는 정도
   : 페이지 부재(Page fault) 발생 확률

 * 페이지 크기가 작을 수록 좋은 기준
   : 내부 단편화
     - 페이지가 작을 수록 버려지는 메모리의 내부 공간(내부 단편화)도 작아진다.
   : 메모리 해상도
     - 페이지가 크면 불필요한 영역까지 함께 적재될 수 밖에 없다. 반대로 적을 수록 필요한 부분만 메모리에 적재되는 정밀도가 증가한다.

 * 페이지크기가 클 수록 좋은 기준
   : Page-in, Page-out 시간
     - I/O 시간은 대부분 디스크의 해드 이동시간이다. 페이지가 클 수록 한 번 이동해서 많은 데이타를 읽어 올 수 있는 장점이 있다.
   : Page Table Size
     - 페이지가 클 수록 페이지 테이블의 열수는 적게 된다.
   : Page Fault 발생 확률
     - 페이지가 클 수록 하나의 페이지 내에 많은 내용을 담고 있기 때문에 페이지 재사용 가능성이 높게 되고 메모리 국지성에 의해 페이지 부재도 덜 발생하게 된다.


* 페이지 테이블(Page Table)
  : 페이지 테이블은 뭘로 만들 것인가?
    - CPU의 레지스터로 구현한다면, 너무 비싸다
    - Memory내에 둔다면 너무 느려진다.
    - 따라서 별도의 Chip(TLB: translation look a side buffer)으로 만든다.


  : 따라서 페이지 테이블은 별도의 chip(TLB 캐시)으로 제작되었다.
  : 그러나 오늘날 반도체 기술의 발달로 CPU 내에 함께 내장되어져 있다.

16 프레임 할당4

 (2-2) 페이지 부재 빈도(PFF: pAGE Fault Frequency)
      * 각 프로세스에 대해 페이지 부재(Page Fault)가 발생할 때 마다 기록을 한다.
      * 페이지 부재율의 상한선과 하한선을 설정하고
       : 페이지 부재율이 상한선을 초과하면
           - 프레임 할당이 너무 적다는 것을 의미하므로 프레임을 추가하여 늘려준다.
       : 페이지 부재율이 하산선아래로 내려가면
         - 프레임 할당이 너무 많아서 메모리가 낭비되고 있다는 것이므로 프레임을 회수하여 줄여준다.

      * 페이지 부재(Page Fault)가 적당한 기준범위내에서 발생하도록 유지한다.

16 프레임 할당3

3) 동적 할당(dynamic allocation)
  * 프레임을 동적으로 요구되는 수 혹은 적당량 만큼 할당하는 방법

   (2-1) 작업 집합 모델(Working set model)
    * 가장 최근에 참조된 프레임은 이후에 또 참조될 가능성이 높다는 가정에서 출발한다. 이는 메모리의 지역성(국지성, Locality)에 기반한다. 따라서 가장 최근에 참조된 페이지 집합을 작업 집합(Working set)이라고 한다.
    * 최근에 참조된 페이지들(작업 집합)을 메인 메모리에 유지시켜 프로세스가 빠르게 실행될 수 있도록 하는 것이 작업 집합 모델이다.

    * 작업 집합 모델에서는 작업 설정 크기(WSS, Working Set Size)의 결정이 중요하다.
      : WSS는 과거 어느 시간까지를 그 범위로 할 것인가에 따라 달라지게 된다. 그 범위값을 델타(∆ or Working Set Window)라고 한다.
      : 시간에 따라 WSS는 그 크기가 급격히 변화하기도 한다.

    

      * 작업 설정 크기(WSS)에 따른 페이지 프레임 수와 페이지 부재율과의 관계