[운영체제] 입출력 시스템

디스크 스케줄링

• 하드디스크 내부는 그림처럼 구성
  • 여러 개의 원판, 마그네틱 매체에 실제 데이터가 저장되어있는 구조
    • 여러 원판은 여러개의 동심원(track)으로 구성되어있다
    • 각각의 트랙은 작은 조각인 섹터로 나뉘어져있다
      섹터는 내부에서 데이터 저장하는 최소 단위
    • 실린더는 같은 트랙에 있는(같은 동심원 상)에 있는 것을 서로 다른 원판에서 모아놓은 것
    • 데이터 읽고 쓰기를 담당하는 것은 헤더
      안쪽 읽으려면 안으로 이동, 바깥쪽 읽으려면 밖으로 이동한다

• 디스크 특징
  헤드는 동일한 실린더 위치, 트랙 위치를 같이 움직이면서 읽거나 쓸 수 있다
  데이터 저장되어있는 단위는 섹터는 최소 512바이트 크기 정도로 구성된다
  
  디스크 외부에는 디스크를 읽고 쓸 수 있는 컴퓨터와 CPU의 작업공간인 메모리가 있다
  디스크 내부에서는 컨트롤러가 섹터에 데이터를 저장하거나 꺼낸다
  디스크 밖인 컴퓨터에서 디스크에 데이터를 읽거나 쓰라는 요청을 할 때 섹터에 요청하는 것이 아니라 로지컬 블럭에 요청한다
  디스크 내부의 특정 원판, 특정 트랙, 특정 섹터에 데이터를 저장해놓기 때문에 내부에 데이터를 요청하면 원판, 트랙, 섹터 번호를 전달받아야 정확한 위치를 알수 있다 이런 물리적 위치를 담당하는 것은 디스크 컨트롤러가 담당

디스크 외부에서 컴퓨터 내부에서는 위치 얘기할 때 그냥 논리적 블록 번호를 이야기한다
디스크 안에 데이터가 1차원 배열에 저장이 된 것처럼 블록 번호가 0번부터 증가하는 번호로 되어있고 트랙번호, 섹터번호, 원판이 없다
디스크 외부에서 호스트 컴퓨터에서 디스크 위치를 지정할 때는 논리적 블록번호(1차원 배열처럼)를 준다 > 논리적 블록이 실제 저장되는 위치는 디스크에서 섹터라는 곳에 1대1로 맵핑이돼서 저장
논리적 블록 번호를 섹터 위치로 맵핑하는 것은 디스크 안 컨트롤러가 역할을 한다
섹터 중에서도 0 번은 제일 밖 쪽 첫번째 위치에 고정되어있다
0번 블럭은 파일 시스템에서도 부트 블럭으로 어떤 시스템에서도 고정되어있었음
디스크에서의 섹터 0번은 부팅을 위해 미리 정해져있는 섹터

디스크 관리

• 물리적 포맷팅
  디스크를 섹터 단위로 쪼개서 하나의 섹터를 관리하고자 구획을 나누는 과정이 필요한데 이를 물리적 포맷팅(로우레벨 포맷팅)이라고 한다

  • 섹터 하나에는 512바이트의 논리적 블럭이 저장된다
    섹터 앞, 뒤 부분에는 헤더와 트레일러라는 부가정보가 저장
    이는 디스크 외부에 보이는 정보가 아니라 내부에서 컨트롤러가 관리하기 위해 두는 정보
    (ex. 실제로 어떤 데이터가 들어와있는지 나타내는 섹터 번호 또는 ECC(에러 커렉팅 코드)라는 저장된 내용이 제대로 저장이 되어있는지, 배드 섹터가 나서 내용이 바뀌지 않았는진 체크)
  • 위와 같은 부가적 코드가 헤더와 트레일러에 같이 보관
  • 디스크 컨트롤러한테 섹터에 있는 데이터를 달라는 요청이 왔을 때, 컨트롤러는 해당 섹터의 실제 512바이트 데이터 뿐만 아니라 헤더와 트레일러 정보를 같이 읽는다

• 디스크 파티셔닝
  디스크 하나를 C드라이브, D드라이브로 나누는 것
  => 서로 다른 논리적 디스크가 된다

  • 운영체제 입장에서는 물리적 디스크의 개수가 아니라 각각의 파티션을 독립적 디스크로 간주한다
    3개로 나눴으면 운영체제 입장에서 디스크 3개로 보임
  • 각각 파티셔닝이 된 논리적 디스크는 파일 시스템을 설치해서 쓰거나 스왑영역으로 쓸 수 있다

• 로지컬 포매팅

  • 파티션된 논리적 디스크에 파일 시스템을 설치하는 과정

정리하면 디스크를 섹터 단위로 컨트롤러가 읽고 쓸 수 있게 나누는 과정이 피지컬 포매팅
각각의 논리적 디스크로 파티셔닝
각 파티션에 파일 시스템을 설치하는 로지컬 포매팅

• 부팅
  • CPU는 메모리의 기계어를 하나씩 실행하는데 메모리는 휘발성 매체라 전원을 키면 비어있다
  • small bootstrap loader
    (loader는 메모리를 올리는 기능을 하는 것)
    • 메모리에 전원 나가도 내용이 유지되는 작은 메모리(ROM)가 옆에 붙어있다 > 전원 켰을 때 ROM에 있는 기계어를 실행하게 된다 > ROM에 디스크 0번 섹터 내용을 메모리에 올리고 거기있는 기계어를 실행하라고 지시
  • full bootstrap loader
    • 0번 부팅 섹터를 로드하고(메모리에 올리고) 거기의 기계어를 실행하면 파일 시스템은 디스크에서 운영체제의 위치를 찾아 메모리에 올리고 지시하는대로 기계어 실행하라고 전달한다

• 디스크 접근하는 시간은 크게 3가지 요소로 구성
  • seek time
    • 가장 큰 시간 차지 => 이 시간을 줄이는게 중요
    • 헤드가 해당하는 트랙, 실린더로 이동하는 시간
  • 로테이셔널 레이턴시
    • 회전지연시간
    • 헤드가 원하는 섹터에 도달하기까지 걸리는 시간
  • 트랜스퍼 타임
    • 섹터와 헤드가 만나서 데이터를 실제로 읽거나 쓰는데 걸리는 시간
    • seek time에 비해 적은 시간 차지
• Disk bandwidth
  • 디스크 성능(처리량, 대역폭)
    단위 시간당 얼마나 처리하는지 처리되는 용량을 나타내는 것
  • 자체 성능도 중요하지만 내부적으로 관리도 중요
    특히 디스크 seek time을 줄이는게 중요
    작업이 큐에 들어온 순서대로가 아니라 뒤바꿔서라도
    이동거리를 줄이면 효율적으로 일하게 된다

    디스크 스케줄링은 시크타임 줄이는게 목표
    즉, 헤드 이동거리 줄이는게 목표

디스크 스케줄링 알고리즘

큐에 들어온 요청을 어떤 순서로 처리?

FCFS

• 디스크 큐에 들어온 시간 순서대로 이동
• 헤드 이동 빈번 > 비효율적

SSTF

• 가장 가까운 위치를 먼저 처리
• 현재 위치 기준으로 가까운 곳으로 이동
• 문제점
  • 스타베이션 발생 가능
    요청 거의 다 처리한 상황에서 새로운 요청이 계속 들어올 경우 영원히 서비스가 안되는 문제가 있을 수 있다

SCAN

가장 획기적인 방식

• disk arm이 이동하면서 중간중간 길목에 요청들어온게 있으면 요청을 처리하고 지나가는 방식
  • 이동방향은 요청의 위치와 관계없이 한쪽으로 이동
• 엘리베이터 스케줄링과 유사
  엘리베이터가 올라가는 방향으로 이동하니까 일단 올라가다가 같은 방향으로 가는 승객이 있으면 태워서 올라간다
• 문제점
  • 트랙 위치에 따라 대기 시간의 편차가 발생
    최악의 경우: 가장자리에서 헤드가 출발했는데 출발 이후에 그제서야 요청 도착했다면 요청은 헤드가 한바퀴 돌아올 때까지 기다려야 한다
    요청이 중간이고 막 출발했다고 한다면 출발한 한 중간부터 다시 중간까지 기다려야 한다
    대기 시간이 2배 차이

C-SCAN

위에 나온 대기시간 편차를 줄이는 알고리즘

• 디스크 한쪽으로 이동하면서 들어온 요청을 처리하고 지나감
• 끝에 도달하면 올때는 요청 처리 안하고 헤드를 다시 출발점으로 이동시킨다
• 어느 위치에 있는 요청이든 간에 기다리는 시간의 편차가 균일하다
  (헤드의 이동은 조금 늘어날 수 있다)

다른 알고리즘들

• N-SCAN
  • SCAN은 이동하면서 각각 위치에 요청이 있으면 반드시 처리하고 지나감
    N-SCAN은 디스크 헤드가 출발하는 시점에 큐에 들어온 요청을 가면서 처리
  • 도중에 들어온 요청은 다 간 다음에 턴을 해서 되돌아올 때 처리
    이동하는 도중에 새로들어온 요청은 이번 이동때 처리하는게 아니라 되돌아올 때 처리
    SCAN에 비해 대기시간 편차를 줄일 수 있다 먼저 들어오면 먼저 처리되는 효과

• LOOK과 C-LOOK
  • LOOK은 SCAN을 변형한 것, C-LOOK은 C-SCAN을 변형한 것
  • SCAN은 항상 밖에서 안 실린더로 턴하면서 이동
    LOOK은 이쪽 방향으로 더이상 들어온 요청이 없으면 찍고 턴할 이유가 없다
    굳이 14에서 0까지 이동할 이유가 없다고 판단하고 14에서 바로 턴
  • C-LOOK은 C-SCAN처럼 운영하는데 이쪽 방향으로 더이상 요청이 없으면 턴
    183까지는 요청이 있지만 더 큰번호에서 요청이 없더라도 마지막 부분 찍고 턴

현대 디스크 시스템에서는 SCAN을 기반해서 개선한 알고리즘을 사용중
디스크 스케줄링은 파일 어떻게 할당하느냐에 따라 영향받고있음
디스크 특성에 맞게 사용할 수 있게 하는 것이 바람직

스왑영역 관리

• 물리적 디스크를 파티션으로 나누어서 각각 로지컬 디스크로 만들 수 있다. 운영체제 입장에서는 독립적 디스크로 간주하고 파일 시스템을 설치하거나 스왑영역으로 사용
  • 전원 나가더라도 영구적 영역을 담당하는게 파일 시스템
    물리적 메모리 연장공간으로 프로세스 주소공간을 담는게 스왑영역
    * 파일시스템 관리는 512바이트 섹터 단위로 관리
    최근에는 호스트 컴퓨터와 디스크 사이 데이터 주고받는 단위를 4KB로 주고받기도 한다
    스왑영역은 주고받는 단위가 더 크다
• 파일 시스템에 저장되는 파일은 전원 꺼지더라도 항상 유지가 되는 정보 => 공간 효율적 관리가 중요
• 스왑영역은 전원을 끄면 사라질 정보
  따라서 공간 효율성보다는 속도 효율성이 중요
  많은 내용을 빠르게 메모리에 올리고 메모리에 있는 내용을 빠르게 쫓아낸다
• 스왑영역은 더 큰 단위로 관리
  연속된 여러 개의 섹터를 모아서 많은 양을 읽고 쓰게되고, 512바이트까지 큰 데이터를 읽을 수 있다
  스왑영역은 큰 뭉치로 데이터를 읽고 쓰는데 있어서 효과적이다

RAID

• 레이드
  • 독립적인 디스크를 묶어서 쓰는 방법
    저렴한 디스크를 쓴다고 하는 사람들도 있다
• 장점

1. 신뢰성 향상

• 서로 다른 디스크에 중복저장 => 미러링 또는 쉐도잉
• 디스크 하나가 고장나더라도 다른 고장안난 것을 읽어서 쓰면 훨씬 안정적
  하지만 공간낭비가 발생
  중복 많이 하면 신뢰성 높아지고 부분만 중복하면 공간효율성이 높아진다
  (버전 여러개 있다 - 완전 중복, 최소 중복 등)
  디스크가 하나 고장나더라도 나머지 디스크와 parity 정보를 이용해서 고장난 디스크 정보 복원이 가능
  * parity는 일종의 축약정보
  각각 다른 디스크에 다른 내용을 저장하고 마지막 디스크에 3개의 내용을 축약해서 결과를 저장

2. 성능 향상

• 데이터를 하나에 저장하는게 아니라 나누어 저장해놓으면 데이터를 호스트 컴퓨터가 요청하는데 한군데에서 읽어오라는 것과 각각 디스크에서 읽어오라는 것 중 어떤 것이 빠른가?
  • 4군데서 병렬적으로 일하면 빠름 > 디스크 성능 향상
• 블럭 내용을 분산적으로 저장해놓고 요청을 병렬성을 이용해서 모으면 더 빠르다
  인터리빙, 스트라이핑(줄무늬)이라고 함

유닉스 파일 시스템

논리적 블럭은 아래 그림처럼 구성
맨 앞에 기존 슬라이드에는 부트 블럭이 0번에 있었다. 어떤 파일 시스템 사용하든 간에 부트블럭 존재했음

• 수퍼 블록
  • 맨 앞에 존재
  • 데이터 전체의 총체적인 구조를 가지고 있다
    (블럭 하나 크기, 아이노드 몇 개, 데이터 블록 몇 개 비어있는것 어디부터 시작되는지 등)
• 아이노드 블록
  • 메타 데이터 관리
• 데이터 블록
  • 실제 데이터 관리
• 아이노드나 데이터블럭이나 블럭 하나 크기는 동일하지만, 파일 하나당 저장되는 메타데이터는 블럭 하나보다 작다

아이노드

• 각 파일마다 파일의 메타데이터를 보관하는 공간
  파일의 소유주, 최종 수정 시각, 여러 가지 파일의 접근 권한, 파일의 위치 정보가 메타 데이터로서 아이노드에 저장되어있다

파일 시스템 변천사

• 가장 많이 사용하는 파일 시스템 Ext4의 과거 버전과 발전 방향
  *FFS나 Ext3, 등은 리눅스 기반 파일시스템
• 파일 시스템이 발전하면서 성능이 좋아지고 대용량 데이터를 지원하는 방향으로 발전하고 있다

Ext2 파일 시스템

• 아이노드 부분
  • 여러 메타 데이터들이 아이노드에 저장
  • 위치 정보 나타내는 부분이 15개의 포인터로 구성된다
    12개는 실제 데이터 블럭의 위치를 곧바로 가리키고 있고, 나머지 3개의 포인터는 아주 큰 파일을 지원하기 위한 인다이렉트 포인터
    Ex. 다이렉트 포인터만 15개가 있다고 하면 파일의 크기가 15 곱하기 블럭 하나의 크기로 한정된다
    큰 파일을 지원하기 위해서 인다이렉트 포인터를 3개를 지원
    
• 첫 번째는 싱글 인다이렉터: 포인터가 데이터 블럭을 가리키는데 여기에 실제 파일 위치를 가리키는 포인터들이 위치
  더블 인다이렉터: 인덱스 두 번 통과해야지만 실제 데이터 위치가 나온다
  트리플 인다이렉터: 인덱스 3개 통과해야지 실제 데이터블럭이 나온다
  (트리플은 매우 큰 파일이 지원이 된다)

ext2 파일시스템이 기존 유닉스에 비해 개선된 점이 블록을 그룹화한다는 점

• ext2는 기존 유닉스와 달리 아이노드와 데이터 블록을 그룹으로 묶어서 여러개 만든다
  파일에 접근할 때 메타데이터에 접근한 뒤 실제 데이터 접근하게 되는데,
  메타데이터와 실제 데이터는 양 끝에 위치하게 되면 디스크 헤드가 왔다갔다 하면서 헤드이동이 빈번해지게 된다

• 이를 해결하기 위해 각각의 그룹 내에 메타와 실제 데이터를 같이 위치시킨다 => 이를 통해 헤드 이동 줄임

• 원래 오리지널 유닉스는 전체에 대해 수퍼블록을 하나만 저장했었는데
  EXT2에서는 그룹마다 동일한 수퍼블럭을 저장한다
  전체 파일 시스템의 수퍼블럭을 그룹마다 여러 개 중복저장해서 신뢰성을 높일 수 있다
  각각의 블럭 그룹을 보면 파일 시스템 하나의 구조로 되어 있다

• 그룹 디스크립터
  • 그룹의 수퍼블럭 역할
  • 전체 파일 시스템의 총체적 정보는 수퍼블럭이고 디스크립터는 그룹에 대한 총제적 정보

• 비트맵 방법
  • 비어있는 블럭과 사용중인 블럭을 비트로 표기하는 방법
• 데이터 블럭 비트맵
  • 데이터 블럭 개수만큼 비트맵이 있어서 사용중인 것을 쭉 표시
• 아이노드 비트맵
  • 사용중인 아이노드와 비어있는 아이노드가 어딘지 표시

전체 파일 시스템을 그룹화해서 나누어 놓았다는게 가장 중요

EXT2가 EXT3와 EXT4로 발전을 해왔다
지금의 4는 어떤 차이?
구조는 동일하다
4는 2에 저널링이라는 기능이 추가
4가 서버에서도 사용되고 있고 데스크탑에서도 스마트폰에서도 사용되고 있다

저널링

고양이가 코드 뽑아서 블루스크린이 떴으면 작업 소실되거나 파일시스템 자체가 깨져서 옛날 데이터도 안보일 수도 있다

• 파일 시스템 내용을 작업하기 위해 메인 메모리 버퍼캐시에 올려놓고 작업한다 > EAST를 올려놓음
• 파일시스템에서 하드디스크는 비휘발성, 전원 나가더라도 내용이 유지작업이 가능하다
  * 버퍼캐시는 휘발성, 전원이 나가면 내용이 사라진다
• 버퍼캐시에 올려놓고 작업은 하지만 수정된 내용은 파일 시스템에 반영해줘야 한다
  GO EAST였는데 작업하던 사람이 WEST로 바꿨다면 파일 시스템이 아니라 버퍼캐시에 먼저 반영된다
  정상적인 상황이라면 파일 데이터로 반영되어야 하는데 W만 반영된 상태에서 전원이 나가버리는 상황 => 시스템 크래시 발생
  전원 나가면 휘발성 내용은 사라짐!
  동쪽도 아니고 서쪽도 아닌 내용으로 내용이 깨진다
  (가장 최신 내용인 웨스트가 저장되어있으면 좋은것
  동쪽 이전 데이터가 저장되어있으면 그나마 좋은것)
  재부팅을 하면 버퍼캐시는 당연히 비어있있고 인컨시스턴트 하다고 보인다

저널링으로 해결

버퍼캐시에 올라온 데이터가 수정된 경우,
쫓겨날 때 파일시스템에 저장하는게 아니고, 이러면 중간에 크래시 났을 때 안쫓겨났으면 상당히 오래된 정보 보이거나 완전히 깨질 수 있기 때문에
주기적으로 수정된 정보를 스토리지에 기록

• 원래 위치에 쓰는게 아니라 저널이라는 별도영역에 써준다
  • 수정된 내용을 5초 간격으로 저널에 써주고 나중에 5초보다 더 긴 주기로 원래 위치에 반영한다
• 두번쓰기로 깨지는 것을 막으려는 목적
• 저널에 쓰는 도중에 크래시 나면 그냥 날려버린다고 해도 적어도 옛날 정보는 남아있다
• 온전히 써졌다면 마크를 찍어서 제대로 써졌다고 전달한다
  • 크래시가 파일 시스템에 반영 도중에 나더라도 이미 저널에 마크가 찍혀있기 때문에 마크가 찍힌 내용을 한번 더 올려주면 최신 정보를 볼 수 있다

또 다른 예제
저널링이라고 별도 위치에 써주고 온전히 써지면 나중에 체크포인트에 반영
올드와 뉴 상태가 보일 순 있지만 적어도 inconsistent 상태가 만들어지지는 않도록 한다

저널링 모드 두 가지

• 디폴트는 메타데이터만 저널링
  • 사용자가 파일의 데이터를 시스템 콜해서 수정하면 버퍼캐시에 반영이 된다 > 이때 메타데이터도 수정(최종수정시각 등)
  • 데이터는 원래 위치에 써주고 메타데이터만 저널링 위치에 써준다
    5분 간격으로 체크포인트 주기가 되면 메타데이터를 실제 위치에 올려서 써준다
  • 메타데이터 저널링한다는 것은 파일 위치정보가 들어가있기 때문에 위치 정보가 깨지지는 않는다
  • 파일구조자체가 깨지는 것을 방지할 수 있지만 일부 데이터는 훼손 가능

• 메타와 일반 모두를 저널링
  • 신뢰성이 높아야된다고 하면 메타와 일반까지 저널링 될 수 있도록 모드 바꿔줄 수 있다
  • 버퍼캐시에 반영된 정보를 5초 간격으로 메타, 일반 모두 저널 영역에 써준다 > 체크포인트 주기가 도래하면 원래 위치에 써주게 된다
    => 어떤 경우에도 파일 시스템과 파일이 깨지지 않게 된다
  • 최신 정보 보장 된다는게 아니라 옛정보 또는 새 정보와 같이 의미있는 정보가 보인다

    저널링이 의미단위로 업데이트 되는지 안되는지를 말한다
    반만 업데이트 되는것 방지, 깨지는 것 방지

버퍼캐시 알고리즘

파일을 요청한 순서에 따라 버퍼캐시에 올라가는데
5번 올라와야할 때 공간 다 찼기 때문에 하나가 쫓겨나야 한다

• LRU는 가장 오래전에 사용된 블럭인 1번을 쫓아냄
• 단점
  • 가장 마지막에 사용된 시점만을 고려해서 이전에 사용된 기록은 전혀 활용되고 있지 못하다
• LFU는 사용횟수를 고려해서 4번 쫓아냄
• 단점
  • 사용시점을 고려하지 않는다

LRFU 알고리즘

• 지금 버퍼캐시 안의 블럭에 대해서 가치 평가하는 식을 계산해서
  각 블럭 x에 대해 밸류가 가장 작은 블럭을 쫓아내게 된다

• 현재 시점 기준으로 블럭 x는 과거에 세 번 사용되었다

  • 로우의 델타 승, 로우는 상수(0보다 크고 1보다 작다), 지수는 사용된 시점부터 현재까지 흐른 시간
    세번 사용되었다면 로우의 델타 승이 세번 합쳐지게 된다

• 사용횟수가 많으면 더해지니까 값이 커지게 된다

• 로우가 0보다 크고 1보다 작기 때문에 지수가 커지면 값은 작아진다

  • 흐른시간이 길수록 값은 작아진다는 것
  • 최근 사용 기록일 수록 더 많이 기여(더 높은 가치)

제약조건이 있었다

• 각 블럭마다 과거의 모든 참조 시각을 유지하는것은 메모리 낭비
  • 블럭 자체를 보관하는것보다 시간 정보 유지하는게 더 많은 공간 소요 > 공간 오버헤드
• 타임 오버헤드
  • 버퍼캐시 공간이 N개가 있을 때 적어도 O(log n) 이내에 어떤것을 쫓아낼 수 있을지 결정할 수 있어야 한다
  • 매번 결정하기위해 N개를 쭉 살펴보고 결정하면 시간이 오래걸린다
    이 알고리즘은 버퍼캐시 안의 모든 블록에 대해 밸류를 다 계산해보고 밸류가 제일 작은것을 쫓아내기 때문

LRFU의 효율적 구현 방법

• 공간 오버헤드 해소 방법
  • t'(t프라임)이라는 현재 시점에 블럭 x의 가치를 평가하는 계산식
    • 각각의 참조 시점부터 현재까지 흐른 시간을 지수로 해서 합쳐준다
  • t'보다 조금 과거 시점인 t를 기준으로 t까지 흐른 시간의 밸류가 괄호안의 식이 된다 => t 시점에 구해놓은 밸류를 가지고 t 시점부터 현재까지 얼마나 시간이 흘렀는지만 지수로 해서 곱해주면 가치 계산할 수 있다
  • 모든 과거 참조기록 유지할 필요없이 특정 시점의 가치를 계산해놓으면 그 이후에 흐른 시간 정보를 가지고 가치 계산할 수 있다

• 타임 오버헤드 해소 방법
  • 다시 사용되지 않은 블럭들 안에는 상대적 가치의 대소관계가 변하지 않는다
  • t라는 시점에 a라는 블럭 가치가 b보다 높았고, 그 이후에 a, b 모두 사용된적 없다고 하면 아무리 시간이 흘러도 a의 가치가 b의 가치보다 더 크다
  • 흐른 시간만큼 로우의 델타 승 곱해준다
    • 양수 곱해도 부등호 방향 바뀌지 않기 때문에 블럭들이 재사용되지 않는 이상은 가치 대소관계가 바뀌지 않는다

LRFU의 효율적 구현 방법

• 힙 델타 스트럭처를 이용해서 구현
  • 힙의 루트에는 밸류가 작은 블럭 위치
  • 부모보다 자식 밸류값이 크도록 위치시키면 매번 쫓겨날 블럭을 찾기 위해 모든 블럭 밸류 계산할 필요없이 루트 블럭 쫓아내면 된다
    시간 흐름 따라 밸류 자체는 변하지만 밸류가 작은 것은 변하지 않기 때문에 루트 쫓아내고 힙을 재구성한다
  • 다만 힙 안의 블럭이 다시 사용되면 그 친구의 밸류는 증가한다
    한번 더 사용되면 화살표 한번 더 생김, 그만큼 플러스
    밸류 바뀌면서 대소관계 바뀔 수 있어도 전체와 비교할 필요없이 직계자식과만 비교해서 자리 바꿈
    재사용이 된 친구만 본인 위치 따라내려가서 자리 찾아준다

장점만 모아놓은 알고리즘
로그 2의 백만 하면 20보다 작은 숫자기 때문에 백만번 비교해야할 것은 10번만 비교하면 되는식

버퍼캐시 크기에 따라 LRFU가 성능이 더 좋다