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)에 따른 페이지 프레임 수와 페이지 부재율과의 관계

16 프레임 할당2

2) 정적 할당(static allocation): 균등 할당, 비례 할당
  (1-1) 균등 할당(Equal allocation)
    * 가용한 프레임을 모든 프로세스에 균등하게 할당하는 방법
      예1) 프레임: 120 이고 프로세스: 3개 (P1, P2, P3)
           P1: 40개, P2: 40개, P3: 40개
      예2) 프레임: 120 이고 프로세스: 4개 (P1, P2, P3, P4)
           P1: 30개, P2: 30개, P3: 30개, P4: 30개
    * 문제점: 각 프로세스마다 메모리 요구량이 다르기 때문에 프로세스에 따라서 프레임 낭비 또는 빈번한 페이지 부재가 발생한다.
      예) 알씨: 약 90 Mb / 카카오톡: 약 50 Mb / MS-Word: 약 500 Mb
          카카오톡은 메모리 낭비가 있고 MS-Word에서는 페이지 부재 빈도가 증가한다.

  (1-2) 비례 할당(Proportional allocation)
    * 균등 할당의 문제를 해결하기 위해 프로세스의 크기에 비례하여 메모리 프레임을 할당한다.
     예) 가용 프레임: 120개
        프로세스 크기: 알씨: 약 90 Mb / 카카오톡: 약 50 Mb / MS-World: 약 500 Mb
          알씨 => 120 * 90 / (90 + 50 + 500) = 17개
         카카오톡 => 120 * 50 / (90 + 50 + 500) = 9개
         MS-Word => 120 * 500 / (90 + 50 + 500) = 94개
    * 문제점 : 요구 페이징에서 처럼 프로세스의 모든 페이지가 다 메모리에 적재될 필요는 없다. 즉, 카카오톡 프로세스는 작은 프로그램이기 때문에 모든 페이지가 다 적재될 필요가 있을 수 있지만 MS-Word는 해당 프로세스의 많은 부분이 지금 당장 필요하지 않은 페이지들이다. 즉, 동적인 요구를 반영하고 있지 못하다.

16 프레임 할당1

1) 쓰레싱(Thrashing)이란?
  * CPU utilization (CPU 이용율)
    : CPU가 쉬지 않고 얼마나 잘 활용되었는가!
  * degree of multiprogramming(number of processes)
    : 멀티 프로그래밍의 정도. 즉,수행중인 프로세스의 수
  * 쓰레싱(hrashing)
    : 프로세스가 1개이거나 수가 적으면 I/O 처리가 있을 때마다 CPU는 대기 상태가되어 이용률이 낮아진다. 그러나 프로세스가 많아 질 수록 CPU 대기 시간이 줄어들고 이용률이 증가하게 된다.
    : 그러나 프로세스의 수가 어느 정도 증가하고 나면 CPU 이용률이 급격하게 감소하는 현상이 발생한다. 이를 쓰레싱(Thrashing)이라고 한다.
    :쓰레싱의 원인은 프로세스가 많아 질 수록 메모리에 빈 프레임이 줄어들게 되고 따라서 페이지 교체의 빈도가 증가하게 되기 때문이다. 페이지 교체로 인한 I/O처리로 인해 CPU의 대기 시간이 증가하는 것이다. (동시에 많은 프로그램을 실행하면 컴퓨터가 늦어지는 이유중의 하나이기도 하다.)

  * 쓰레싱 현상을 최대한 감소 시켜야 시스템의 성능을 높일 수 있다.
  * 쓰레싱을 줄이는 방법은?
    (1) Local Repleacement(지역 교체)를 한다.각 프로세스에 할당된 프레임의 수가 변동이 없게 되며, 다른 프로세스에 의해 영향을 받지 않는다. 즉, 다른 프로세스의 쓰레싱에 영향을 받지 않게 된다.
    (2) 프로세스에게 적당한 수의 프레임을 할당해 준다. 페이지 교체는 결국 프레임의 부족해서 발생하는 것이기 때문이다. 단, 문제는 어느 정도가 적당한가? 이것이 문제이다.

  * 프레임 할당이란?
   : 메모리를 프로세스에게 어떻게 분배할 것인가? 즉, 프레임을 어떻게 할당할 것인가?
   : 프레임은 프로세스의 페이지 크기와 같은 크기로 메인 메모리를 나눈 단위이다.
   : 프로세스에게 너무 적은 프레임이 할당되면 페이지 부재가 빈번하게 발생한다.
   : 프로세스에게 과한 프레임이 할당되면 페이지 부재는 적지만 메모리 낭비를 초래한다.

  * 프레임 할당 알고리즘
   (1) 정적 할당(static allocation)
      1-1) 균등 할당(Equal allocation)
      1-2) 비례 할당(Proportional allocation)
   (2) 동적 할당(dynamic allocation)
      2-1) 작업 집합 모델(Working set model)
       2-2) 페이지 부재 빈도(Page fault frequency)

15 가상 메모리4

4) 페이지 교체 알고리즘

  * 예시)
   : 페이지 참조열 = 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
   : 프레임의 수 = 3

4-1) First-In-First-Out (FIFO) Algorithm
  * 메인 메모리에 제일 먼저 올라온 페이지를 Victim(희생양)으로 결정
  * 초기화 코드는 재사용되지 않을 것이라는 전제

  * Page Fault (페이지 부재) : 15회 발생
  * 이상 현상: Belady's Anomaly
      할당되는 프레임의 수가 증가해도 페이지 부재율이 증가하는 현상.

4-2) Optimal Algorithm
  * 앞으로 제일 사용이 늦게될 페이지를 Victim(희생양)으로 결정
  * 앞으로 한참동안 사용이 되지 않는 페이지는 제일 불필요할 것이다.

  * Page Fault (페이지 부재) : 9회 발생
  * 문제점: 미래에 어떤 페이지가 사용될 지 알 수 없다.


4-3) Least Recently Used (LRU) Algorithm
  * 가장 최근에 사용되지 않았던 페이지를 Victim(희생양)으로 결정
  * 통계적으로 최근에 사용되지 않았던 페이지는 앞으로도 사용되지 않을 가능성이 높다.

  * Page Fault (페이지 부재) : 12회 발생

5) 페이지 교체 알고리즘의 비교

6) Global vs Local Replacement
  * Global Replacement
    : 페이지 교체의 대상이 메인 메모리에 있는 모든 페이지를 대상으로 한다.
    : 다른 프로세스의 영향을 받게 되게 된다. 프로세스의 실행이 늦어지거나 빨라질 수 있다.
    : 개별 프로세스의 동작 보다는 시스템 전반의 효율에 중점을 두기 때문에 대형 시스템에서 이용된다.

  * Local Replacement
    : 페이지 교체의 대상이 동일 프로세스의 페이지만 대상으로 한다.
    : 각 프로세스에 할당된 프레임의 수는 변하지 않으며, 프로세스의 상대적인 중요도에 따라 메모리 할당을 조정, 성능개선을 할 수 있다.