[CS Study] - 4주차

• 페이지 교체 알고리즘
• 캐시의 지역성
• 파일 시스템

들어가기 전에

가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다.

하지만 필요한 페이지만 올려도 메모리는 결국 가득 차게 되고, 올라와있던 페이지가 사용이 다 된 후에도 자리만 차지하고 있을 수 있다.

따라서 메모리가 가득 차면, 추가로 페이지를 가져오기 위해서 안쓰는 페이지는 out하고, 해당 공간에 현재 필요한 페이지를 in 시켜야 한다.

여기서 어떤 페이지를 out 시켜야 할 지 정해야 한다. 이때 out되는 페이지를 victim page라고 부른다.

기왕이면 수정이 되지 않는 페이지를 선택해야 좋다. 만약 수정되면 메인 메모리에서 내보낼 때, 하드디스크에서 또 수정을 진행해야 하므로 시간이 오래 걸린다.

이와 같은 상황에서 상황에 맞는 페이지 교체를 진행하기 위해 페이지 교체 알고리즘이 존재하는 것이다.

요구 페이징 (Demanding Paging)

• 필요한 페이지만 메모리에 할당하는 페이징 기법이다.
• 기존의 페이지 테이블과 다른 점은 valid bit가 추가되었다. 이는 현재 메모리에 페이지가 있는지 없는지를 나타내는 비트이다. 현재 페이지가 메모리에 있다면 1, 없다면 0 값을 갖는다.
• 가상 메모리를 만드는 방법은 대표적으로 두 가지가 존재하지만, 대부분 요구 페이징을 사용하므로 가상 메모리와 요구 페이징을 같은 용어로 사용하는 경우가 많다.

페이지 부재 (Page Fault)

페이지 부재는 CPU가 접근하려는 페이지가 메모리에 없는 경우이다. 즉, 페이지 테이블의 valid bit 값이 0인 경우이다.

위 그림은 page fault가 발생했을 때 처리하는 과정을 나타낸 것이다.

1. 해당 페이지가 메모리에 있는지 valid bit를 확인한다.
2. valid bit가 0이라면 CPU에 인터럽트 신호를 보내어 운영체제 내부 해당 ISR (Interrupt Service Routine)로 점프한다.
3. 해당 ISR에서 디스크(backing store)를 탐색하여 해당 프로세스의 페이지를 찾는다.
4. 해당 페이지를 비어있는 프레임에 할당한다.
5. 페이지 테이블을 갱신한다. (프레임 번호 설정, valid bit 1로 변경)
6. 다시 명령어로 돌아가서 실행한다.

ISR: 인터럽트 접수에 의해 발생되는 인터럽트에 대응하여 특정 기능을 처리하는 기계어 코드 루틴

Page Reference String

페이지 교체 알고리즘을 살펴보기 전에 Page reference string 이라는 용어를 알아야 한다. CPU가 내는 주소는 이진수 단위이지만, 페이지 교체 알고리즘을 계산하기 위해서는 이진수 주소 단위가 아닌 페이지 단위로 계산해야 한다.

예를 들어, CPU가 내는 주소를 간단히 십진수로 표현하여 {100, 101, 102, 432, 612, 103, 104, 611, 612} 라고 하자. 만약 페이지 크기가 100bytes라면, 위 주소를 페이지 번호로 나타내면 {1, 1, 1, 4, 6, 1, 1, 6, 6} 이다. 주소 100번지는 1번 페이지에서 offset이 0인 위치이고, 101은 1번 페이지의 offset이 1인 위치라고 볼 수 있다.

페이지 번호로 나타낸 것을 page reference string으로 나타내면 {1, 4, 6, 1, 6} 이다. 이는 간단히 말하면 연속된 페이지는 생략하고 하나의 페이지 번호만 나타낸 것으로 볼 수 있다. 이 이유는 연속된 페이지를 참조할 때는 한 번 page fault가 발생하면 같은 페이지를 사용하는 동안에는 page fault가 발생하지 않기 때문이다. 즉, 메인 메모리에 올라와 있는 주소들은 페이지 단위로 가져오기 때문에 페이지 번호가 연속되어 나타나게 되면 페이지 결함이 발생하지 않는 것이다.

정리하면, page size = 100bytes 일 때

페이지 교체 알고리즘

페이지 부재 발생 → 새로운 페이지를 할당해야 함 → 현재 할당된 페이지 중 어떤 것을 교체할 지 결정하는 방법

1. FIFO 알고리즘

First-In-First-Out; 메모리에 먼저 올라온 페이지를 먼저 교체하는 알고리즘

victim page: out 되는 페이지는 가장 먼저 메모리에 올라온 페이지이다.
가장 간단한 방법으로, 메모리에 올라온 시간을 저장하거나 올라온 순서를 큐에 저장하여 사용한다. 특히 초기화 코드에서 적절한 방법이다.

초기화 코드: 처음 프로세스 실행될 때 최초 초기화를 시키는 역할만 진행하고 다른 역할은 수행하지 않으므로, 메인 메모리에서 빼도 괜찮다.

하지만 처음 프로세스 실행시에는 무조건 필요한 코드이므로, FIFO 알고리즘을 사용하면 초기화를 시켜준 후 가장 먼저 내보내는 것이 가능하다.

Belady's Anomaly
요구 페이징의 FIFO와 연관된 내용 중 Belady anomaly 라는 것이 있다. 흔히 생각했을 때는, 사용하는 Page frame이 많아질수록 가지고 있는 page의 개수가 많기 때문에 사용하려는 페이지가 없는 page fault 문제가 덜 발생할 것이라고 예측한다.
아래의 그림을 보자.

3개의 page frame을 사용하면 9개의 page fault가 발생한다. 하지만, 4개의 page frame으로 증가시킨 경우에는 10개의 page fault가 발생하는 것을 확인할 수 있다. (빨간색으로 표기된 곳이 page fault가 발생하는 곳이다.)

직관적으로 이해하기 힘들지만, 위의 예제를 통해 이러한 사례가 존재함을 알 수 있다. 3개의 page frame을 사용하는 경우에 4개의 page frame을 사용하는 것보다 더 적은 page fault가 발생한다.

Belady의 역설은 일반적으로 FIFO 페이지 교체 알고리즘을 사용할 때 발생하고, LRU (Least Recently Used)와 같은 알고리즘에서는 페이지 프레임이 증가함에 따라 페이지 폴트가 감소한다고 한다.

2. OPT 알고리즘

Optimal 알고리즘; 앞으로 가장 오랫동안 사용되지 않을 페이지를 우선적으로 교체하는 알고리즘

FIFO에 비해 페이지 결함의 횟수를 많이 감소시킬 수 있다. 하지만, 가장 이상적인 반면 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없기 때문에 수행하기 어려운 알고리즘이다.

3. LRU 알고리즘

Least-Recently-Used; 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘

최근 가장 오랫동안 사용하지 않았으면, 나중에도 사용되지 않을 것이라는 아이디어에서 나왔다. 시간 지역성(temporal locality) 성질을 고려한 방법이다.

시간 지역성: 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질

사용된 시간을 알 수 있는 부분을 저장하여 가장 오랫동안 참조되지 않는 데이터를 제거한다. 그래서 페이지마다 카운터가 필요하다.

카운터: 각 페이지별로 존재하는 논리적인 시계로, 해당 페이지가 사용될 때마다 0으로 clear 시킨 후 시간을 증가시켜 시간이 가장 오래된 페이지를 교체

큐로 구현이 가능한데, 사용한 데이터를 큐에서 제거하여 맨 위로 다시 올리고 프레임이 부족할 경우 맨 아래에 있는 데이터를 삭제한다.

OPT의 경우 미래 예측이지만, LRU의 경우는 과거를 보고 판단하므로 실질적으로 사용이 가능한 알고리즘이다.

OPT 보다는 페이지 결함이 더 일어날 수 있지만, 실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법 중 하나이다.

그러나, 프로세스가 주기억장치에 접근할 때마다 참조된 페이지 시간을 기록해야 하므로 막대한 오버헤드가 발생하고, 카운터나 큐, 스택과 같은 별도의 하드웨어가 필요하다는 단점도 존재한다.

4. LFU 알고리즘

Least-Frequently-Used; 과거에 참조 횟수가 가장 낮은 페이지를 교체하는 알고리즘

페이지의 참조 횟수로 교체할 페이지를 결정하는 알고리즘이다. LFU 알고리즘은 크게 2가지로 나뉘어진다.

• Incache-LFU: 메모리에 적재될 때부터 페이지의 횟수를 카운트 하는 방식
• Perfect-LFU: 메모리 적재 여부와 상관없이 페이지의 과거 총 참조 횟수를 카운트 하는 방식
  Perfect-LFU의 경우 정확하게 참조 횟수를 파악할 수 있지만 시간에 따른 참조의 변화를 반영하지 못하고, 구현이 복잡하다는 단점이 있다.

LRU는 직전 참조된 시점만을 반영하지만, LFU는 참조 횟수를 통해 장기적 시간 규모에서의 참조 성향을 고려할 수 있다. 하지만, 가장 최근에 불러온 페이지가 교체될 수도 있으며, 구현이 복잡하고 막대한 오버헤드가 있다는 단점이 있다.

5. NUR = NRU 알고리즘

Not Used Recently, Not Recently Used; 클럭 알고리즘으로 하드웨어적인 자원을 통해 기존 LRU, LFU 알고리즘의 소프트웨어적인 운영 오버헤드를 줄인 방식

클럭 알고리즘은 LRU처럼 가장 오랫동안 사용되지 않은 페이지를 대상으로 선정한다는 점에서 LRU와 근사하지만, 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 않는다.

클럭 알고리즘은 아래의 그림처럼 참조 비트(reference bit)를 순차적으로 조사하며 동작한다.
1. 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동으로 세팅된다.
2. 클럭 알고리즘은 한 바퀴 돌며 참조되지 않은 페이지의 참조 비트 값을 0으로 바꾼 후 지나간다.
3. 참조 비트가 0인 페이지를 방문하면 해당 페이지를 교체한다.

즉, 페이지가 참조되어 1이 되고, 한 바퀴 도는 동안 사용되지 않으면 0이 되고 다시 한 바퀴를 도는 동안 사용되지 않는 페이지는 참조되지 않았으므로 교체 대상 페이지로 선정하는 알고리즘이다.

클럭 알고리즘은 시계 바늘이 한 바퀴 도는 동안 걸리는 시간만큼 페이지를 메모리에 유지시켜 페이지 부재율을 줄이도록 설계 되었다. 때문에 클럭 알고리즘을 2차 기회 알고리즘이라 부르기도 한다.

교체 방식

• Global 교체: 메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식

• Local 교체: 메모리 상의 자기 프로세스 페이지에서만 교체하는 방식

다중 프로그래밍의 경우, 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있다. 따라서, 다양한 프로세스의 페이지가 메모리에 존재한다.

페이지 교체 시, 다양한 페이지 교체 알고리즘을 활용해 victim page를 선정하는데, 선정 기준을 Global로 하느냐, Local로 하느냐에 대한 차이이다.

실제로는 전체를 기준으로 페이지를 교체하는 것이 더 효율적이다. Local 프로세스 페이지에서만 교체를 하면, 교체를 해야할 때 각각 모두 교체를 진행해야 하므로 비효율적이다.

스레싱 (Thrashing)

프로그램을 과도하게 많이 띄워 놓으면 어느 순간까지는 페이지 교체를 진행하면서 CPU가 실행을 잘 하다가 성능이 급격하게 떨어지는 순간이 온다. 원인은 프로세스가 실제 실행 보다도 더 많은 시간을 페이징에 사용하고 있기 때문이다. 필요한 프로그램만 띄워서 사용해야 쾌적하게 컴퓨터를 사용할 수 있는 이유이다.

캐시 메모리 (Cache Memory)

등장 배경
메인 메모리는 CPU의 성능이 점차 증가함에 따라 CPU와의 속도 격차가 현저히 벌어지게 된다. (CPU가 훨씬 빠르다.) 즉, 메인 메모리가 CPU가 요구하는만큼 빠르게 데이터를 전달해줄 수 없어서 전체 시스템 성능의 향상은 어려워진다. 이러한 배경에서, 메인 메모리보다 접근 속도가 빠른 저장장치 '캐시'를 CPU - 메인 메모리 사이에 두어서 메인 메모리에 직접 접근하는 것이 아니라 캐시에 접근해서 데이터를 가져옴으로써 접근 속도의 향상을 이루고자 등장했다.

주기억장치에서 자주 사용하는 프로그램과 데이터를 저장해두어 속도를 빠르게 하는 메모리

• 그러므로 캐시는 주기억장치보다 크기가 작을 수 밖에 없다.

• 캐시 기억장치와 주기억장치 사이에서 정보를 옮기는 것을 사상(Mapping, 매핑) 이라고 한다.

  • 매핑의 3가지 방법
  1. 직접 매핑 (Direct Mapping)
  2. 연관 매핑 (Associate Mapping)
  3. 집합 연관 매핑 (Set Associate Mapping)

속도가 빠른 장치와 느린 장치간의 속도 차에 따른 병목현상을 줄이기 위한 범용 메모리

• 이를 위해서는 CPU가 어떤 데이터를 원하는지 어느 정도 예측할 수 있어야 한다.
• 캐시 메모리에 CPU가 이후에 참조할, 필요 있는 정보가 어느 정도 들어있느냐에 따라 캐시의 성능이 좌우되기 때문이다.

이 밖에도, 아래의 특징을 가지고 있다.

• 주기억 장치와 CPU 사이에 위치한다.
• 메모리 계층 구조에서 가장 빠른 소자이며, 처리속도가 거의 CPU의 속도와 비슷할 정도의 속도를 가지고 있다.
• 캐시메모리를 사용하면 주 기억장치를 접근하는 횟수가 줄어들어 컴퓨터의 처리속도가 향상된다.
• 캐시의 크기는 보통 수십 KByte ~ 수백 KByte이다.
  

캐시 (Cache)의 종류

1. L1 Cache: 프로세서와 가장 가까운 캐시. 속도를 위해 I$ 와 D$로 나뉜다.

• Instruction Cache (I$): 메모리의 TEXT 영역 데이터를 다루는 캐시
• Data Cache (D$): TEXT 영역을 제외한 모든 데이터를 다루는 캐시

2. L2 Cache: 용량이 큰 캐시. 크기를 위해 L1 캐시처럼 나누지 않는다.

3. L3 Cache: 멀티 코어 시스템에서 모든 코어가 공유하는 캐시

오늘날 CPU 칩의 면적 30~70%는 캐시가 차지한다.

캐시 (Cache)의 지역성 (Locality)

기본적으로 컴퓨터 시스템 내부의 정보들은 메인 메모리와 같은 저장장치에 저장이 된다. 메인 메모리와 CPU의 속도의 차이 때문에 생기는 문제를 해결하기 위해 캐시를 사용한다고 했다. 그렇다면, 캐시 안에 메인 메모리에 있는 정보들이 들어 있어야 한다. 하지만, 메인 메모리에 비해 캐시는 접근 속도는 높지만 저장용량의 크기는 낮다. 즉, 캐시에 저장할 수 있는 데이터의 양은 한정적이며 효율적인 캐시 활용을 위해서 메인 메모리에서 자주 사용되는 데이터들을 선별할 수 있어야 함을 의미한다. 이러한 상황에서, 데이터의 지역성을 이용하게 된다. 데이터의 지역성이란, 프로그램이 참조하는 코드나 데이터에 대해 지역성을 가짐을 의미한다.

• 캐시가 효율적으로 동작하려면, 캐시의 적중률(Hit-rate)를 극대화 시켜야 한다.
• 캐시에 저장할 데이터가 지역성(Locality)을 가져야 한다.
• 지역성이란, 데이터 접근이 시간적 혹은 공간적으로 가깝게 일어나는 것을 의미한다.
• 지역성의 전제 조건으로 프로그램은 모든 코드나 데이터를 균등하게 Access 하지 않는다는 특성을 기본으로 한다.

즉, 지역성이란 기억장치 내의 정보를 균일하게 Access하는 것이 아닌 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성이다.

지역성의 종류

1. 시간적 지역성

• 특정 데이터가 한번 접근되었을 경우, 가까운 미래에 또 한번 데이터에 접근할 가능성이 높은 것
• 메모리 상의 같은 주소에 여러 차례 읽기 쓰기를 수행할 경우
  for, while 같은 반복문을 예시로 들 수 있다. 특정 부분을 반복해서 접근하기 때문에 다시 참조할 확률이 높다.

2. 공간적 지역성
캐시 지역성이란 지금 참조하는 메모리 주변을 다음에도 참조할 확률이 높다는 원리이다.

• 특정 데이터와 가까운 주소가 순서대로 접근되었을 경우를 말한다.
• CPU 캐시나 디스크 캐시의 경우 한 메모리 주소에 접근할 때 그 주소뿐 아니라 해당 블록을 전부 캐시에 가져오게 된다. 즉, 앞으로 사용할 데이터들이 블록 안에 많이 모여있는 것을 뜻한다.
• 필요한 데이터들이 모여있다면 한번만 메모리에 접근해도 필요한 데이터들을 많이 가져올 수 있을 것이고, 흩어져 있다면 catch miss가 날 확률이 높아질 것이므로 효율성이 떨어지게 될 것이다.
  배열을 예시로 들 수 있다. A[0], A[1]과 같은 연속 접근의 경우 그 다음 원소들에 접근할 가능성이 높다.
  

캐시 Hit, 캐시 Miss

CPU에서 요청한 데이터가 캐시 내에 존재한다면 이를 Cache Hit이라고 한다. 캐시 내에 존재하지 않아서 메인 메모리를 통해 가져와야 한다면 이를 Cache Miss라고 한다.

이에 대해 Hit Ratio, Miss Ratio를 정의할 수 있는데, 이는 아래와 같다.

Hit Ratio = (Cache Hit 횟수 / 전체 요청 횟수) * 100
Miss Ratio = 1 - Hit Ratio

캐시 미스가 발생하게 되면, (cache access time + main memory access time)이 소요되므로, CPU가 요청하는 족족 캐시 미스가 발생하면 안 쓰느니만 못하다.

하지만 Miss Ratio가 대부분의 경우에서 높지 않기 때문에, 캐시를 사용하면 일반적으로 시스템 성능을 크게 향상시킬 수 있다.

Caching Line

위에서 언급했듯이, CPU에서 요청한 데이터가 Cache Hit 했다고 해보자. 그런데 어떻게 Cache Hit 했음을 알 수 있을까? Cache의 모든 데이터를 다 뒤져서 "아! 찾았다!" 했을까?

실제로 이렇게 Brute하게 탐색하면 캐시 탐색 시간이 생각보다 오래 소요될 것이다.

캐시는 CPU 가까이에 위치하면서 빈번하게 사용되는 데이터를 저장하는 장소이다. 캐시 메모리는 메인 메모리에 비해 크기가 매우 작기 때문에 메인 메모리와 1:1 매칭이 불가능하다. 캐시가 아무리 가까이 있더라도 찾고자 하는 데이터가 어느 곳에 저장되어 있는지 몰라 모든 데이터를 순회해야 한다면 시간이 오래 걸리게 된다. 즉, 캐시에 목적 데이터가 저장되어 있다면 바로 접근하여 출력할 수 있어야 캐시가 의미 있어진다는 것이다.

그렇기 때문에 캐시에 데이터를 저장할 때 특정 자료구조를 사용하여 묶음으로 저장하게 되는데 이를 캐싱 라인이라고 한다. 다양한 주소에 있는 데이터를 사용하므로 빈번하게 사용하는 데이터의 주소는 흩어져 있다. 따라서 캐시에 저장하는 데이터에는 데이터의 메모리 주소 등을 기록해 둔 태그를 달아놓을 필요가 있다. 이러한 태그들의 묶음을 캐싱 라인이라고 하고 메모리로부터 가져올 때도 캐싱 라인을 기준으로 가져온다. 즉, 캐시에 있는 정보를 요청했을 때 바로 매핑시켜줄 수 있도록 한다는 것이다. 종류로는 대표적으로 세 가지 방식이 존재한다.

1. 직접 매핑 (Direct Mapping)

메인 메모리의 주소 : 캐시 메모리의 주소 = N : 1

메인 메모리를 일정한 크기의 블록으로 나누어 각각의 블록을 캐시의 정해진 위치에 매핑하는 방식이다. 가장 간단하고 구현도 쉽다.
하지만 적중률(Hit rate)가 낮아질 수 있다. 또 동일한 캐시 메모리에 할당된 여러 데이터를 사용할 때 충돌이 발생하게 되는 단점이 있다. (같은 캐시 메모리의 주소를 갖는 2개의 데이터가 반복/교차적으로 요청된다면 무한 캐시 교체가 일어날 수도 있다.)

2. 연관 매핑 (Associative Mapping)
직접 매핑 방식의 단점을 보완한 방식으로, 캐시 메모리의 빈 공간에 마음대로 주소를 저장하는 방식이다. 저장하는 것은 매우 간단하지만, 원하는 데이터가 있는지 찾기 위해서는 모든 태그를 병렬적으로 검사해야 하기 때문에 복잡하고 비용이 높다는 단점이 있어서 거의 사용하지 않는다.

3. 집합-연관 매핑 (Set-Associative Mapping)
Direct Mapping과 Associative Mapping의 장점을 결합한 방식이다.
빈 공간에 마음대로 주소를 저장하되, 미리 정해둔 특정 행에만 저장하는 방식이다. 특정 데이터가 k-way만큼 할당 가능한 캐시 인덱스를 가지고 있다. 즉, Cache Hit 여부를 판단하려면 k개의 블록을 체크하면 된다.

Direct에 비해 검색 속도는 느리지만 저장이 빠르고 Full에 비해 저장이 느리지만 검색이 빠르다. 주로 사용하는 방식이다.

Cache Miss

캐시 미스 (Cache Miss)는 CPU가 참조하려는 데이터가 캐시 메모리에 없을 때 발생한다.

1. Compulsory Miss
특정 데이터에 처음 접근할 때 발생하는 cache miss이다.

2. Capacity Miss
캐시 메모리의 공간이 부족해서 발생하는 cache miss이다.

3. Conflict Miss
캐시 메모리에 A와 B 데이터를 저장해야 하는데, A와 B가 같은 캐시 메모리 주소에 할당되어 있어서 발생하는 cache miss이다. direct mapped cache에서 많이 발생한다.

파일 시스템

파일(File)은 논리적인 저장 단위로, 관련된 정보 자료들의 집합에 이름을 붙인 것이다. 컴퓨터 시스템의 편리한 사용을 위해 정보 저장의 일괄된 논리적 관점을 제공한다. 일반적으로 레코드(Record) 혹은 블록(Block) 단위로 비휘발성 보조기억장치에 저장된다.

파일 속성(File attribute) 또는 파일의 메타데이터(metadata)는 파일을 관리하기 위한 각종 정보들이다. 파일 자체의 내용은 아니다. 파일 이름, 유형, 저장된 위치, 파일 사이즈, 접근 권한, 소유자, 시간(생성/변경/사용) 등 파일에 대한 전반적인 정보를 말한다.

파일 시스템(File System)은 운영체제와 모든 데이터, 프로그램의 저장과 접근을 위한 기법을 제공한다. 시스템 내의 모든 파일에 관한 정보를 제공하는 계층적 디렉터리 구조이고, 파일 및 파일의 메타데이터, 디렉터리 정보 등을 관리한다.

파티션은 연속된 저장 공간을 하나 이상의 연속되고 독립적인 영역으로 나누어 사용할 수 있도록 정의한 규약이다. 하나의 물리적 디스크 안에 여러 파티션을 두는 게 일반적이지만, 여러 물리적 디스크를 하나의 파티션으로 구성하기도 한다.

Access Methods

시스템이 제공하는 파일 정보의 접근 방식으로는 순차 접근(Sequential Access)과 직접 접근(Direct Access, Random Access), 색인 접근(Index Access)로 나뉜다.

1. 순차 접근 (Sequential Access)
가장 단순한 방법으로 파일의 정보가 레코드 순서대로 처리된다. 카세트테이프를 사용하는 방식과 동일하다. 현재 위치에서 읽거나 쓰면 offset이 자동으로 증가하고, 뒤로 돌아가기 위해선 되감기가 필요하다.

2. 직접 접근 (Random Access)
파일의 레코드를 임의의 순서로 접근할 수 있다. LP 판을 사용하는 방식과 동일하다. 읽기나 쓰기의 순서에 제약이 없으며 현재 위치를 유지할 수 있다면 이를 통해 순차 접근 기능도 구현할 수 있다.

3. 색인 접근 (Index Access)
파일에서 레코드를 찾기 위해 색인을 먼저 찾고 대응되는 포인터를 얻는다. 이를 통해 파일에 직접 접근하여 원하는 데이터를 얻을 수 있다. 따라서 크기가 큰 파일에서 유용하다.

Directory

디렉터리(Directory)는 파일의 메타데이터 중 일부를 보관하고 있는 일종의 특별한 파일이다. 해당 디렉터리에 속한 파일 이름과 속성들을 포함하고 있고, 다음과 같은 기능들을 제공한다.

• 파일 찾기(Search)
• 파일 생성(Create)
• 파일 삭제(Delete)
• 디렉터리 나열(List)
• 파일 재명명(Rename)
• 파일 시스템 순회(Traverse)

디렉터리는 어떻게 구성되어야 할까? 기본적으로 디렉터리 파일을 빠르게 탐색할 수 있어야 할 것이다. 또 적절한 이름으로 사용자들이 편리하게 사용할 수 있으면 좋을 것이다. 그리고 파일들을 적절한 분류로 그룹화해두면 사용하기 편리할 것이다. 이를 위해 디렉터리의 논리적 구조를 정의하는 여러 방법들이 있다.

1. 1단계 디렉터리 (Single-Level Directory)
1단계 디렉터리는 모든 파일들이 디렉터리 밑에 존재하는 형태이다. 파일들은 서로 유일한 이름을 가지고 서로 다른 사용자라도 같은 이름을 사용할 수 없다. 지원하기도 쉽고 이해하기도 쉽지만, 파일이 많아지거나 다수의 사용자가 사용하는 시스템에서는 심각한 제약을 갖는다.

2. 2단계 디렉터리 (Two-Level Directory)
2단계 디렉터리는 각 사용자별로 별도의 디렉터리를 갖는 형태이다.

UFD: 자신만의 사용자 파일 디렉터리
MFD: 사용자의 이름과 계정 번호로 색인되어 있는 디렉터리이다. 각 엔트리는 사용자의 UFD를 가리킨다.

서로 다른 사용자가 같은 이름의 파일을 가질 수 있고 효율적인 탐색이 가능하다. 하지만 그룹화가 불가능하고, 다른 사용자의 파일에 접근해야 하는 경우에는 단점이 된다.

3. 트리 구조 디렉터리(Tree-Structured Directory)
사용자들이 자신의 서브 디렉터리(Sub-Directory)를 만들어서 파일을 구성할 수 있다. 하나의 루트 디렉터리를 가지며 모든 파일은 고유한 경로 (절대 경로/상대 경로)를 가진다.

Reference

https://velog.io/@codemcd/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-16.-%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://gyoogle.dev/blog/computer-science/operating-system/Page%20Replacement%20Algorithm.html
https://melonicedlatte.com/2020/10/13/003700.html
https://dar0m.tistory.com/270
https://rebro.kr/180
https://nukw0n-dev.tistory.com/9