Page

선수지식

• OS를 이해하기 위한 기본개념
  • Kernel(커널)
    • 컴퓨터 전원을 켰을 때 메모리로 올라와 시스템이 동작되는 동안 계쏙 머무르는 부분으로 OS에서 가장 기초적이고 핵심적인 기능을 담당한다. 커널을 통해 메모리,파일,주변장치 등과 같은 시스템구성 자원을 관리할 뿐 아니라 시간관리, 프로세스관리, 스케줄링 등 핵심사항을 처리함(JVM의 메소드영역과 비슷한 느낌이다.) 하드웨어에 두 사람 이상이 동일한 작업을 실행시켰을 때 중재자의 역할을 하고, 여러사용자가 동시에 사용할때 각자 독자적으로 작업할 수있도록 영역을 확보해 준다.
    
  • https://images.app.goo.gl/H6k6VktFFKDVFTqF9
  • Interrupt
    • 프로그램 수행 중 현재 프로그램과 상관없는 사건이 발생하면, 인터럽트를 걸어 수행중인 작업을 잠시 멈추고, 새로 발생한 사건을 처리한다. 쓰레드의 sleep, wait과 비슷한 느낌이다.
  • Trap
    • 커널 안으로 들어가 커널 서비스를 제공받기 위한 하나의 절차이다. 예를 들어 시스템 사용자가 작업 도중 시간을 알고 싶다는 요청을 하면 트랩을 통해 커널에게 요청이가고, 커널은 트랩을 통해 들어온 요청을 받아 처리한다. 트랩은 커널과 shell(Library)의 경계에서 기능을 수행한다.
  • System Call
    • 커널에게 작업을 의뢰하는 것이다. Trap 설명에서 들었던 예시인 '시간을 알고싶다' 요청이 System Call이다.
  • DMA(Direct Memory Access)
    • 프로그램 처리 중 입/출력 처리속도가 느린 것을 염두에 두고 고안한 방법이다. 입/출력이 동작할 때 CPU와 관계없이 DMA컨트롤러가 메모리에 접근 처리하는 것이다. DMA로 인해 CPU는 입/출력 처리 중에도 다른 연산이 가능하다. CPU는 DMA컨트롤러에게 입/출력 내용을 카피할 것을 명령, 이시점에서 CPU의 역할은 끝, DMA컨트롤러가 나머지 연산을 수행한다. (버퍼의 개념과 비슷하다.)
  • Context Switching(문맥 교환)
    • CPU의 수행 내용이 어떤 조건에 의해 바뀐느 것을 의미한다. 현재 수행 중이던 프로세스가 어떤 조건에 의해 잠시 수행이 멈추고, 다음 프로세스가 수행된다. 문맥 교환이 일어나는 조건들은 다음과 같다.
      1. 타임 퀀텀이 다 된 경우, 하나의 CPU로 여러 작업들을 처리하면 작업을 보다 빠르게 수행하기 위해 일정시간을 정해 두고, 그 시간동안만 수행한다.
      2. 입/출력이 발생해 유효시간 동안 CPU가 다른 작업을 수행할 경우
  • PCB(Process Control Block)
    • 프로세스가 수행되기 위해서는 프로세스만이 필요할까? 여러 프로세스들이 하나의 시스템 내에서 처리되기 위해선 그 프로세스의 정보가 유지되야 한다. PCB에는 프로세스에 어떤 자원이 할당되어 있고, 또 프로세스가 어떤 상태에서 수행 중인가를 나타내는 일체의 정보가 수록되어있다. 다시말해 Context Switching에 필요한 모든 정보가 PCB에 수록되어 있다. 다음과 같은 정보들이 PCB에 저장되어 있다.
      1. 프로세스가 준비, 실행, 대기 등 현재 어떤 상태인지
      2. 프로세스가 다음 어떤 명령을 처리하는지
      3. 프로세스가 CPU를 얼마나 사용했는지
      4. 먼저 처리되야할 프로세스는 어떤 것인지

학습목표

• 캐시교체 알고리즘을 공부하면서, OS의 페이지교체 알고리즘도 비슷한것을 알게되었다. OS에서 사용하는 페이지는 무엇일까?
• 페이지란?
• 페이지 교체 알고리즘
• 페이지 교체가 일어나게되는 이유

페이지란?

페이지는 페이징의 논리적 메모리공간을 나눈 단위이다.

페이징(Paging)이란,

• 하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 한다라는 제약을 없앤 메모리 관리법이다.
• 물리메모리는 Page Frame(페이지 프레임), 논리메모리는 페이지(Pgae) 단위로 나눈다.
• 논리 메모리는 물리 메모리에 저장될 때 연속되어 저장될 필요없이, 물리 메모리의 남는 Page Frame에 적절히 배치함으로써 외부 단편화를 해결한다.
  • 메모리가 남아있음에도, 실제 그 크기의 작업을 받아드리지 못하는 현상. → 메모리할당이 연속적이어야 한다는 제약 조건으로 인해, 연속된 공간의 크기가 작업의 크기만큼 확보되야 작업을 받아드릴수 있다.
• 외부 단편화를 해소하기위해 프로세스가 사용하는 공간들을 한쪽으로 몰아 공간을 확보하는 압축 작업보다 효율성이 놓다.
• 단점으로는 내부단편화 문제가 발생할 수 있다.
  ex) Page 크기가 1000Byte, Process A의 메모리 요구가 3010Byte라 가정하면, 물리 메모리 4개의 Page Frame이 사용되고 그 중한개는 990Byte 만큼의 공간이 낭비된다.

Page Table?

1. OS는 프로세스마다 Page Table이라는 자료구조를 유지한다.
2. Page Table은 Page Table Entry라는 페이지 정보를 저장한다.
3. Page Table Entry의 Key 는 Page 번호, Value는 물리 메모리의 시작주소다.
4. CPU에서 논리주소를 보내면 Page Table이 해당하는 물리메모리의 시작주소를 찾는다.

→ 즉 Map에 Key값으로 Page를, Value값으로 실제 물리메모리를 넣는것이다!...

세그멘테이션(segmentation)

• 페이징기법과 같은 비연속할당 기법중 하나이다.
• 세그멘테이션은 모두 고정된 크기가 아닌 가변크기인 세그먼트(segment)단위로 나눈다.
• 세그먼트 안위는 일련의 논리적 구조 단위다. ex)main functoin, method, object, stack, loacal variable 등과 같은 단위로 이루어져 있다.
• 각 세그먼트는 고유한 이름과 길이를 가진다.
• 주소변환을 위해 세그먼트테이블(segment table)을 사용
  • 세그먼트 테이블 구성 : 세그먼트 번호(S), 한계주소(limit), 기준주소(base)
• 페이지 테이블과 세그먼트 테이블은 구조가 다르다. 페이지와 다르게 세그먼트는 고정된 크기가 아니므로, 세그먼트의 크기를 알려줄수있는 limit와 base정보를 추가적으로 가지고 있다.
• 내부단편화는 없지만, 외부단편화가 발생한다.

페이지 교체 알고리즘

Page Fault가 나고, Frame(실제 메모리공간)이 더이상 비어있지 않을때, 즉 메모리가 꽉차있을때 페이지 교체 알고리즘을 통해 페이지를 교체한다. 이 알고리즘은 앞서 배운 캐시교체 알고리즘과 같다.

• Page Fault란 PageTable을 통해 실제 메모리에 접근하고자 했지만, 접근할수 없는 경우이다.

1. FIFO algorithm : 실제메모리에 가장먼저 들어온 페이지를 교체하는 방법
2. OPT algorithm : 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체, 실제 구현은 불가능
3. LRU algorithm : 가장 오랫동안 사용되지 않'은' 페이지를 교체한다. 참조된 시간을 알기위해 계수기(Counter)or스택(Stack)을 두어야 하므로 오버헤드 발생, 실제 구현이 복잡하다.
4. NUR algorithm : LRU와 비슷하지만, 오버헤드를 더 적게하는 방법이다. 2개의 bit를 통해 최근에 사용되지 않은 페이지를 교체한다.
5. SCR algorithm : FIFO 알고리즘에 1개의 bit를 추가해, bit값이 1이면 0으로 교체후 피드백시켜 다시한번 기회를 준다.

알게된 점

• 페이지란?
  • 메모리를 관리하는 기법중 하나인 페이징기법에서 논리적 메모리를 나누는 단위이다.
• 페이지 교체 알고리즘
  • Page Fault가 일어나고, Frame에 남은 공간이 없을때, 페이지 교체알고리즘을 통해 페이지를 교체한다.
  • 캐시알고리즘과 같으며, 역시 LRU알고리즘이 제일 효율적이다.
• 페이지 교체가 일어나게되는 이유
  • PageFault : PageTable을 통해 실제 메모리주소에 접근하려 했으나, 접근이 실패한 경우
  • PageFault가 나면 Disk에 있는 데이터를 찾아 실제 메모리에 올린다. 이때 실제 메모리(Frame)에 공간이 없으면 페이지 교체를 하게된다.

Reference

OS의 메모리 관리

OS의 메모리관리2

[운영체제] 3. 페이징(Paging)

운영체제 Page replacement (페이지 대체) 알고리즘이란?