#복습

CPU utilization(사용량) = running time(CPU 동작시간)/running time + idle time(전체 동작시간)

thru-put: 단위시간 당 처리한 프로세스 수 = process의 갯수/총 시간

response time: 일을 시작해서 결과가 다 나올 때까지 시간(응답시간) 대기시간 포함

mean response time = Σresponse time(총 응답시간)/process의 갯수

waiting time: 레디 큐에서 소비한 시간

turn around time = 종료시간 – 도착시간 -> I/O까지 고려한 시간

메모리 관리 전략

  • 지속적인 메모리 할당
  • 페이징
  • 세그먼테이션

운영체제의 중요한 역할 중 하나

  • 운영체제와 유저 프로세스를 지키기 위해서
  • 베이스 레지스터(base register): 가장 작은 legal 물리 메모리 주소
  • 리미트 레지스터(limit register): 범위의 크기(size of the range)
    • 만약 어떤 프로세스가 주소 100에서 150까지에 할당되어 있다면 베이스 레지스터는 100, 리미트 레지스터는 50이 된다.
  • CPU 주소가 베이스 레지스터보다 작거나, 베이스 + 리미트 레지스터보다 크거나 같으면(허용되지 않거나 다른 프로그램, 운영체제에 접근하면) 운영체제 모니터에 (addressing error) 트랩이 발생한다.

주소 바인딩

  • 컴파일 시간(컴파일러 또는 어셈블러)
    • 주소가 확실하게 정해질 수 있다면 이 때 정해준다. 또는 relocatable 주소로 바꿔준다.
    • 시작 주소가 바뀌게 되면 리컴파일 해주어야 한다.
  • 로드 시간(다른 오브젝트 모듈들과 시스템 라이브러리 링크 에디터, 로더)
    • 컴파일 시간에 정해지지 않은 주소를 정해준다.
  • 실행 시간(동적으로 불러온 시스템 라이브러리 메모리 바이너리 이미지)에 일어난다.
    • 주소 맵핑에 하드웨어 지원(베이즈, 리미트 레지스터)이 필요하다.

논리적 주소(Logical address) 또는 가상 주소(Virtual Address)

CPU에 의해 생성된 주소

물리적 주소(Physical address)

메모리 유닛에 의해 보여진(seen) 주소(메모리 주소 레지스터에 불러오는 주소)

** 컴파일 시간과 로드 시간 주소 바인딩에서 논리적 주소와 물리적 주소는 같지만, 실행 시간 바인딩에서 달라진다. **

MMU(Memory Management Unit)

  • 가상 주소를 물리 주소로 매핑하는 하드웨어 장치
  • MMU 체계에서, 재배치(relocation) 레지스터의 값이 메모리에 전송될 때, 유저 프로세스에 의해 생성된 모든 주소에 값을 더해준다.
    • 논리적 주소가 100, 재배치 레지스터가 20이라면 물리적 주소는 120이 된다.
  • 유저 프로그램은 논리적 주소를 다룬다. 실제 주소를 바로 참조하지 않는다.

동적 로딩(Dynamic Loading)

  • 루틴은 호출될때까지 로드되지 않는다.
  • 더 나은 메모리 공간 최적화
    • 사용되지 않은 루틴은 절대 로드되지 않는다.
  • 대용량 소스 코드가 자주 발행하지 않는 케이스들을 다룰 때 유용하다.
  • 운영체제로부터 틀별한 지원이 필요하지 않다.
    • 프로그램 디자인으로 implement 되었다.

동적 링킹(Dynamic Linking)

  • 링킹은 다음 실행 시간까지 연기된다.
  • 소규모 소스 코드(stub)이 적절한 메모리를 위치시키는(locate)데 사용된다. - resident library routine
  • Stub은 자기 자신을 루틴의 주소로 변경하고, 루틴을 실행한다.
  • 운영체제는 루틴이 프로세스의 메모리 공간에 있는지 체크해야 한다.
  • 동적 링킹은 특히 라이브러리에 유용하다.
    • 공유 라이브러리

스와핑(Swapping)

  • 일시적으로 메모리 밖의 backing store로 스와핑되고, 실행의 지속을 위해 메모리 안으로 다시 돌아올 수 있는 프로세스
  • 스와핑의 주요한 부분은 transfer time이다.
    • 총 전송 시간(total transfer time)은 스왑된 메모리 양과 정비례한다.

메모리 할당 체계

연속적인 메모리 할당(Continuous Memory allocation)

  • 다분할 할당(Multiple partition allocation)
    • 홀(Hole)
      • 사용 가능한 메모리의 블록
      • 다양한 크기의 홀이 메모리 공간에 흩어져 있다.
  • 프로세스가 도착하면, 그것을 수용할 수 있을 만큼 큰 홀로부터 메모리를 할당받는다.
  • 운영체제는 “할당된 파티션(Allocated partitions)”과 “빈 파티션(Free partitions)”에 대한 정보를 유지한다.

빈 홀 목록에서 어떻게 n 크기의 요청을 만족시키는가?

  • First-fit
    • 크기가 충분한 첫번째 홀을 할당해준다.
  • Best-fit
    • 크기가 충분한 홀 중 가장 작은 홀을 할당해준다.
    • 전체 리스트를 탐색해야 되거나, 크기로 정렬해야 한다.
    • 가장 작은 남은(leftover) 홀을 생성한다.
  • Worst-fit
    • 가장 큰 홀을 할당해준다.
    • 전체 리스트를 탐색해야 되거나, 크기로 정렬해야 한다.
    • 가장 큰 남은(leftover) 홀을 생성한다.

단편화(Fragmentation)

  • 외부 단편화(External fragmentation)
    • 총 남은 매모리 공간이 요청을 만족하나, 연속적이지 않다.
  • 내부 단편화(Internal fragmentation)
    • 할당된 메모리가 요청한 메모리보다 많을 수 있다.
    • 이러한 크기 차이는 파티션에 속해 있지만, 사용되지 않는다.
  • 외부 단편화를 줄이기 위해서
    • Compaction
      • 메모리 내용을 섞어서 모든 여유 메모리를 하나의 큰 블록에 함께 배치하는 것이다.
      • 재할당(relocation)이 동적일 경우에만 가능하다. (실행 시간 주소 바인딩)
    • 프로세스의 논리적 주소가 비연속적이 되도록 허용하여 해당 메모리가 사용 가능한 곳이면 어디든 물리적 메모리가 할당될 수 있도록 허용한다.
      • 이를 위해 나온것이 페이징과 세그먼테이션

페이징(Paging)

프로세스의 논리적 주소가 비연속적이 되도록 허용하여 해당 메모리가 사용 가능한 곳이면 어디든 물리적 메모리가 할당될 수 있도록 허용한다.

  • 물리적 메모리를 고정된 크기의 블록(프레임, frames)으로 나눈다.
  • 논리적 메모리를 동일한 크기의 블록(페이지, pages)으로 나눈다.
  • 크기가 n 페이지인 프로그램을 실행하기 위해서, n개의 여유 프레임을 찾아 프로그램을 로드해야 한다.
  • 페이지 테이블이 논리적 주소를 물리적 주소로 변경할 수 있도록 해야 한다.
  • 내부 단편화를 해결해야 한다.

페이징 모델

3

주소 전환 체계(scheme)

  • CPU에 의해 생성된 주소는 다음 두가지 부분으로 나뉜다.
    • 페이지 넘버(p)
      • 물리적 메모리의 각각 페이지에 해당하는 베이스 주소를 포함하는 페이지 테이블의 인덱스로 사용된다.
    • 페이지 오프센(d)
      • 베이스 주소와 합쳐져서 메모리 유닛으로 보내진 물리 메모리 주소를 정의하는데 사용된다.

주어진 물리 주소 공간 2^m^ 과 페이지 크기 2^n^에 대해

page number page offset
p d
m-n n

메모리 페이징 예제 5

Free frame 목록 6

페이지 테이블의 구현

  • 페이지 테이블은 메인 메모리에 보관된다. (프로세스당 1개 존재?)
  • 페이지 테이블 베이스 레지스터(PTBR)는 페이지 테이블의 시작주소를 가리킨다.
  • 페이지 테이블 길이 레지스터(PTLR)는 페이지 테이블의 크기를 가리킨다.
  • 이러한 시스템에서, 모든 데이터/명령 접근은 두 번의 메모리 접근을 필요로 한다.
  • 두 번의 메모리 접근 문제(속도의 저하)는 TBL(Translation Look-aside Buffers)특별한 fast-lookup 하드웨어 cached 를 통해 해결할 수 있다.
  • free frame list는 시스템에 1개 존재한다.
  • Page Table의 size가 커서 RAM에 저장되며, 실제 MMU에는 Associative memory인 Translation Look-Aside Buffer(TLB cache)가 있다.

TLB

7

  • 몇몇 TLB cache에는 주소-공간 구별자(address-space identifiers, ASIDs)를 각각의 TLB 엔트리에 저장한다. ASIDs가 각각의 프로세스를 특별하게 구별하고 그 프로세스에 대한 주소공간 보호를 제공한다.
  • 효과적인 액세스 타임(Effective Access Time) = (1+e)a+(2+e)(1-a) = 2+e-a
    • TLB 룩업 - e time unit
    • 메모리 액세스 타임 - 1 time unit
    • Hit ratio (a)
      • TLB에서 페이지 넘버가 발견되는 비율

메모리 보호

  • 메모리 보호는 각각 프레임에 연결된 프로텍션 비트(protection bites)로 구현된다.
  • valid-invalid bit
    • 페이지 테이블의 각각 엔트리에 존재한다.
    • “valid”는 연관된 페이지가 프로세스의 논리적 주소 공간에 존재함을 의미한다.
    • “invalid”는 연관된 페이지가 프로세스에 존재하지 않음을 의미한다.
  • Valid-Invalid bit는 Page가 Read only 또는 Read/Write 별로 정의되어 있는 것을 구분시켜주는 것으로 만약 읽기 전용에 Frame에 쓰기를 시도한다면 OS가 Trap으로 프로세스를 죽이게 된다.
  • 보호를 위해 PTLR을 사용해서 illegal address를 참조하지 않도록 하는 방법도 있다.

8

공유된 페이지(코드)

  • 프로세스를 통해 공유된 하나의 read-only(reentrant) 코드.
  • Page 단위로 공유를 할 수 있으며 Read Only Page의 reentrant code가 공유되면 좋다.
  • Multi Thread의 메모리 공유와 비슷하게 Stack을 제외한 것을 공유할 수 있다.
  • 단순히 메모리 공유로 IPC를 할 수 있는 것이 장점이다.
  • 공유되는 Page는 같은 Frame을 공유해야 하므로 이를 번역하는 Page Table에서 혼동되면 안 되기 때문에 아무 데나 존재하면 안 된다.
  • Private Code, Data는 공유되는 것이 아니므로 아무 곳에나 존재해도 된다.

9

페이지 테이블의 구조

  • 계층 페이징(Hierarchical paging)
    • 논리적 주소를 여러 페이지 테이블로 쪼갠다.
    • two-level 페이지 테이블이 간단한 기법이다.
  • 해시 페이지 테이블(Hashed page tables)
  • 역전된 페이지 페이블(Inverted page tables)

10

** 투 레벨 페이지 테이블 체계 예제 **

  • 32-bit 머신, 4K 페이지 크기
  • 각각의 페이지 엔트리 크기는 4 바이트
  • 논리적 주소는 다음으로 구성됨
    • 20 bit의 페이지 넘버
    • 12 bit의 페이지 오프셋
  • 페이지 페이블이 페이징되었으므로, 페이지 넘버는 다음과 같이 구성됨.
    • 10 bit 페이지 넘버
    • 10 bit 페이지 오프셋

** 예제 하나 더 ***

32 bit 머신, 1K 페이지 크기 페이지 엔트리 크기 = 4 바이트

** 쓰리 레벨 페이징 예제 **

p~1~ (42) p~2~(10) d(12)  
p~1~(32) p~2~(10) p~3~(10) d(12)

계층 페이지 테이블은 보통 64비트 아키텍처에서 부적절함

해시드 페이지 테이블

  • Common in address spaces > 32 bits
  • 가상 페이지 넘버는 페이지 테이블로 hashed 됨
    • 이 페이지 테이블은 같은 공간으로 해싱되는 element의 chain을 포함한다.
  • 가상 페이지 넘버는 이 해시 테이블 안에서 찾는다.
    • 만약에 찾으면, 상응하는 물리적 프레임이 추출된다.

: Page Table entry가 32bit보다 더 큰 수로 표현돼야 할 겨우 이 방법을 고려한다.

  : Hierarchical Paging을 해도 Outer Page entry 수가 너무 많아서 Page entry 자체를 줄일 수 있는 Hash function을 사용하여 Table 구조를 만들었다.

  : Original Page Table은 찾는 시간은 걸리지 않아서 O(1)의 Time Complexity를 가졌고, Direct Method로 Hashing 한다면 Original Page Table과 같이 O(1)의 Time Complexity를 가진다.

  : Hashing 되어 같은 Key 값을 가지게 되는 것을 Synonym이라 하며, 같은 주소를 참조하는 Key가 여러 개 있다면 이는 Collision이 발생했다고 하고, Collision resolution으로는 Chaining을 사용한다.

  : Chaining을 함에 따라 Linked list의 size에 따라 Time Complexity는 O(1) ~ O(n)를 가지게 된다. ![11](/images/운영체제3/11.PNG "hashed page table")

역전된 페이지 테이블(Inverted Page Table)

  • 메모리의 각각의 실제 페이지들에 대해 하나의 엔트리 제공(모든 프로세스가 하나의 페이지 테이블을 공유), Frame마다 하나의 entry를 가진다.
  • 엔트리는 페이지를 소유하고 있는 프로세스에 대한 정보와 함께, 실제 메모리 위치에 저장된 페이지의 가상 주소로 구성되어 있다.
  • 각 페이지 테이블을 저장하는 데 필요한 메모리를 줄이지만 페이지 참조가 발생할 때 테이블을 검색하는 데 필요한 시간은 오히려 늘어난다.

12

세그먼테이션(Segmentation)

  • 메모리에 대한 사용자 관점을 지원하는 메모리 관리 기법
  • 프로그램은 세그먼트의 집합으로 이루어져 있다.
    • 세그먼트는 다음과 같은 논리적인 단위 하나하나이다.
      • 메인 프로그램
      • 프로시져
      • 함수
      • 메소드
      • 객체
      • 지역 변수, 전역 변수
      • 평범한 블록
      • 스택
      • 심볼 테이블
  • 각 Segment의 크기가 다르므로 Multiple Partition으로 메모리를 할당하며 이에 따라 External Fragmentation은 없지만, Internal Fragmentation이 생긴다. xxx

세그먼트는 크기가 고정되어 있지 않고 가변적이다. 크기가 다른 각 세그먼트를 메모리에 두려면 동적 메모리 할당을 해야 한다. 앞에서 말한 외부 단편화가 발생할 수 있다. 반면에 페이징은 외부 단편화를 해결하므로 둘을 스까면 된다.

13

  • 논리적 주소는 두 개의 튜플로 이루어져 있다.

<세그먼트-넘버, 오프셋>

  • 세그먼트 테이블
    • 이차원적 물리 주소를 매핑한다.
    • 각각의 테이블 엔트리는 다음 요소를 가지고 있다.
      • 베이스(Base) - 메모리의 세그먼트가 존재하는 물리적 주소의 시작점을 포함한다.
      • 리미트(Limit) - 세그먼트의 길이를 정해준다.
    • 세그먼트-테이블 베이스 레지스터(STBR)
      • 메모리의 세그먼트 테이블의 위치를 가리킨다.
      • 프로그램에 의해 사용된 세그먼트의 갯수를 가리킨다.
        • 게스먼트 넘버 s는 s<STLR 일 경우 유효하다.

  • Segmentation은 Multiple Partition(Variable Size Partition)을 사용하고 이 중에서 First-fit, Best-fit을 사용한다.

  • Relocation Address를 사용하고 Dynamic Execution Binding을 한다.

  • Segment Sharing은 Sharing의 기본 단위가 segment이므로 Segment Table에서 같은 메모리를 참조하도록 limit과 Base로 주소를 정해주면 공유된다.

  • Page와 비슷하게 Protection은 Valid-Invalid bit로 가능하며 Read/Write/Execute에 대한 정보를 가지고 있다.

  • Variable Size Partition은 Execution Time Binding이 아니어도 되지만 Segmentation에서는 Execution Time Binding이어야 한다.

14 15 16

가상 메모리

  • 보통, 프로그램의 특정 부분만 실행을 위해 메모리에 있을 필요가 있다.
    • 평범하지 않은 오류 상황을 핸들링하기 위한 코드들
    • 배열, 리스트, 그리고 테이블들은 종종 필요한 메모리보다 더 할당된다.
    • 프로그램의 특정 옵션과 기능들은 거의 사용되지 않는다.
    • 프로그램 전체가 모두 필요한 기능이더라도, 모두 동시에 필요하지는 않을 것이다.
  • 프로그램을 메모리에서 부분적으로 실행하는 것의 장점
    • 프로그램은 더이상 가능한 물리적 메모리에 제약받지 않는다.
    • 더 많은 프로그램들이 동시에 실행될 수 있다.
    • 유저 프로그램이 메모리로 로드되거나 스왑되는데 I/O가 더 적게 필요할 것이다.

17 18

  • 프로그램이 실행되려면 메인 메모리에 프로그램이 탑재되어야 하는데, 그 크기가 클 경우는 문제가 될 수 있다.

  • 소스 코드의 전체의 루틴 중에 실행되어 사용되는 코드는 많지 않으므로, 전체 중에 일부만 탑재시키는 목적으로 가상 메모리를 사용한다.

  • Memory Management에서의 목적과 같이 Degree of multiprogramming을 높여주는 것이 목적이지만 Memory Management의 Overlay나 Dynamic Loading, Linking과 다른 것은 Logical address space의 대부분이 탑재되는 것이 아닌 대부분이 탑재되지 않으며 사용되는 부분만 탑재되어 물리적 주소공간을 절약할 수 있게 된다.

  • 각 process는 logical address space가 Virtual address space로 되며 이는 무한대의 공간을 가질 수 있다.

  • 실행에서는 Logical address space(virtual address space)와 Physical address space가 분리되어있어야 하며, 이는 Execution time binding이 필요하다.

  • 프로그램이 Physical memory보다 클 경우도 탑재할 수 있으며 프로그램의 메모리를 분리하여 논리 공간과 물리 공간의 사용되는 부분만 탑재해서 사용하므로 Paging과 Segmentation이 사용될 수 있다.

  • 메모리를 분리해서 관리하므로 공유메모리 구현이 가능하며 파일 공유가 쉽다.

  • 구현이 어려우며 잘못 사용한다면 성능이 저하될 수 있는 것이 단점이다.

  • 전체를 탑재하지 않아서 프로세스 생성에 효율적이며, 더 많은 프로그램이 동시에 돌아갈 수 있고, 프로세스를 load 혹은 swap 할 때, 더욱 적은 I/O로 가능하다.

  • Virtual Memory는 OS가 제공하는 기능으로 Process의 어느 부분이 탑재되었는지, 언제 Process의 부분을 가져올 것인지, 어디에 탑재시킬 것인지, 언제 빼내 올 것인지를 정해야 한다.

  • OS가 언제 부분을 가져올지에 대해서 Page에 대해서 한다면 Demand Paging, Segmentation 기반으로 한다면 Demand Segmentation이라 한다.

  • 각 부분을 Main Memory로 가져오는 것을 Swap-in, 빼내는 것을 Swap-out이라 하며, 이 Swapping은 Medium-term Scheduler의 Swapping과는 다른 것으로 각 단위, 부분에 대한 것이다.

가상 메모리 관리 전략

디맨드 페이징(Demand paging)

  • 가상 메모리는 다음에 의해 구현될 수 있다.
    • 디맨드 페이징(Demand paging)
    • 디맨드 세그먼테이션(Demand segmentation)
  • 디맨드 페이징(Demand paging)
    • 페이지가 필요할 때 그 부분만 메모리로 불러온다.
      • Lazy swapper (or pager)
      • 적은 I/O가 필요
      • 적은 메모리가 필요
      • 빠른 반응 속도
      • 더 많은 유저
    • 메모리에 있는 페이지들과 디스크에 있는 페이지들을 구별하기 위해 하드웨어 지원이 필요하다.
      • valid-invalid bit 체계가 쓰인다.
        • valid - 연관된 페이지가 유효하고, 메모리에 있다.
        • invalid - 페이지가 유효하지 않거나, 메모리에 올라가있지 않다. invalid는 abort하고 not in memory는 메모리로 불러온다. 19
  • 페이지 폴트(Page fault)
  • Process가 Page table에서 Legal address를 참조했으며, Page가 Main Memory에 탑재되지 않았을 경우를 나타낸다.
  • illegal Address를 참조했을 경우 OS는 Process를 abort() 하며 단순히 메모리에 없을 때 발생한다
  • 페이지에 대한 참조가 있으면, 첫 번째 참조는 운영체제에 trap을 발생시킬 것이다.
  • 운영체제는 “invalid 참조”와 “메모리에 없는 것”을 결정하기 위해 다른 테이블을 본다.
  • 빈 프레임을 얻는다.
  • page를 프레임과 Swap 한다.
  • 테이블을 Reset한다.
  • 유효 비트를 v로 설정한다.
  • page fault를 일으켰던 명령어를 재시작한다.

20

1: Invalid bit임을 알아서 OS에게 Trap이 발생함을 알린다.

  2: Context Switch가 발생하며 Process의 정보를 PCB에 저장한다.

  3: Vectored Interrupt 형식으로 Interrupt를 발생시킨 device가 data bus에 interrupt vector를 실어서 보내는데 이 Interrupt vector를 받아서 Page Fault Interrupt임을 확인한다.

  4: 해당 Page의 참조가 illegal 했다면 abort 시키고, Legal 했다면 Backing store에서 Page를 찾는다.

  5: Free Frame을 확보하며 없으면 Replacement 정책으로 Swap 할 Frame을 고른다.

  6: Backing Store에서 Frame에 쓰이기 위해 Backing store, disk가 읽힐 때까지 Device Queue에서 기다린다.

  7: 해당 Device를 찾을 때까지 걸리는 Seeking time이 걸리게 된다.

  8: 찾은 후에 Free frame으로 Page를 가져온다 (Swap-in)

  9: 위의 기다리는 시간 동안 CPU에게 다른 프로세스를 할당한다. 원래의 프로세스는 waiting state에 있다.

  10: Swap-in이 끝나게 되면 Disk controller가 Interrupt를 발생시킨다.

  11: Interrupt가 발생하여 CPU에서 돌고 있던 다른 프로세스의 정보가 PCB에 저장되는 Context switch가 일어난다.

  12: 어떤 Interrupt인지를 확인하며, Disk로부터 발생하였음을 확인한다.

  13: OS에 의해서 Page Table의 수정이 일어난다.

  14: 원래의 프로세스가 다시 CPU의 할당을 받기 위해 잠시 기다린다.

  15: 원래 프로세스의 정보가 담긴 PCB를 가져오는 Context switch가 일어난다. 

  16: 처음에 Interrupt가 걸린 Instruction을 재시작한다.

Page table과 swap space, Instruction restart를 위해서 Hardware인 MMU chip이 필요하다.

  • 프로세스가 시작할 때 1개도 메모리를 탑재시키지 않고 실행시키는 것을 Pure Demand Paging이라 한다.

  • 한 번도 불리지 않은 Page는 Page Fault interrupt가 반드시 발생하고, 이때의 Page fault는 특별히 Cold fault라고 한다.

  • Cold fault는 프로세스가 시작하는 초기 단계에서 집중적으로 발생하며, Replacement 정책으로 Page fault를 줄일 수 있는 반면에 Cold fault는 줄일 수 없다.

  • 디맨드 페이징의 성능
    • 페이지 폴트 비율 0 ≤ p ≤ 1
      • p가 0이면 페이지 폴트가 발생하지 않았다.
      • p가 1이면 모든 참조가 폴트이다.
    • Effective Access time(EAT)
      • EAT = (1-p) * 메모리 액세스 타임 + p * 페이지 폴트 타임
      • 페이지 폴트 타임 = 페이지 폴트 오버헤드 + 스왑 페이지 아웃 + 스왑 페이지 인 + 재시작 오버헤드

** 재시작 오버헤드 **

만약 페이지 폴트가 일어나면, 명령어를 fetch하고 decode해야 한다.

최악의 상황은 block move가 일어날 때…. (겹침)

해결방법

  • To access both ends of blocks

  • To use temporary registers to hold the values of overwritten locations

  • 가상 메모리 아래에서 프로새스 생성
    • 부모와 자식 프로세스는 초기에 메모리의 같은 페이지를 공유한다.
    • 만약 두 프로세스가 공유 메모리를 변화시켜야만 페이지가 복사된다.
      • (copy-on-write)
  • Copy-on-Write는 Parent Process가 fork 하여 생긴 Child Process의 page를 공유하다가 Child가 Page에 write를 하면 해당 페이지만을 Copy 하는 것을 의미한다.

새로운 프로세스를 실행하는 방법은 보통 fork 시스템 콜을 사용한다고 앞서 설명하였다. 그런데 페이징 방법을 고려하면 프로세스를 복사하는 것이 만만찮은 작업임을 알 수 있다. 심지어 어떤 프로세스는 복사되자마자 exec 시스템 콜을 호출하여 다른 프로세스로 바뀌어버린다. 이는 페이지나 페이지 테이블을 복사하는 것이 낭비가 될 수 있음을 뜻한다.

21 22

페이지 전환 체계(Page Replacement Schemes)

23

  • OS가 Free Frame을 관리하게 되는데, Kernel과 I/O 버퍼용 frame을 미리 확보해놓게 되고, 특히 I/O 버퍼는 상당히 큰 크기를 가지고 있다.

  • 만약 여유 프레임이 없으면
    • 메모리에서 실제 사용되고 있지 않은 페이지를 찾아 스와핑한다. (Page replacement)
    • 페이지 폴트의 최소 넘버를 위한 페이지 전환 알고리즘이 필요하다.
    • page transfer 오버헤드를 줄이기 위해 (dirty)비트를 수정(Modify)한다.
      • 오직 수정된 페이지들만 디스크로 다시 쓰기된다.

  • Free Frame이 없는 경우 Victim Page를 내보내고 요청된 Page를 가져오는 2번의 메모리 접근이 필요하고 EAT이 증가하게 되는데, modify bit를 사용하여 이러한 Overhead를 감소시킬 수 있다.

  • Modify(Dirty) Bit를 사용하여 확인되면 내용이 원래 디스크 상의 페이지 내용과 다르다는 것을 알 수 있고 현재의 내용을 디스크에 기록하게 된다. Swap out 시에 이 bit를 확인하고 Disk에 기록하며, set이 안 돼 있으면 단순히 버린다. 이 기법은 읽기 전용 페이지에도 적용된다.

  • 기본적인 페이지 전환
      1. 디스크에서 요구되는 페이지의 위치를 찾는다.
      1. 빈 프레임을 찾는다.
        • 만약 빈 프레임이 있으면, 사용한다.
        • 만약 빈 프레임이 없으면, 희생(victim) 프레임을 선택하도록 한다.
        • Modify bit이 Set 되어있다면 Victim을 디스크에 기록한다.
      1. 요구된 페이지를 새 프레임에 할당시키고, 페이지와 프레임 테이블을 업데이트한다.
    • 프로세스를 재시작한다. 24

페이지 전환 알고리즘

25

  • FIFO
    • Belady’s abnormaly -> more frames == more page faults 딜레마에 빠진다
    • ex) 1 2 3 4 1 2 5 1 2 3 4 5 => 3 frame:9 page fault, 4 frame:10 page fault

26

  • Optimal [26]

27

  • LRU(Least Recently Used)
    • 구현: Counters(각각의 페이지가 엔트리에 의해 참조되면 페이지-테이블 엔트리에 시간 저장 - 페이지 테이블 변경시마다 시간값 관리, 카운터를 써칭하는 시간의 오버헤드가 발생한다.), Stack(페이지가 참조되면 스택에서 지워지고 top에 저장함 - Double Linked List로 Stack이 구현된다. Bottom의 Page가 무조건 Victim이므로 Victim을 찾는 시간이 없다. Page를 참조할 때마다 Stack의 위치이동이 일어나므로 Overhead가 존재한다.) : 하드웨어 지원 필요
  • LRU-Approximation: 기존 LRU는 몇개의 하드웨어만이 완벽하게 지원하기 때문에 reference bit를 사용
    • Additional-Reference Bits
      시간 대신 8비트 레퍼런스 비트 사용: 10101010이 01010101보다 최근에 불려짐, 일정 interval 마다 비트를 우측으로 이동
    • Second-Chance
      FIFO로 동작하고, 레퍼런스 비트가 1이면 그 페이지에게 두 번째 기회를 주고 다음 FIFO 페이지를 찾는다. 두 번때 기회를 받으면 레퍼런스 비트가 0이 된다. 모든 비트가 set되어있을 경우 fifo 알고리즘이 된다.
    • Enhanced second chance
      레퍼런스 비트 + 모디파이 비트
      입/출력 횟수를 줄이기 위해 변경된 페이지에 우선순위를 준다.
      교체될 페이지를 찾기까지 여러 번의 순환 큐를 검사할 수 있다.
      Modify bit가 Set 되어 있다면 Replace 할 때에 Hard disk에 쓰기 하는 데에 부담이 있다.
      두 bit 모두 0일 때가 Replace 되기에 좋은 Page이며, Reference bit이 Modify bit보다 Replace가 되지 않을 우선순위가 높다.
레퍼런스 비트 모디파이 비트  
0 0 최근에 사용되지도 않았고 수정되지도 않음
0 1 최근에 사용되지 않았으나 수정됨 -> 페이지가 전환 전에 사용되어져야 됨
1 0 최근에 사용되었으나 clean함 -> 필시 다시 쓰일 가능성이 있음
1 1 최근에 사용되었고, 수정됨

  • 전환되어야 할 페이지가 발견되기 전에 여러 번 원형 큐를 스캔해야 할 수도 있다.

  • Counting-based: 각각의 페이지에 생성된 참조의 갯수 카운터를 저장한다.

    • LFU(Least Frequently Used)알고리즘
      • 카운트가 가장 작은 페이지를 전환한다.
      • 가장 활발한 페이지가 큰 참조 카운트를 가진다고 가정한다.
      • : 하지만 초기에 많이 사용되고 나중에는 사용되지 않는 식의 일이 발생한다면 문제가 된다
      : 일반화시키면 집중적으로 사용된다면 사용되지 않더라고 이 방식으로는 메모리에 머무르게 된다.

      이를 해결하기 위해 일정 시간마다 Counter bit를 1씩 shift 시켜서 지수 적으로 영향을 감소시킨다.

    • MFU(Most Frequently Used)알고리즘
      • 카운트가 가장 큰 페이지를 전환한다.
      • 가장 작은 카운트를 가진 페이지가 들어왔고, 사용되지는 않았다고 가정한다.
      • : 작은 Counter의 수를 가진 Page는 가장 최근에 참조된 Page 것으로 해석한다.
      : 값이 큰 Counter를 가진 Page는 나중에 들어왔기 때문에 Counter가 클 것으로 해석한다.

      Locality of reference를 배경으로 한 해석을 기반으로 한다.

assume that the page with the smallest count was probably brought in and has yet to be used

추가

페이지 버퍼링(Page-Buffering) 알고리즘은 풀링(Pooling) 방식을 적용한 알고리즘이다. 사용 가능한 물리 메모리 프레임을 풀에 보관하다가 필요하면 꺼내 쓰고 victim은 보조 기억 장치에 복사한 뒤 다시 풀에 추가한다.

프레임의 할당

  • 메모리는 크게 OS를 위한 부분과 사용자를 위한 부분으로 나눌 수 있으며, 프로세스는 사용자를 위한 부분의 메모리에 탑재되어 사용된다.

  • 가상 메모리 기법을 이용하여 프로세스의 일부 메모리만을 탑재하며 실행시킬 수 있게 되지만, 다중 프로그래밍 환경에서는 여러 개의 프로세스가 메모리에 존재하게 되고, 이에 따라 몇 개의 Frame을 프로세스에 할당하여 다중 프로그래밍을 구현할 것인지 정해야 한다.

  • 프로세스에 할당할 최소 Frame의 수는 Instruction Set Architecture에 의해서 결정되는데, 명령어가 실행 도중에 Page Fault 현상이 일어나게 되면 해당 명령이 다시 시작해야 되므로, 하나의 명령어가 참조할 수 있는 모든 페이지를 수용할 수 있는 충분한 Frame이 존재해야 한다.

  • 프로세스에 할당할 수 있는 최대 Frame 수는 할당 가능한 실제 메모리의 양으로 정의된다.

  • 최소 Frame 할당과 최대 Frame 할당 사이에서 적당한 Frame 할당을 해야 한다.

  • 이러한 Frame 할당 방법에는 Fixed Allocation과 Priority Allocation이 있다.

  • 각각의 프로세스는 최소 프레임의 갯수가 필요하다.
    • IBM 370 - MOVE 명령어를 위해 6페이지
      • 명령어 - 6 바이트 (1 워드보다 크다.), 2 페이지 차지
      • from을 위해 2 페이지(indirect addressing 케이스에서)
      • to를 위해 2 페이지(indirect addressing 케이스에서)
  • 프레임 할당 체계
    • 고정 할당 vs 우선순위 할당
    • 글로벌 할당 vs 로컬 할당
  • 고정된 할당(Fixed Allocation)
    • 균등 할당(Equal Allocation)
      • 100 프레임과 5 프로세스가 있으면 각각 프로세스에게 20 프레임 할당
    • 비례 할당(Proportional allocation)
      • 프로세스의 크기에 따라 할당
        • s~i~ = 프로세스 p~i~의 크기
        • S = ∑s~i~
        • m = 프레임의 총 갯수
        • a~i~ = allocation for p~i~ = (s~i~/S * m)
  • 우선순위 할당
    • 크기보다 우선순위를 사용하여 부분적인 할당을 함
    • 만약 프로세스 P~i~가 페이지 폴트가 일어나면
      • 낮은 우선순위의 프로세스를 프레임 전환을 위해 선택함
  • 글로벌 전환(할당)
    • 프로세스가 변경할 프레임을 모든 프레임 셋에서 찾는다. 하나의 프로세스가 다른 프로세스의 프레임 take 가능
      • 다중 프로그래밍 환경에서 여러 프로세스가 메모리에 상주할 때, 한 프로세스는 모든 Frame에 대해서 Replacement를 해줄 수 있다.

  • 다른 프로세스에 할당된 Frame을 가져올 수 있으며, 한 프로세스에 할당되는 Frame 수는 바뀔 수 있다.

  • 프로세스 실행 시간이 매우 다양하게 바뀔 수 있으며 Throughput이 좋아질 수 있다.

  • 어떤 Frame을 가져올지 모름으로 프로세스가 자신의 Page Fault Rate를 조절할 수 없다.
  • 로컬 전환(할당)
    • 각각의 프로세스가 그 고유의 할당된 프레임 셋에서만 선택

  • 각각의 프로세스는 자신에게 할당된 Frame 안에서 Replacement를 한다.

  • 잘 사용되지 않는 Frame이 있다면 낭비의 문제가 있을 수 있다.

쓰래싱(Thrashing)

  • Degree of multiprogramming을 높이기 위해서 프로세스마다 할당해줄 Frame을 줄일 수 있다.

  • 프로세스가 실제 사용하는 Frame 수 만큼 프레임을 갖지 못하게 되면 Page Fault가 계속해서 일어나게 되고, CPU Utilization은 프로세스의 page가 계속 교체돼서 I/O 작업이 계속 일어나게 돼서 줄어들게 된다.

  • 다중 프로그래밍의 정도를 높이기 위해 Frame의 개수를 줄이다가 CPU 활용도가 줄어들게 되는 현상을 Thrashing이라 한다.

  • 어떤 프로세스가 프로세스 수행에 보내는 시간보다 페이지 교환에 보내는 시간이 더 크면 Thrashing이라고 할 수 있다.

  • Thrashing을 해결하기 위해서는 프로세스에 필요한 만큼의 Frame을 할당하는 것이다.

  • Thrashing에 대한 대책으로 Working-Set Model이 사용된다.

  • 만약 프로세스가 충분한 페이지를 가지고 있지 않다면, 페이지 폴트는 매우 빈번하게 발생
    • 낮은 CPU 최적화
    • 운영체제가 멀티프로그래밍의 수준을 높여야겠다고 생각
    • 다른 프로세스가 시스템에 들어올 때
  • 쓰래싱이란 프로세스가 스와핑하는데 매우 바쁜 시간을 보내는것을 말한다.
  • 쓰래싱을 방지하기 위해서는 필요한 충분한 프레임을 제공받아야 한다.
    • 우리가 어떻게 그것이 얼마나 필요한지 알까?
    • 프로세스 실행의 로컬 모델
      • 로컬리티(Locality) - 같이 사용되고 있는 페이지의 집합
      • 프로세스는 한 로컬리티에서 다른 로컬리티로 이주한다.
      • 로컬리티는 겹칠 수 있다.
  • 쓰래싱은 현재 로컬리티의 크기 > 할당된 프레임의 크기 일때 발생함.

28

  • Working-Set Model

    • 가능한 한 최대의 다중 프로그래밍의 정도를 유지하면서 Thrashing을 막기 위해 사용한다.

    • Locality를 개념으로 만들어진 것으로, 프로세스가 많이 참조하는 Page들의 집합을 메모리 공간에 계속 상주하게 하여, 빈번한 Page Replacement를 줄이는 방법이다.

    • Locality

      Locality는 집중적으로 사용되고 있는 Page의 집합이라 할 수 있다.

      실행 중인 프로세스는 Page 중에 일부를 선호하여 지역적인 부분만을 참조하게 되고 이를 Locality 라 한다.

      기본적인 Page는 중첩돼서 사용되며, 소수의 Page만 Replacement 되는 프로세스의 특성에 의해서 나온 개념이다.

      Thrashing은 Locality에 사용되는 메모리보다 주어진 메모리가 작아서 발생하는 것으로 볼 수 있고, 이에 따라 충분한 Frame을 주어야 한다.

    • 프로세스의 Working-Set Model을 구성하기 위해, 작업설정의 크기를 알아야 하고, 이는 Working-Set Window를 이용한다.

    • Working-Set Window는 프로세스의 Locality에 근사한 값으로 정해지는 것이 좋으며, 특정 시점부터 과거에 참조한 페이지를 보고 미래를 예측하기 위해서 사용한다.

    • Working-Set Window가 크면 여러 개의 Locality를 1개의 Locality로 간주할 수 있다.

    • Working-Set Window가 작으면 1개의 Locality도 포함하지 못할 수 있다.

    • WSS를 프로세스의 Working-Set이라 할 때, 모든 프로세스의 WSS의 합을 D라 하며 전체 요구 Frame과 같다.

    • D가 할당 가능한 Frame의 수 m보다 크게 되면 Thrashing이 발생하게 된다.

    • D가 m보다 크면 프로세스 중 하나는 suspend 되며 이는 Medium-term scheduler가 해준다.

    • 프로세스가 수행되는 동안의 Working-Set은 계속해서 변화한다.

    • OS는 각 프로세스의 Working-Set을 감시하며 각 프로세스에 Working-Set 크기에 맞는 충분한 Frame을 할당하고, Frame이 남을 때는 다른 프로세스도 탑재시키며 다중 프로그래밍의 정도를 증가시키고, 이때 D가 m보다 크게 되면 잠시 중지시킬 프로세스를 선정해서 Page를 회수한다.

Working set and Page Fault Rates

  • Working Set이 설정됨에 따라 초반에는 Page Fault Rate가 높은 것을 볼 수 있지만, 시간이 지나면 Locality에 의해서 Page Fault Rate가 줄어든 것을 볼 수 있다.

  • Page Fault Frequency

    • Working-Set model은 Overhead가 많이 발생하여 이와는 다른 방식으로 사용하며 Working-Set model보다 직접적인 접근 방식이다.

    • Thrashing을 막기 위해서 Page Fault Rate를 사용한다.

    • 허용할 수 있는 Page Fault Rate 구간을 설정해서 높으면 Frame을 할당받아야 하고, 낮으면 Frame을 잃어도 되는 식으로 구현한다.

    • 프로세스가 새로운 지역성으로 이동하는 과도기에는 제대로 작동하지 않을 수 있는 문제가 있다.

Page-Fault Frequency(PFF)는 말 그대로 Page fault인 페이지 결함의 발생 비율을 측정하여 프레임을 할당하는 방식이다. 할당된 프레임의 수와 페이지 결함이 일어나는 비율을 측정한다. 특정 프로세스에 대해 프레임 할당을 많이 해줄수록 페이지 결함이 적게 일어날 것이다. 이와 반대로 프레임 할당이 적으면 페이지 결함이 많이 일어나게 될 것이다. 그래서 PFF라는 방식은 페이지 결함에 대한 특정 상한선을 초과한 프로세스에는 더 많은 프레임을 할당하여 페이지 결함을 줄이고 페이지 결함이 거의 없는 하한선 이하의 프로세스에는 프레임을 회수하여 적절하게 페이지 결함이 일어나지 않게 조절을 하게 된다.

29

30

  • Working set 모델
    • locality 기반
    • △ = working-set 윈도우
      • 페이지 참조의 고정된 갯수 (1000 명령어들 등등)
    • WS~i~ = 프로세스 P~i~의 working-set
      • 가장 최근의 △에서 참조된 페이지들의 집합
      • 만약 페이지가 활발히 사용중이라면 -> working-set 안에 있다.
    • WSS~i~ = WS~i~의 크기
      • 만약 △가 너무 작으면, 전체 locality를 포함하지 않을 것이다.
      • 만약 △가 너무 크면, 여러 locality를 포함할 것이다.
      • 만약 △가 무한대면, 전체 프로그램을 포함할 것이다.
    • D = 프레임에 대한 총 요구량 = ∑WSS~i~
    • 만약 D > m 이면 쓰래싱 상태
      • 만약 D > m 이면, 프로세스 중 하나를 종료한다.
    • working set 추적
      • 대략 interval timer + 참조 비트(reference bit)
      • 예제: △ = 10,000 참조
        • 각각의 페이지들에 대해서 2 비트 메모리를 keep한다.
        • 타이머가 항상 5000 참조 후에 인터럽트한다 -> 모든 레퍼런스 비트의 값을 복사하고 0으로 만든다.
        • 만약 메모리의 한 비트가 1이면 working set에 있는 페이지이다.

메모리 맵핑된 파일(Memory-Mapped Files)

  • 메모리 매핑된 파일 I/O를 통해 디스크 블록을 메모리의 페이지에 매핑하여 파일 I/O를 일상적인 메모리 액세스로 처리할 수 있음
  • 파일은 처음에는 디맨드 페이징(Demand Paging)을 사용하여 읽으며, 파일의 페이지 크기의 부분은 파일 시스템에서 실제 페이지로 읽힌다. 파일의 후속 읽기/쓰기/쓰기는 일반 메모리 액세스로 처리됨
  • read()/write() 시스템 호출 대신 메모리를 통해 파일 I/O를 처리하여 파일 액세스 간소화
  • 여러 프로세스가 동일한 파일을 매핑하여 메모리의 페이지를 공유할 수 있도록 허용

31

커널 메모리 할당

  • 유저 메모리와 다르게 다뤄짐
  • 종종 여유-메모리 풀에서 할당됨
    • 커널은 다양한 크기의 구조에 대한 메모리를 요청한다.
    • 어떤 크기의 데이터 구조가 페이지 크기보다 작은지 -> 단편화
    • 커널 메모리는 연속적일 필요가 있다.
  • 두가지의 잘 알려진 체계 32
    • 버디 시스템(Buddy system)
      • 물리적으로 연속된 페이지로 구성된 고정 크기 세그먼트에서 메모리 할당
      • 2의 배수 할당자를 사용한 메모리 할당
        • 2의 배수에 해당하는 단위로 요청을 충족하는 유닛
        • 다음으로 높은 2의 배수로 반올림된 요청
        • 가능한 할당보다 작은 할당이 필요한 경우, 현재 청크(chunk)가 다음으로 작은 2의 배수 버디로 분할된다.
        • 외부 단편화가 해결된다. 33
    • 슬랩 할당(Slab allocation)
      • ‘Slab’은 하나 이상의 물리적으로 연속된 페이지이다.
      • ‘Cache’는 하나 이상의 슬랩으로 구성된다.
      • 각각의 커널 데이터 구조에는 하나의 캐시가 존재한다.
        • 각 캐시는 오브젝트로 채워져 있다. 인스턴트화 된 데이터 구조
      • 캐시가 만들어지면, ‘free’로 마크된 오브젝트들로 채워진다. (자동 초기화)
      • 구조가 저장되면, 오브젝트는 ‘used’로 마크된다
      • slab은 완전 할당됨, 할당줌, 비어있음의 세가지 상태로 존재한다.
      • 만약 slab이 사용된 오브젝트들로 가득차면, 다음 오브젝트가 빈 슬랩에 채워진다.
        • 빈 슬랩이 없다면, 새로 빈 슬랩을 할당해준다.
      • 단편화가 없고, 빠른 메모리 요청을 만족한다.
      • 내부 단편화도 해결해준다.
  • 다른 이슈들
    • 프리페이징(Prepaging)
      • 프로세스 시작 시 발생하는 많은 페이지 폴트를 줄이기 위해서 사용
      • 페이지가 참조되기 전에 프로세스에 필요하게 될 모든 또는 일부 페이지들을 프리페이징 한다.
        • 프리페이징된 페이지가 쓰이지 않으면 I/O와 메모리가 낭비된다.
      • s 페이지가 프리페이징 되었고 a 페이지가 사용되었다고 치자.
        • cost of s*a의 비용이 saved page faults
        • cost of s*(1-a) unnecessary pages
        • if a is close to 0, prepaging loses
    • 페이지 크기
      • 프래그먼테이션(단편화)
      • 테이블 크기
      • I/O 오버헤드
      • 로컬리티(locality)
    • TLB Reach
      • TLB에서 접근할 수 있는 메모리의 양
      • TLB Reach = TLB size * page size
      • 이상적으로, 프로세스의 working-set이 TLB에 저장된다.
      • TLB Reach를 증가시키기 위해서는
        • TLB 엔트리의 갯수를 증가시키는 것 - 비용이 비싸다
        • 페이지 크기를 증가시키는 것 - 단편화가 심해진다
        • 여러 페이지 사이즈를 지원하는 것 - 운영체제가 TLB를 관리해야한다.
    • 역전된 페이지 테이블(Inverted page table)
      • 프로세스의 논리적 주소 공간에 대한 완벽한 정보를 가지고 있지 않다.
      • 각각의 가상 페이지가 어디에 위치해있는지 가리키는 외부 페이지 테이블이 필요
    • 프로그램 구조
    • I/O 인터록(Interlock)
      • 프로그램은 때때로 메모리에 locked되어야만 한다.
      • lock bit

파일 시스템

파일 시스템은 파일이라는 단위로 대용량 저장 장치를 잘 관리해주는 시스템이다. 앞서 언급한 바와 같이 저장 장치는 물리적으로 연결되어 있을 수도, 네트워크로 연결되어 있을 수도 있다. 이를 추상화하여 파일을 다루는 서비스를 제공하는 것이 파일 시스템이다. 가장 널리 알려진 파일 시스템으로는 FAT, NTFS 등이 있다.

OS마다 차이가 있겠지만 기본적으로 파일은 이름과 식별자, 종류, 위치, 크기, 보호, 시간, 날짜, 유저 정보 등을 포함한다. 파일에 대한 연산에는 파일 생성, 파일 쓰기, 파일 읽기, 파일 내 위치 이동, 파일 삭제, 파일 내용 초기화가 있다. 거의 대부분의 OS는 파일에 대한 연산을 수행하기 전에 그 파일을 여는 작업을 먼저 하도록 한다. 그러한 연산이 일어나는 곳은 프로세스이므로 프로세스는 열린 파일 테이블(Open file table)이라는 것을 가진다. 열린 파일에 대한 연산은 File pointer라는 것으로 다뤄진다. 파일은 여러 프로세스에 의해 동시에 접근될 수도 있기 때문에 어떤 시스템은 동기화를 위해 파일 락킹(File locking) 기능을 제공한다. 예를 들어 함께 파일을 열어 읽을 수 있는 락킹 모드(shared lock)라던가, 남이 파일을 열 수 없게 하는 락킹 모드(exclusive lock) 등을 제공한다.

널리 알려진 파일 종류는 크게 다음과 같다. 엄밀히 말해서 리눅스에서 파일 종류는 크게 디렉터리 파일과 일반 파일, 디바이스 파일로 나뉜다. 아래 파일 종류는 어떠한 규칙으로 저장된 일반 파일에 대해 프로그램이 각자 해석하는 것이지 시스템상으로 차이가 있진 않다.

저장 장치 상에서 접근 방법이 여러 가지 존재할 수 있다. 순차 접근(Sequential Access)은 시작점부터 종료점까지 위치를 순차적으로 이동하는 방법이다. 오직 되감기를 하거나 다음으로 이동만 가능하다. 자기 테이프와 같은 저장 장치에서는 이 방식이 유효하다. 직접 접근(Direct Access)은 저장 장치상의 특정 위치로 직접 이동할 수 있다. 저장 장치의 작동 방식에 따라 직접 접근도 접근에 시간이 걸릴 것이다. 어떤 파일이 어디에 위치해있는지 확인할 수 있도록 인덱스를 구성하기도 하고, 파일이 아주 많은 경우에는 인덱스의 인덱스를 구성하기도 한다. 인덱스를 잘 활용하는 대표적 프로그램으로 데이터베이스 관리 시스템(DBMS)이 있다.

디렉터리 구조도 여러 가지 방법으로 결정할 수 있다. 하나의 루트 디렉터리에 모든 파일이 모여있는 단일 수준 디렉터리(Single-Level Directory), 루트 디렉터리 아래에 하나의 디렉터리가 더 존재할 수 있는 이 단계 디렉터리(Two-Level Directory), 트리와 같은 구조로 디렉터리가 존재할 수 있는 트리 구조 디렉터리(Tree-Structured Directories), 비순환 그래프 구조의 디렉터리(Acyclic-Graph Directories), 아예 순환도 존재할 수 있는 일반 그래프 구조 디렉터리(General Graph Directory)가 있다. 디렉터리 구조에 따라 디렉터리 순회 방법에 대한 고려가 필요하다.

파일 시스템은 마운팅(Mounting) 될 수도 있다. 어떤 디렉터리를 마운트 포인트(mount point)로 보고 마운트 포인트에 다른 파일 시스템을 장착하는 식이다. 네트워크로 연결된 저장 장치도 마운트 한 뒤 파일 접근을 통해 사용할 수 있으므로 쉽고 강력한 기능이라고 볼 수 있다. 여러 저장 장치를 한 시스템에 연결해서 사용한다면 각 저장 장치를 볼륨이라는 이름으로 이미 마운트 해서 쓰고 있는 것이기도 하다.

현대 OS에서는 여러 유저가 시스템을 사용할 수 있도록 다중 사용자 기능을 제공한다. 이 경우 유저 간의 파일 공유가 문제가 될 수 있다. 또는, 네트워크 상으로 연결됐을 때 파일을 공유해줄 수 있도록 하는가도 고려 사항이 된다. 다른 사용자로부터 내 파일을 접근하지 못하도록 하고 싶을 수 있다. 따라서 파일에 대한 보호 기능이 제공된다. 파일 연산에 대해 권한을 나누어 권한별 사용이 가능하게 하는 것이 Access Control이다. 보통 읽기, 쓰기, 실행 권한 정도로 나눈다. 이에 대해서는 추후 보호 부분에서 더 다룬다.

파일 시스템은 볼륨마다 boot block, master file table(superblock)을 두고 파일마다 FCB(File Control Block)을 둔다. FCB는 파일에 대한 자세한 정보가 있는 테이블이다. UNIX에서는 inode에 FCB를 저장한다.

시스템에서는 메모리에 마운트 테이블, 최근 접근한 디렉터리 정보 캐시, 시스템 차원의 열린 파일 테이블과 프로세스당 열린 파일 테이블을 관리한다. 아래 사진은 열린 파일 테이블이 어떻게 사용되는지에 대한 그림이다.

리눅스에서는 VFS(Virtual File System)이라는 추상화 계층을 둔다. 파일 시스템 인터페이스 하에 추상 계층을 두고 추상 계층을 통해 각 파일 시스템이 이용된다. 리눅스의 VFS는 inode 객체, 파일 객체, superblock 객체, directory 객체를 기반으로 운영된다. 아래 그림은 VFS이 어떤 형태인지 보여주는 그림이다.

메모리 때와 마찬가지로 저장 장치의 공간을 할당하는 방법도 고민의 대상이다. 기본적으로 저장 장치는 블록이라는 단위로 나뉜다. 파일을 블록들을 물리적으로 연속하여 위치하도록 하면 당연히 좋겠지만 현실적으로 모든 블록을 연속적으로 두는 것은 어렵다. 각 디스크 블록을 연결된 리스트로 두는 방법도 있다. 하지만 이 방법은 중간 접근을 위해 각 블록을 순차적으로 읽어야 하기 때문에 성능 저하를 일으키게 된다. 곧바로 임의 위치 블록을 찾아 이동할 수 있도록 하기 위해 인덱스를 할당하는 방법이 대안이다. 다만 인덱스를 두는 블록을 어떻게 관리하고 구현할지가 문제가 된다. Linked Scheme, Multi-Level Index, Combined Scheme 등의 접근 방식이 존재한다. 디스크 블록을 읽어 들이는 작업은 매우 느리기 때문에 무엇보다도 디스크 접근을 최소화하는 방법이 성능상의 우위를 보이게 될 것이다. 아래 사진은 UNIX의 inode 관리를 위해 사용되는 Combined Scheme 방식을 보여준다.

가용 공간을 어떻게 관리할지도 생각할만한 부분이다. 저장 장치를 탐색하면서 저장 공간을 관리하는 것은 너무 오래 걸리기 때문에 따로 지속적으로 저장 공간 관리를 한다. 대표적으로 bit 벡터 방식과 연결된 리스트 방식이 있다. bit 벡터는 bit당 블록 하나로 쳐서 bit가 1이면 사용 가능하고, 0이면 사용 중인 것으로 간주한다. 매우 적은 용량과 빠른 알고리즘으로 가용 공간을 관리할 수 있다. 연결된 리스트 방법은 가용 블록들을 연결된 리스트로 관리하여 할당하기에 적합한 블록을 찾는 방법이다. 그 외, 그룹핑이나 카운팅, 공간 맵 방법 등이 있다. 아래 사진은 가용 블록들을 연결된 리스트로 관리하는 예시이다.

퀴즈1) 파일이란 프로그램 또는 데이터등과 같은 정보들의 집합을 말한다. 이러한 파일이 디스크에 할당될 때 구별되는 방법은 무엇인가. 퀴즈2) 파일의 구조와 레코드의 구조를 구분해 설명해보시오.. 퀴즈3) 파일 시스템이 필요한 이유를 파일과 디스크를 연결시켜 설명해 보시오. 퀴즈4) 버퍼 캐쉬(butter cache)를 사용하게 되면 파일을 읽어오는 속도를 높일 수 있다. 그 이유를 설명해 보시오. 퀴즈5) Memory map I/O를 사용하게 되면 read/write 성능을 높일 수 있다. 그 이유는 무엇인가.

정답1) 디스크에 할당되는 여러 파일들은 각자 고유한 이름을 가짐으로서 구별된다. 정답2) 파일의 구조는 바이트의 연속으로 별다른 구조가 없으나 레코드는 필드라는 단위가 모여 이뤄진다. 정답3) 연속적인 바이트로 구성된 파일이 512바이트로 나뉘어져 디스크 곳곳에 블록 단위로 저장되게 된다. 그런데 디스크는 바이트 단위로 읽어들일 수 없는 구조로 되어있기 때문에 파일과 디스크를 연결하는 파일 시스템이 필요한 것이다. 정답4) 처음 한번 읽은 파일은 버퍼캐쉬에 내용을 카피해 둠으로서 이후 동일한 파일을 사용할 때 읽어오는 속도를 높일 수 있는 것이다. 정답5) 디스크에 저장되어있는 파일이 버퍼 캐쉬를 통해 버퍼로 read 하는 대신 주소공간에 직접 load하기 때문에 파일이 주소공간의 일부가 되어 파일 I/O를 하지 않고 읽거나 쓸 수 있게 된다. 그렇기에 Memory map I/O를 사용하게 되면 read/write 성능을 높일 수 있다.