[TIL] CSAPP 9장 공부 - 가상 메모리 개념 정리

1. 아침 문제 풀이

1. 2563번 - 색종이

import sys

n = int(sys.stdin.readline())
array = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
canvas = [[0]*100 for _ in range(100)]

result = 0
for i in range(n) :
    for j in range(array[i][0], array[i][0]+10) :
        for k in range(array[i][1], array[i][1]+10) :
            if canvas[j][k] == 0 :
                canvas[j][k] = 1
                result += 1
print(result)

처음에는 색종이의 개수만큼의 넓이를 구한 다음 겹치는 부분을 넓이에서 빼주려고 했다.
그러나 다 겹치는 경우에 모든 넓이를 빼버려서 0이 도출되어 틀렸다.

이 문제는 실버5 문제로 내가 너무 어렵게 생각한 문제였다.
단순히 canvas라는 2차원 배열을 두어서 색종이가 존재할 위치에 모두 1로 표시를 해두고
1의 개수를 세면 간단하게 풀릴 문제였다.

다양한 방식으로 생각해보는 연습이 된 문제였다.

---

2. 가상 메모리(Virual Memory, VM)

메인 메모리의 추상화
각 프로세스에 하나의 크고 통합된 사적 주소 공간 제공

1. 기능

• 메인 메모리를 디스크에 저장된 주소공간에 대한 캐시로 취급해서 메인 메모리 내 활성화 영역만 유지하고 데이터를 디스크와 메모리 간에 필요에 따라 전송하는 방법으로 메인 메모리를 효율적으로 사용
  • 메인 메모리(RAM)는 한정되어 있다.
  • 즉, 필요한 데이터만 메인 메모리에 올린다.
  • 데이터를 디스크→메인메모리 또는 메인메모리→디스크 로 이동시키는 과정이 필요하다.
  • 이는 CPU, OS에 의해 관리된다.
• 각 프로세스에 통일된 주소 공간을 제공함으로써 메인 메모리를 효율적으로 관리
• 각 프로세스의 주소 공간을 다른 프로세스에 의한 손상으로부터 보호

---

2. 주소 방식

• 메모리 주소(memory address) : 메모리 위치에 대한 식별자
• 물리 주소 방식 : CPU가 메인 메모리에 접근할 때 물리 주소를 사용
  • 물리주소(Physical Address) : 컴퓨터가 메인 메모리에 접근할 때 사용되는 주소
  • 물리 주소 공간(Physical Address Space) : 물리 주소로 접근이 가능한 주소 공간 = 실제 메모리 공간
  • 한계
    • 메인 메모리의 크기보다 용량이 큰 프로그램을 메모리에 적재할 수 없어 실행 불가능
    • 컴파일할 때 물리 주소를 지정하기 때문에 여러 개의 프로그램을 동시에 실행 어려움
  • 🔗 https://ko.wikipedia.org/wiki/물리_주소
• 가상 주소 방식 : CPU가 메인 메모리에 접근할 때 가상 주소를 사용
  • 가상 주소(Virtual Address) : 물리 주소의 반대 개념
  • 가상 주소 공간(Virtual Address Space) : 가상 메모리 기법으로 제공되는 주소 공간 = 프로세스의 관점에서 사용하는 주소
    • 프로세스가 참조할 수 있는 주소들의 범위
    • 하나의 프로세스 당 하나의 가상 주소 공간 제공
    • Thread는 프로세스 내의 주소공간 공유
  • 주소 번역 : 가상 주소를 메모리로 보내기 전에 적절한 물리 주소로 변환
    • VAS 와 PAS의 원소들 간의 mapping
    • n-bit VA : virtual page number(n-p) / p-bit virtual page offset
    • PA = physical page number + page offset
    • virtual offset = physical page offset
  • Memory Management Unit(MMU) : 메인 메모리에 저장된 참조 테이블을 사용해서 실행 중에 가상 주소 번역

가상 주소 지정 방식

주소 변환

---

3. Paging

가상 메모리를 모두 같은 크기의 블록으로 편성하여 운용하는 기법

• page : 가상 메모리를 일정한 크기를 나눈 블록
• frame : 물리 메모리를 일정한 크기로 나눈 블록
• page의 크기 = frame의 크기
• 어떤 프로세스가 현재 참조하고 있는 페이지가 메인 메모리에 있다면 그 프로세스는 수행 가능
• 반면에 메인 메모리에 없다면 디스크에서 읽어와서 메인 메모리에 저장해야 한다.

 

• Page Table
  • 프로세스의 페이지 정보를 저장하고 있는 테이블 = PTE
  • 메인 메모리에 저장되어 있고 이는 MMU 가 주소를 번역할 때마다 읽는다.
  • Page Table Entry(PTE)
    • 페이지 기본주소(Page base address)
    • 플래그 비트
      • 접근 비트(Accessed bit) : 페이지에 대한 접근이 있었는지를 나타낸다.
      • 변경 비트(Dirty bit) : 페이지 내용의 변경이 있었는지를 나타낸다.
      • 존재 비트(Present bit) : 현재 페이지에 할당된 프레임이 있는지를 나타낸다.
      • 읽기/쓰기 비트(Read/Write bit) : 읽기/쓰기에 대한 권한을 표시한다.
    • 🔗 https://ko.wikipedia.org/wiki/페이징
• Page Hit
  • 사용하려는 데이터가 이미 메인 메모리에 적재되어 있으면 적중했다.

hit 과정

• Page Fault
  • 사용하려는 데이터가 메인 메모리에 적재되어 있지 않아서 예외가 발생한다.
  • Handler 호출 : 희생자 페이지를 선택하여 참조할 데이터를 적재할 수 있도록 한다.
  • page fault가 발생하면 전환하는 과정이 꼭 필요하다.
  • 지역성을 이용하여 miss rate를 줄인다.

falut 과정

• TLB : Translation Lookaside Buffer
  • MMU가 가상 주소를 번역하는 작업을 하기 위해서는 PTE에 무조건 참조해야한다.
  • 즉, 위의 번역 작업을 할때마다 해야하는 작업이므로 최악의 경우 메모리로부터 추가적인 선입작업이 필요하다.
  • MMU 속에 작은 cache를 두어 주소 번역 속도를 더 빨라지게 한다.
  • 빨라지는 이유 : on-chip MMU / 주소 번역을 하는 하드웨어 내에 캐시를 두어 매우 빠르게 PTE를 참조할 수 있도록 한다.