KOCW_File System

✅ File and File System

named collection of related inforamtion

• 일반적으로 involataile 보조기억장치에 저장(Harddisk에 저장)
• file은 이름으로 접근(🆚 메모리는 주소로 접근)
• OS는 다양한 저장장치를 file이라는 동일한 논리적 단위로 볼 수 있게 해 줌
• File Operation
  • create
  • read
  • write
  • reposition(lseek): 파일 내 장소를 포인터로 가리킴(현재 수정하고 있는 부분)
  • delete
  • open: File attribute를 메모리에 올려놓기
  • close 등

☑️ File attribute(metadata)

metadata of file

• 파일 자체의 내용 ❌
• 파일을 관리하기 위한 각종 정보
  • 파일 이름, 유형, 저장 위치, 파일 사이즈
  • 접근 권한(read, write), 시간(생성/변경/사용), 소유자 등

☑️ File System

• 운영체제에서 파일을 관리하는 부분
• file, file attribute, directory info 관리
• 파일의 저장 방법 결정
• 파일 보호 등

✅ Directory and Logical Disk

☑️ Directory

• 파일의 metadata 중 일부를 보관하고 있는 일종의 특별한 파일
• 그 디렉토리에 속한 파일 이름 및 파일 attribute

일반 파일: 파일 내용
Directory 파일: 그 Directory 안에 존재하는 파일들의 metadata 저장

• Directory Operation
  • search for a file
  • create a file
  • delete a file
  • list a directory: 그 Directory내에 있는 파일 뭐가 있는지
  • rename a file: 그 Directory내에 있는 파일 이름 바꾸기
  • traverse the file system: 파일시스템 전체 탐색

☑️ Partition(Logical Disk)

• 하나의 physical 디스크 안에 여러 partition을 두는 것이 일반적이다
• 여러 개의 물리적 디스크를 하나의 partition으로 구성하기도 함
• physical 디스크를 partition으로 구성한 뒤
• 각각의 partition에 file system을 깔거나, swapping 등 다른 용도로 사용 가능

📍 File Operation Open

• 파일의 metadata를 디스크에서 메모리에 올려두기
• system call의 일종

--- 디스크로부터 파일 c의 metadata를 메모리로 가지고 오는 과정 ---

open("a/b/c") system call
CPU제어권이 OS에게 넘어감
process A의 PCB

directory path를 search
root의 metadata를 열면, file a 의 위치 획득
root directory /를 open하여 그 안에서 파일 a위치 획득

file a를 open하고 read하여 파일 b의 위치 획득
file b를 open하고 read하여 파일 c의 위치 획득
open file c
return fd: file descriptor

이 때 바로 프로세스에게 전달하는게 아니라
OS한테 먼저 저장하고, 복사해서 전달
Buffer caching: 그래서 나중에 다른 프로세스가 같은 파일을 요청하면, OS에 있는 값을 복사해서 전달

• 👎🏻 Directory path의 search에 시간이 너무 오래 걸림

  • open을 read, write와 별도로 두는 이유이다
  • 한번 open한 파일은 read, write시 directory search불필요
• ✔️ Open file table
• 현재 open된 파일들의 metadata 보관소(in memory)
• 디스크의 metadata보다 몇 가지 정보 추가
  • open한 프로세스의 수
  • file offset: 파일의 어느 위치를 접근 중인지 표시(별도 테이블 필요)

• system wide open file table: 시스템에 open file table한 개

• ✔️ File descriptor
• file handle, file control block
• open file table에 대한 위치 정보(프로세스 각각 가지고 있는 테이블)
• per process file descriptor table: 프로세스마다 metadata를 가지고 있는 테이블

✅ Buffer caching

• OS가 이전에 파일에서 읽어온 값을 buffer cache에 저장해 두었다가
• 똑같은 요청이 들어오면 buffer cache에서 전달
• 파일 요청은 OS에게 무조건 system call을 통해 CPU제어권이 넘어 오기 때문에
• buffer cache에 대한 LRU는 구현 가능
• 🆚 memory에서는 page에 대한 정보를 OS가 다 가지고 있지 않았기 때문에 LRU는 구현 불가능했음, clock algorithm썼음

✅ File Protection

• 각 파일에 대해 누구에게 그리고 어떤 유형의 접근 read, write, execution을 허락할 것인가?

☑️ Access Control 방법 3가지

• 1️⃣ Access Control Matrix

• 행렬에 사용자, 파일을 정렬해놓고 권한 정리
• 👎🏻 행렬 칸을 모두 만들어야 하니 비효율적

• 💊 Access Control List, Capability를 linked list로 구현

• Access Control List: 파일별로 누구에게 어떤 접근권한이 있는지 표시(하나의 file만 linked list로 구현)

• Capability: 사용자별로 자신이 접근 권한을 가진 파일 및 해당 권한 표시(하나의 user만 linked list로 구현)

• 2️⃣ Grouping
• 전체 user을 owner, group, public세 그룹으로 구분
• 각 파일에 대해 세 그룹의 접근 권한 rwx를 3비트씩으로 표시

• UNIX에서 사용하는 방식, 일반적으로 많이 사용하는 방식

• 3️⃣ Password
• 파일마다 Password를 두는 방법(디렉토리 파일에 Password 두는 방법도 가능)
• 모든 접근 권한에 대해 또 하나의 Password(all or nothing)
• 👎🏻 접근 권한 별 Password: 암기 문제, 관리 문제

✅ File System의 mounting

• 하나의 physical disk를 partition을 통해 logical disk로 나눌 수 있다
• 각각의 logical disk에는 file system을 설치해서 사용
• 🧐 Disk1에서 Disk 2, 3번은 어떻게 접근하지?

• root system의 특정 디렉토리 이름에 또다른 partition의 file system을 mount
• 그러면 Disk1에서 Disk2의 file system에 접근할 수 있게 된다.

✅ Disk Access Methods

• 시스템이 제공하는 파일 정보의 접근 방식

• ✔️ Sequential Access
• 카세트 테이프처럼 순서가 있음 1~n 으로 들어야 함
• 건너뛰기 불가능 ❌
• 1번 노래 듣고 5번 노래 듣고 싶으면 2, 3, 4를 듣고 5번 들을 수 있음

• 읽거나 쓰면 offset은 자동적으로 증가

• ✔️ Direct Access, Random Access
• 레코드판처럼 접근
• 건너뛰기 가능 ⭕️
• 파일을 구성하는 레코드를 임의의 순서로 접근 가능
• 1번 노래 듣고 5번 노래로 바로 접근 가능

✅ Allocation of File Data in Disk

• disk에 파일을 저장하는 방법
• 파일을 같은 크기로 쪼개서, 어떻게 업로드할까?

☑️ Contiguous Allocation

• 분할된 파일이 연속해서 저장
• 예를 들어 메일은 19~24번까지 length 6으로 저장
• directory: 파일에 대한 메타데이터, 위치 정보, 크기 등 저장

• 👎🏻 external fragmentation
• 👎🏻 file grow가 어려움
  • 파일은 수정하면서 크기가 바뀔 수 있음
  • 파일의 크기가 커질 수 있기 때문에 file grow 가능
  • file 생성 시 얼마나 큰 hole을 배당할 것인가? 빈 공간을 얼마나 할당해 둘 것인가?
  • internal fragmentation, 공간 낭비

• 👍🏻 Fast I/O
  • 한번의 seek/rotation으로 많은 data transfer 가능
  • disk head rotation이 한번 이동하는 동안 많은 데이터를 받아올 수 있다
  • realitime file용으로
  • 이미 run중인 프로세스의 swapping용으로 사용
• 👍🏻 Direct Access(🟰 random access) 가능 ⭕️
  • mail의 5번째 data를 보고 싶으면 19+4하면 끝!

☑️ Linked Allocation

• disk의 빈 위치면 아무 곳에나 파일을 쪼개서 집어 넣음
• 그리고 그 쪼개진 파일들이 어디 저장되어 있는지 link해서 저장
• directory: 파일의 시작 위치만 가지고 있고
• 그 파일에 가면 그 다음 파일 위치를 알 수 있다

• 👍🏻 external fragmentation 발생하지 않음
  • disk의 남는 공간이 없음
• 👎🏻 Direct Access(🟰 random access) 불가능 ❌
  • 특정 파일의 특정 위치를 보고 싶으면, 처음부터 일일이 따라가봐야 함
  • 순차접근만 가능하다
• 👎🏻 순차접근만 가능하다보니 disk head가 많이 이동해야 해 비효율적
• 👎🏻 reliability문제
  • 한 sector이 고장나 pointer가 유실되면 많은 부분을 잃음

• 👎🏻 pointer을 위한 공간이 block의 일부가 되어 공간 효율성 감소

  • 보편적으로 각 pointer는 512KB이고 block은 4KB
  • 따라서 data를 저장할 수 있는 공간이 512 - 4
• ✔️ Linked Allocation 변형 FAT
• FAT(File Allocation Table) 시스템
• 포인터를 별도의 위치에 보관하여 reliability와 공간효율성 문제 해결

☑️ Indexed Allocation

• directory: index block의 위치를 담고 있다
• index block: 각 파일들이 어디있는지 위치를 저장해 둔 block
• index block에는 파일 내용이 들어있는게 아니고❌ 위치 정보만 들어있음

• 👍🏻 Direct Access(🟰 random access) 가능 ⭕️
  • index block을 살펴보면 바로 데이터 접근 가능

• 👍🏻 external fragmentation 발생하지 않음

• 👎🏻 small file의 경우 공간 낭비(실제로 많은 file은 작다)

• 👎🏻 too large file의 경우 하나의 block으로 index를 저장하기 부족

• ✔️ 해결방안
  • linked scheme: too large file이라서 하나의 block안에 다 저장못하고 넘어가면 다음 block에 연결
  • multi level index

📌 UNIX File System

Inode List에 파일 이름을 저장한 대부분의 메타 데이터 저장

• ✔️ Boot Block: 부팅에 필요한 정보, bootstrap loader
  • OS의 kernel에 file system 올리기
• ✔️ Super Block: 파일 시스템에 광한 총체적인 정보
  • 어디가 빈 block, 어디가 사용중인 block인지
• 🌟 Inode List: 파일 이름을 제외한 파일의 모든 메타 데이터 저장
  • directory와 함께 파일의 메타데이터 저장
  • 파일의 이름은 directory가 가지고 있고,
  • inode는 나머지 파일의 owner, timestamp…등 메타데이터 보관
• ✔️ Data Block: 파일의 실제 내용 보관

• indexed allocation사용
• inode의 크기는 동일 사이즈로 고정
• direct index를 가지고 파일의 위치 표현
• indirect index를 가지고 위치를 찾으면 또 파일의 위치 표현, 결국 파일 데이터 접근 가능

• double index: 따라가면, 파일 위치를 가리키는 인덱스가 있고, 또 따라가면 데이터 접근

• 👍🏻 파일 크기에 맞게 index를 사용해서 공간 효율성을 극대화
• 대부분 파일은 크기가 작음 ➡️ inode list로 충분히 커버 가능
• 하지만 가끔 큰 파일도 있음 ➡️ indirect index, double index를 사용하여 구현

📌 FAT File System

FAT에 메타데이터 중 위치정보만 보관, 나머지 메타데이터는 directory에 보관

• ✔️ Boot Block: 부팅과 관련된 정보
• 🌟 FAT: 파일의 메타데이터 중 일부위치정보만 FAT에 보관
  • 나머지 메타데이터는 directory에 보관
  • 일종의 배열로 이루어져 있음
• ✔️ Root Directory:

• ✔️ Data Block:

• linked allocation을 사용
• 그러나 파일의 다음 위치를 알기 위해서는 파일에 접근하는게 아니라
• FAT에 접근해야 알 수 있다는 차이점이 있다
• FAT에 위치정보를 저장하기 때문이다

• FAT만 봐서는 어떤 파일인지, 크기는 어떤지 등의 정보는 알 수 없음

• linked allocation의 단점을 모두 극복하는 FAT
• 👍🏻 직접 접근 random access가 가능하다
• 👍🏻 reliability문제 해결
  • 하나의 sector이 고장나도 FAT에 위치 정보가 중복되어 저장되어 있으므로 유실 ❌

• 👍🏻 512KB를 모두 활용 가능

• ❓ 위치정보를 FAT에 보관하는 이유
• directory에 보관하면 위의 linked allocation에서처럼 일부 sector이 고장나면 나머지도 유실되는 문제가 있음
• 따라서 directory에는 파일의 시작 위치만 보관
• 그 다음 데이터에 접근하기 위해서는 FAT에 가서 데이터 참조
• EOF: 파일이 끝났음을 의미

✅ Free Space Management

아까 contiguous allocation에서처럼
데이터가 할당되지 않고 비어있는 메모리는 어떻게 관리할까?

☑️ Bit map or bit vector

• 각각의 block별로 숫자가 있음
• 그 block마다 bit를 두어서 free or occupied 표시

• 그 bit들을 다 모아둔 것을 bit map

• bit[i]

  • 0 : free, 저장된 데이터 없음
  • 1: occupied, 데이터 저장 되어 있음
• 👍🏻 연속적인 n개의 free block를 찾는데 효과적
• 👎🏻 bit map을 위한 부가적인 공간이 필요함

☑️ Linked List

• 비어있는 free block를 연결을 해 두고
• pointer을 둬서 다음 free block을 가리키도록 한다
• 맨 처음 free block의 위치만 알고 있으면 굄
• 👍🏻 부가적인 공간이 필요가 없으므로, 공간 낭비가 없다
• 👎🏻 연속적인 가용 공간 찾기가 어렵다
• 👎🏻 Disk head가 많이 돌아야 가용공간 찾을 수 있음
• 👎🏻 link가 유실되면 뒤의 free block을 모르게 됨

☑️ Grouping

• linked list방법의 변형
• 첫 번째 free block이 n개의 pointer를 가진다
• n-1 pointer는 free data block을 가리킴
• 만약 하나의 free block이 빈 공간을 다 가리키지 못한다면

• 마지막 pointer가 가리키는 block은 또 다시 n pointer을 가진다

• 👎🏻 연속적인 가용 공간 찾기가 어렵다

☑️ Counting

• 프로그램들이 종종 여러개의 연속적인 block을 할당하고 반납한다는 성질에서 고안된 방법
• first free block, number of contiguous free blocks를 유지한다

• 예시: 1번 블럭부터, 4개가 비어있다

• 👍🏻 연속적인 free block찾기가 쉽다

✅ Directory Implementation

Directory: 그 Directory안에 있는 metadata를 보관하는 특별한 파일

☑️ Linear List

• <file name, file의 metadata>의 list
• 파일 이름을 찾으면, metadata도 찾을 수 있음
• 👍🏻 구현 간단
• 👎🏻 directory내에 파일이 있는지 찾기 위해서는 일일이 linear search 필요
• 👎🏻 time consuming

☑️ Hash Table

• linear list ➕ hashing
• hash table은 file name을 이 파일의 linear list의 위치로 바꾸어줌
• Hash함수를 적용하면 특정 범위 내로 값이 도출, 이 결과값에 해당하는 엔트리에 metadata 저장
• 👍🏻 search time을 없앰
  • 순차적으로 찾을 필요가 없고
  • Hash함수로 특정 범위 내에 값들이 있을테니까, 검색 용이
• 👎🏻 collision 발생 가능

☑️ File의 metadata 보관 위치

• 파일의 metadata 중 일부는 directory가 직접 가지고 있고

• 나머지는 directory에는 포인터만 두고 다른 곳에 보관

• inode(UNIX)
• FAT

☑️ Long file name의 지원

• 긴 파일 이름을 저장하는 방식
• <file name, file의 metadata>의 list에서 각 entry는 일반적으로 고정된 크기이다
• 그런데 file name은 고정 크기보다 길어질 수 있음
• file name이 고정 크기의 entry보다 길어지는 경우,
• 💊 entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 pointer를 둔다
• 이름의 나머지 부분은 동일한 directory 파일의 일부에 둔다

✅ VFS, NFS

다양한 파일 시스템 또는 원격 파일 시스템 접근

☑️ Virtual File System

• file system 종류는 아주 다양한
• 사용자가 서로 다른 다양한 file system에 접근하더라도
• 동일한 system call interface API를 통해 접근할 수 있게 해주는 OS layer
• file system 종류와는 상관 없이 VFS를 통해 동일한 system call 가능

☑️ Network File System

• 원격에 저장된 파일 접근
• 분산 시스템에서는 네트워크를 통해 파일 공유 가능
• NFS는 분산 환경에서의 대표적인 파일 공유 방법
• RPC: remote procedure call
  • one computer to execute functions on another computer over a network as if they were local

✅ Page Cache and Buffer Cache

• 프로세스가 파일 I/O필요함
• OS에게 system call, 파일 I/O요청
• 프로세스는 CPU제어권을 잃고, OS에게 넘어감
• OS는 파일 I/O를 해 온 결과를 kernel영역의 buffer cache에 저장
• buffer cache에 저장된 내용을 복사하여 사용자 메모리 영역의 page cache에 저장

• 나중에 같은 파일에 대한 요청이 들어오면 buffer cache에서 가져옴

• page cache에는 당장 사용되는 프로세스 일부분인 page를 swap area에서 page cache에 올려놓기

☑️ Page Cache

• page(현재 필요한 프로세스 부분)에 대한 데이터를 page cache에 보관
• virtual memory의 paging system에서 사용하는 page frame을 caching의 관점에서 설명하는 용어

• memory mapped I/O를 쓰는 경우 file I/O에서도 page cache사용

• TLB miss가 났을 때만 OS가 page에 대한 정보를 얻을 수 있어서
• OS가 page cache에 대한 정보를 반만 얻을 수 있음
• 따라서 LRU, LFU 불가능, clock algorithm사용

☑️ Memory-Mapped I/O

• 원래는 system call을 통해 file을 read/write하는데
• 그 대신 file의 일부를 virtual memory에 mapping시키는 방식
• (그림에서 검정색 부분들이 mapped된 영역)
• 매핑시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 함

• system call없이 파일I/O가 가능

• 사용자 프로그램이 read/write하면 mapped되어 있으므로 file system에 반영됨
• 사용자 프로그램이 file을 read/write하려고 했는데 아직 file이 mapped되어있지 않으면 page fault가 나지만,

• swap area에서 찾아오는게 아니라 file system에서 찾아오게 된다

• ❓ 파일I/O를 하는 두 가지 방법은?
• 1️⃣ system call
• 2️⃣ Memory-Mapped I/O

☑️ Buffer Cache

• 파일에 대한 데이터를 buffer cache에 보관했다가 같은 요청시 사용
• 파일 시스템을 통한 I/O연산은 메모리의 특정 영역인 buffer cache사용
• file사용의 locality활용
  • 한번 읽어온 block에 대한 후속 요청 시 buffer cache에서 즉시 전달
• 모든 프로세스가 공용으로 사용
• replacement algorithm필요

• (LRU, LFU)

• file I/O를 위해서는 system call을 통해 OS에게 제어권이 넘어오게 되기 때문에
• OS가 buffer cache에 대한 정보를 모두 가지고 있음

• ➡️ LRU, LFU가능

• 🆚 page cache
• ✔️ page cache:
  • 현재 프로세스 중 사용될 page를 보관
  • OS는 page에 대한 정보를 다 가지고 있지 않음, clock algorithm사용
• ✔️ buffer cache:
  • 파일에서 읽어온 데이터를 보관
  • OS는 buffer cache에 대한 정보를 다 가지고 있어 LRU, LFU가능

☑️ Unified Buffer Cache

• 최근의 OS에서는 기존 buffer cache가 page cache에 통합됨
• linux

• ✔️ Unified Buffer Cache 사용하지 않는 file I/O
• system call인 경우
• read/write 요청
• buffer cache로 읽어들이고
• 있으면 buffer cache를 page cache에 복사

• 없으면 file system에서 읽어옴

• Memory-Mapped I/O인 경우라면
• 프로세스가 자신의 page cache에 데이터를 read/write하면
• buffer cache를 통과해

• file system에 반영

• ✔️ Unified Buffer Cache 사용하는 file I/O
• buffer cache를 page cache에 복사하는 과정이 없음
• Memory-Mapped I/O인 경우라면
• buffer cache를 통과할 필요 없이 바로 mapping가능
• 따라서 한 단계를 줄일 수 있다

🎯 프로그램 address space의 code

• code는 Memory-Mapped I/O의 대표적인 예시이다

프로그램이 실행되면
각 프로그램마다 virtual memory의 address space를 가지고
현재 실행에 필요한 부분만 메모리에 load
나머지는 swap area에 내려가 있는다고 배웠음

• address space중 code는 이미 실행 파일로 존재하기 때문에
• swap area애 내려가 있는게 아니라
• file system안에 저장되어 있고
• Memory-Mapped I/O를 통해 불러오게 됨

✅ Ext2

• 최근에는 Ext4가 많이 쓰이는데, 그 근간이 되는 file system
• inode: 파일의 메타데이터 저장
• pointer이 파일이 디스크에 어디 있는지 위치를 가리킨다
• indirect pointer를 쓰면 더 큰 파일을 지원

• 기존 UNIX파일 시스템에 비해 Ext2는 block을 사용해 그룹화한다는 점이 개선됨
• block의 그룹화: 메타데이터와 실제 데이터를 가까이 위치시켜서 disk head의 이동을 최소화한다
• 하나의 block안에 데이터의 메타데이터, 실제 데이터를 넣어서 가깝게!

• 👍🏻 디스크 탐색 시간 감소

• 슈퍼블록의 중복저장

• 👍🏻 슈퍼블록을 그룹마다 중복저장하여 디스크 오류에 대비, 신뢰성을 높인다

• ✔️ Group Descriptor
• 각 block으로 만든 그룹에 대한 정보를 담고 있는 블록
• 데이터블록 비트맵의 시작 위치, 아이노드 비트맵의 시작 위치 등

• 첫 번째 아이노드의 시작 주소, 가용 아이노드의 수

• ✔️ Data block bitmap

• 사용중인 데이터블록인지, 비어있는 데이터블록인지 비트로 표시

• ✔️ Inode bitmap

• 사용중인 아이노드인지, 비어있는 아이노드인지 비트로 표시

• ✔️ Inode table
• 실제 아이노드의 저장 위치

✅ Ext4

Ext2 ➕ 저널링 기술

• 최근 가장 많이 사용되는 file system
• 더 많은 데이터 저장하는 방향으로 저장되어 있음

☑️ Journaling

• ⚠️ 갑작스런 전원 공급 중단 시 파일시스템 일관성 훼손inconsistency 발생 가능
• 그림처럼 웃는것도 리본도 아닌 이상한 이미지가 된다.
• buffer cache는 휘발성이기 떄문이다
• 💊 Journaling

• Journaling을 통해 신뢰성을 향상한다

• 데이터가 수정되면
• 데이터가 쫒겨날 때 저장하는게 아니라 ❌
• 5~30초 단위로 버퍼캐시에서 수정된 내용을 저널 영역에 기록한다
• 단, Journaling은 수정된 내용을 저널 영역에 저장
• 그리고 나중에 file system원래 위치에 반영(더 오랜 주기로 반영)

- ✔️ Journaling
- 30초 단위로 수정 내용을 저널 영역에 저장

- ✔️ Checkpointing
- 5분 단위로 수정된 내용을 파일시스템의 원래 위치에 반영

• ✔️ 메타데이터 저널링 모드

• 메타데이터만 저널링
• Journaling주기가 도래하면 데이터를 파일시스템에 저장 후
• 메타데이터를 저널영역에 기록
• Checkpointing 주기가 도래하면 메타데이터를 파일 시스템에 반영
• 👍🏻 crash 발생 시 파일 시스템 자체가 깨어지는 것 방지

• 👎🏻 메타데이터가 아닌 일반 데이터의 일부는 훼손 가능

• ✔️ 메타데이터와 일반 데이터를 모두 저널링 -Journaling주기가 도래하면 데이터와 메타데이터 모두 저널 영역에 기록
• Checkpointing 주기가 도래하면 데이터와 메타데이터를 파일 시스템에 반영
• 👍🏻 crash 발생 시 데이터 자체의 복구 보장

✅ Buffer cache 교체 알고리즘

• LRU의 단점: 가장 마지막 시점에 사용된 것만 고려, 횟수는 고려하지 않음
• LFU의 단점: 사용 시점은 고려하지 않음

✅ LRFU 알고리즘

• 캐시블록 x 중 그 가치평가 값 Value(x)가 제일 적은 블록 삭제
• LFU의 성질: 과거의 모든 참조기록이 현재 시점의 블록 가치 계산에 합산
• LRU의 성질: p<1이므로 p의 델타제곱값은 감소함수(즉, 델타의 값이 작을수록 p의 델타제곱은 커짐)

• 최근 참조일수록 블록의 가치평가에 대한 기여도가 크다

• 즉, 최근에 사용된 기록은 가치평가에 크게 반영, 예전에 사용된 기록은 적게 반영해 블록의 가치를 평가하고, 이 평가 결과가 낮으면 쫒아냄

• 👎🏻 Space overhead
• 블록의 사용 시점, 횟수에 대해 과거에 대한 모든 정보를 가지고 있어야 함
• 👎🏻 Time overhead
• 블록 replacement가 필요할 때 각 블록의 가치를 평가해야 함

☑️ Space Complexity

LRFU를 효율적으로 구현하기 위해 Space를 어떻게 쓸까?

• Value at t' can be computed directly from Value at t
• maintain only recently computed Value and computing time t
• O(1) space complexity per block

• 블록 사용 시점, 횟수를 다 저장하는게 아니라 ❌
• 어떤 시점에 블록의 가치가 어떠했는지를 저장해두고
• 이를 바탕으로 현재 블록의 가치 평가

☑️ Time Complexity

• relative ordering of Values not change if not re-referenced
• 시간이 지나도 특정 블록들이 참조되지 않았다면
• 그 블록간의 Value 순서는 변하지 않을 것이다
• 따라서 재사용되지 않으면, Value의 대소관계는 변하지 않았을 것이다
• heap으로 구현
• 매번 쫒겨날 블럭을 찾기 위해 블럭 Value 계산할 필요 없이 ❌
• 사용되었다면 그 주변 node들과만 Value비교
• 재사용되지 않았다면 비교할 필요 없이 Value 가장 작은 값 쫒아냄
• O(log n) time complexity