LECTURE is here

KOCW 온라인에서 제공되는 이화여대 반효경 교수님의 OS 강의에 대한 정리 요약

• 노션에 기록했듯 CSAPP과 함께 천천히 병행
• 연관 게시글은 강의 진행 순서대로 정렬되어 있지 않고, 내 필요에 따라 강의의 주제를 선택해 듣는다.
• 온라인 상의 타인들이 올려놓은 연관 자료 역시 함께 참고한다.

Demand Paging (요구 페이징)

paging 기법을 기반으로 하되, 실제로 필요할 때 page를 메모리에 올리는 메모리 관리 기법이다.

필요할 때 page를 올린다는 개념으로, 전부 한꺼번에 올리는 게 아니고 요청이 있으면 그 페이지를 메모리에 올리겠다는 의미이다.

실제로 현재의 대부분의 시스템들은 Paging 기법을 사용 중이다.

여기서 잠깐,
Segmentation with paging vs Demand paging

둘 다 프로세스가 실행될 때 필요한 페이지 또는 세그먼트를 메모리에 적재하는 방식이다.

Segmentation with paging 기법은 세그먼트와 페이지를 조합하여 가상 주소 공간을 관리합니다. 이 방식은 가상 주소 공간을 여러 개의 세그먼트로 나눈 후, 각 세그먼트를 페이지로 나누어 메모리에 적재하는 방식입니다. 이 방식은 세그먼트별로 크기가 다른 프로세스를 관리할 수 있으며, 메모리 내부 단편화를 방지할 수 있습니다.

Demand paging 기법은 필요한 페이지만 메모리에 적재하는 방식입니다. 이 방식은 페이지 폴트가 발생할 때마다 해당 페이지를 디스크에서 메모리로 읽어옵니다. 이 방식은 프로세스가 실행되는 동안 필요한 페이지만 메모리에 적재하므로 메모리 사용량을 줄일 수 있습니다.

따라서, 두 기법은 각각의 장단점을 가지고 있으며, 운영 체제에서는 상황에 따라 적절한 방식을 선택하여 사용합니다.

요구 페이징의 장점

• I/O양의 감소 (프로그램 중에 빈번하게 사용되는 부분은 지극히 제한적이고, 좋은 소프트웨어일수록 프로그램 사용에 있어 굉장히 방어적으로 코드를 작성하기 때문에 잘 사용되지 않는다.)
• 물리 Memory 사용량 감소
• I/O 요청이 있을 때만 메모리에 올리기 때문에 한정된 메모리 공간을 효율적으로 사용하고, 메모리에서 직접 서비스하는 비율이 높아지기 때문에 보다 더 빠른 응답 시간을 기대할 수 있다.
• 멀티프로그래밍 환경에서는 더 많은 사용자 수용 가능
  프로그램 여러 개가 동시에 메모리에 올라가는 환경에서는 더 많은 사용자가 동시에 메모리에 올라갈 수 있기 때문에 효과적이다.

📌 Vaild / Invaild bit의 사용 (페이지 테이블의 엔트리마다 존재)

Invaild의 의미는 앞서 알아보았듯 아무 사용도 되지 않고 있는 주소 영역인 경우, 혹은 페이지가 물리적 메모리에 없는 경우다.

페이지가 물리적 메모리에 없는 경우

demand paging에 의해 필요하지 않은 페이지들 backing store에 있음. -> Invlalid 표시

사용되지 않는 주소 영역인 경우

위 그림에서는 G,H는 사용안되는 공간, 주소 공간에서 영역을 지원하기 떄문에 
페이지 테이블에는 올라가게 되고, invalid 표시가 된다.

처음에는 모든 page entry가 invaild로 초기화되어 있다.

address translation 시에 invalid bit이 set되어 있으면 "page fault"! -> cpu가 자동적으로 운영체제로 넘어간다. 이를 Page Fault Trap에 걸린다고 표현한다.

Page Fault Trap 발생 후 진행

주소변환을 하려고 봤더니 invalid로 표시되어 있음.
페이지가 메모리위에 올라와있지 않다는 말이고 trap에 걸려서 CPU가 OS에게 자동으로 넘어간다.
OS는 백킹스토어에 있는 페이지를 물리메모리로 올린다.
빈 페이지 프레임이 없으면 뭔가를 쫓아내고 올린다.
올렸으면, 해당 프레임번호를 엔트리에 적어두고, invalid -> valid로 수정한다.
나중에 CPU를 다시 얻어서, 정상적으로 주소 변환을 하면 물리 메모리에 정상 접근이 가능해진다.

현실에서는 아주 낮은 확률로 Page Fault가 발생한다고 한다. 대부분의 경우에 메모리로부터 직접 주소 변환할 수 있고, 매우 드물게 Page Fault가 발생해 디스크 접근이 필요하게 된다. Page Fault 처리는 매우 긴 시간을 소요하는 작업이다.

Replacement algorithm

Free page frame이 없는 경우 어떤 frame을 빼앗아올지 결정해야 한다. 이를 선정하는 알고리즘을 Replacement algorithm이라고 한다. 이는 OS가 담당하는 업무다.

1. 어떤 걸 쫓아낼 지 결정하고, 만약 쫓아낼 때, 변경된 내용이 있다면 변경된 내용을 백킹스토어에 써줘야 한다.
2. 쫓아내고 빈 자리에 새로운 page를 올려준다. 페이지 테이블에 frame number를 적고, valid로 바꿔준다.

곧바로 사용되지 않을 page를 쫒아내는 것이 좋으며 가능하면 Page-fault rate를 최소화하는 것이 목표다. 동일한 페이지가 여러 번 메모리에서 쫒겨났다가 다시 들어올 수 있다. 주어진 page reference string에 대해 page fault를 얼마나 내는지에 대한 기준이 알고리즘의 평가 기준이다.(페이지 폴트 발생비율을 가급적 0으로 만드는게 이 알고리즘의 목표)

1. 최적 알고리즘 (Optimal Algorithm)

페이지 폴트를 가장 적게하는 알고리즘이나, 미래의 일을 예측할 수 없기 때문에 이론적인 알고리즘이다. (실제 시스템에서 온라인으로 사용하는게 아니기 때문에 Offline Optimal Algorithm 이라고도 부른다.)

• 제일 먼 미래에 사용될 page를 쫓아내는 방식.
• 빨간색으로 적은 부분이 페이지 폴트가 발생하는 부분. 연보라색은 메모리에서 직접 참조되는 경우.

(다른 알고리즘의 성능에 대한 upper bound를 제공하는 데에 의의가 있다. 아무리 좋은 알고리즘을 만들어도 이 최적 알고리즘보다 더 좋은 알고리즘은 만들 수 없기 때문에 참고용으로만 사용 가능하다.)

2. FIFO (Fist In First Out) Algorithm

여기서부터 실사용 가능한 알고리즘이다.

• 먼저 들어온 것을 먼저 내쫓는 방식.

• FIFO Anomaly(Belady's Anomaly) :
  메모리 크기(page frame 갯수)를 늘려줘도 성능이 더 나빠지는 특이한 상황이 발생할 수 있음.

3. LRU (Least Recently Used) Algorithm

실제로 가장 많이 사용하고 있는 알고리즘이다!

• 가장 오래 전에 참조된 것을 지우고 최근에 쓰인 것은 남기는 것. 최근에 쓰인 페이지가 또 쓰일 것이라고 가정하는 알고리즘.

• 장점
  구현이 비교적 쉬움.
• 단점
  page의 실제 인기도를 고려하지 못함.

4. LFU (Least Frequently Used) Algorithm

• 참조 횟수 (reference count)가 가장 적은 페이지를 지우는 것.

• 최저 참조 횟수인 page가 여럿 있는 경우:
  • LFU 알고리즘 자체에서는 여러 page 중 임의로 선정한다.
  • 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있다.
• 장점
  LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간규모를 보기 때문에
  page의 인기도를 좀 더 정확하게 반영할 수 있음.
• 단점
  참조시점의 최근성을 반영하지 못함. LRU보다 구현이 복잡함.

5. LRU vs LFU 예제

• 페이지 프레임은 4개 존재. 1,2,3,4중에 하나를 쫓아내야 함.
• LRU : 1번을 쫓아냄 / LFU : 4번을 쫓아냄.
• 제일 참조횟수가 많은 1번을 쫒아내는 LRU, 제일 최근에 참조된 페이지를 쫒아낸 LFU -> 누가 더 비효율적인지 측정 힘듬.

6. LRU, LFU 알고리즘의 구현

6.1. LRU

시간복잡도 : O(1)

LRU는 메모리에 있는 페이지들을 참조 순서에 따라 한 줄로 줄세우기를 한다. linkedlist 형태이다.

맨 아래로 갈수록 가장 최근에 참조한 페이지, 맨 위에 페이지가 가장 오래전에 참조된 페이지.

쫓아낼 때 비교가 필요없다. 제일 위에 있는 페이지를 내쫓으면 된다.

6.2. LFU

시간복잡도 : O(log n) ~ O(n)

이 알고리즘은 한 줄로 줄세우기가 불가능하다. 카운팅 될 때마다 비교를 해서 어디까지 내려올 수 있는지 비교하고 자리 바꿈을 해야 하기 때문. 고로 자료구조 min heap을 택하며, 이는 tree의 형태를 띈다.

힙을 사용(Complete binary tree)하게 되면 시간복잡도 O(log n). 경로를 따라가면서 자식 2개와만 비교하기 때문에 log n 의 시간복잡도가 발생하게 됨. (이진트리의 장점)