[TIL] Pintos - 가상 메모리 관련 개념 공부1

1. 아침 문제 풀이

1. 2023번 - 신기한 소수

import sys

N = int(sys.stdin.readline())
result = []

#소수인지 판별하는 함수
def isPrime(n) :
    for i in range(2, int(n**(1/2))+1) :
        if n % i == 0 :
            return False
    return True

#백트래킹 방식을 사용한 탐색
def dfs(depth, n) :
    if depth == N :
        if isPrime(n) :
            result.append(n)
        return
    for i in range(10) :
        nn = n*10 + i
        if isPrime(nn) :
            dfs(depth+1, n*10+i)

prime = [2, 3, 5, 7]
for p in prime :
    dfs(1, p)

for r in result :
    print(r)

예전 같았으면 풀이를 참고할 법한 문제였다.
여기서 2가지 정리하면
1. 소수 판별
  소수란 1과 자기 자신만을 약수로 가져야하므로 자기보다 작은 수들을 나눠 떨어지는 것이 없으면 된다.
  이때 자신의 제곱근보다 큰 수들까지 셀 필요는 없다. 
2. 백트래킹 탐색
   문제 상에서 왼쪽부터 1자리, 2자리 등 모두 소수여야 하므로 소수일 경우 재귀를 사용

---

2. 가상 메모리 관련 개념 정리

1. 메모리 공유

• 메모리 : 각각 주소가 할당된 일련의 바이트들로 구성
• CPU는 Program Counter가 지시하는대로 메모리로부터 다음 수행할 명령어를 읽는다.
• CPU 스케줄링의 결과로 CPU 이용률과 사용자에게 제공하는 컴퓨터 응답속도를 향상
• 이러한 성능 향상을 실현하려면 많은 프로세스를 메모리에 유지할 필요가 있다.
• 즉, 메모리를 여러 프로세스들이 공유할 필요가 있다.

• 각각의 프로세스가 독립적인 메모리 공간을 가지도록 보장
  • 프로세스별 메모리 공간은 서로 보호하고 병행 실행을 할 수 있도록 한다.
  • base register : 가장 작은 합법적인 물리 메모리 주소
  • limit register : 주어진 영역의 크기 저장
  • base 값 <= addr < base + limit
  • 이러한 레지스터의 값 변경을 커널 모드에서만 변경 가능
    • 사용자 프로그램이 이 값들을 변경하는 것을 방지

2. 페이지

가상 주소의 분할된 영역으로 가상 메모리의 연속 영역

• Paging 기법
  • 고정 분할 방식 = 메모리를 모두 같은 크기의 블록으로 편성
  • 이때 일정한 크기를 가진 블록을 page라고 한다.
  • 장점 ✅ 
    • 프로세스의 물리 주소 공간이 연속적이지 않아도 된다.
    • 외부 단편화 해결
  • 페이지 개수가 n개인 프로그램을 실행하기 위해 n개의 프레임을 찾아서 로드할 필요가 있다.
• pintos에서의 페이지 크기 : 4096byte = 2^12byte = 4kiB
  • 페이지는 항상 정렬되어있어야 한다.
  • 즉, 각 페이지는 페이지 크기로 균등하게 나누어지는 가상 주소에서 시작!
  • 시작 위치 = 항상 페이지 크기로 나누어 떨어지는 위치
• 64bit 가상 주소(논리 주소) 
  • 상위 52bit = 페이지 테이블의 인덱스를 나타내는 데 사용 = page number
  • 하위 12bit = offset으로 사용

63          48 47            39 38            30 29            21 20         12 11         0
+-------------+----------------+----------------+----------------+-------------+------------+
| Sign Extend |    Page-Map    | Page-Directory | Page-directory |  Page-Table |    Page    |
|             | Level-4 Offset |    Pointer     |     Offset     |   Offset    |   Offset   |
+-------------+----------------+----------------+----------------+-------------+------------+
              |                |                |                |             |            |
              +------- 9 ------+------- 9 ------+------- 9 ------+----- 9 -----+---- 12 ----+
                                          Virtual Address

멀티 페이지 테이블 예시

3. 프레임

물리적 프레임 또는 페이지 프레임으로 물리적 메모리의 연속 영역

• 실제 메모리를 page와 크기가 같은 블록을 frame이라고 한다.
• 물리 주소 : 위의 논리 주소와 형식은 같음
  • frame number : 상위 52bit
  • frame offset : 하위 12bit = page offset과 동일하다

물리 주소

• 프레임 테이블 Frame Table (후에 구현해야할 것)
  • 어느 프레임이 할당되어 있고, 어느 프레임이 사용 가능한지, 총 프레임은 몇 개나 되는지 등에 대한 정보를 담는 자료구조
  • 각 프레임에 대해 하나의 항목을 포함
    • 현재 이를 차지하고 있는 페이지가 있는지
      • 있을 경우에는 차지하고 있는 프로세스에 대한 포인터 저장
        
    • 가장 중요한 작업은 사용하지 않는 프레임을 얻는 것
      • 프레임이 비어 있으면 비어있는 프레임 사용하면 된다.
      • 그러나 사용 가능한 것이 없으면 프레임에서 일부 페이지를 제거하여 프레임을 사용 가능하게 만들어야 한다.
      • 이 테이블을 사용하여 빈 프레임이 없을 때 제거할 페이지를 선택하여 Pintos가 제거 정책을 효율적으로 구현
      • 페이지 교체 알고리즘
        • FIFO : 가장 먼저 들어온 페이지 선택
        • Optimal Page Replacement : 앞으로 가장 오랫동안 사용되지 않을 페이지 선택
        • Least Recently Used : 가장 오랫동안 참조되지 않은 페이지 선택
        • Least Frequntly Used : 참조 횟수가 가장 적은 페이지 선택
        • Most Frequently Used : 참조 횟수가 가장 많은 페이지 선택

 

4. 페이지 테이블

프로세스의 페이지 정보를 저장하고 있는 테이블
CPU가 페이지에서 프레임으로 변환하는데 사용하는 데이터 구조

• 즉,논리 주소를 물리 주소로 변환
• 하나의 프로세스는 하나의 페이지 테이블을 가진다.
• page number는 frame number로 변환되고 offset과 결합
  • page offset = frame offset 항상 같다!

주소 변환 구조

• 추가 페이지 테이블 (후에 구현해야 할것)
  • 각 페이지에 대한 추가 데이터로 페이지 테이블을 보완
  • 페이지 테이블의 형식에 따른 제한 때문에 필요하다.
  • 사용 이유
    • page falut 시 커널이 추가 페이지 테이블에서 폴트가 발생한 가상 페이지를 조회하여 어떤 데이터가 있어야 하는지 알아내는 것
    • 커널은 프로세스가 종료될 때 추가 페이지 테이블을 참조하여 해제할 리소스를 결정
  • page fault가 발생하면 file 또는 swap slot에서 페이지를 가져와야 한다.

페이지 교체 과정

• page fault handler()
  • 추가 페이지 테이블에서 오류가 발생한 페이지 찾기
  • 페이지를 저장할 프레임 얻기
  • 데이터를 읽어 프레임으로 가져오기
  • fault가 있는 가상 주소에 대한 페이지 테이블 항목에 물리적 페이지를 가리키는 포인터 저장

5. swap slot

swap partition 내의 디스크 공간에 있는 페이지 크기의 영역

• swapping
  • 프로세스는 임시적으로 디스크로 교체되어 나갔다가 다시 메모리로 돌아올 수 있다.
  • 실제로 사용하는 부분만을 swap하여 시간을 줄인다.

• 스왑 테이블 Swap Table (구현해야 할것)
  • 사용 중 및 사용 가능한 swap slot을 추적
  • 프레임에서 swap partition으로 페이지를 제거하기 위해 사용되지 않은 swap slot을 선택
  • lazy swapper
    • 프로세스를 실행하고 싶으면 읽어 들이되, 필요한 페이지만 적재
  • 게으르게 할당되어야 한다.
    • 즉, 실제 필요할 때만 할당

< 참고 >

🔗 wiki-page

🔗 chappi.log - 가상메모리

🔗 pintos -vm -introduction 정리

🔗 가상 주소 gitbook

🔗 가상 메모리 gitbook

---

3. Pintos 관련 정리(gitbook)

1. 메모리에 접근하는 방법

• 물리 메모리에 접근하기 위해서는 커널 가상 메모리를 통해 접근한다.
• 커널 가상 메모리의 첫 번째 페이지는 물리적 메모리의 첫번째 프레임에 매핑
• 물리 주소와 커널 가상 주소 사이를 변환하는 함수

//물리적 주소에 해당하는 커널 가상 주소를 반환
#define ptov(paddr)

//커널 가상 주소에 해당하는 물리적 주소를 반환
#define vtop(vaddr)

🗒️ Pintos 가상 메모리 영역

//include/threads/vaddr.h
//include/threads/mmu.h

//커널 가상 메모리의 기본 주소
#define KERN_BASE 0x8004000000

• 사용자 가상 메모리 범위 = 0 ~ KERN_BASE
• 커널 가상 메모리 범위 = KERN_BASE ~ 나머지 공간
  • 전역적이다.
  • 항상 같은 방식으로 매핑된다.
  • 모든 유저 프로세스의 가상 메모리의 커널 가상 메모리는 항상 동일하다.