[공룡책🦖] ch9 Main Memory

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

---

Background

• 프로세스 = 실행 중인 프로그램으로, 메인 메모리에 로드되어 있는 상태
• 메모리 = large byte의 배열로 구성, 각 바이트에 주소 저장
• CPU = 프로그램 카운터가 지정한 주소에서 명령을 가져와 실행, 명령어에서 load나 store 같이 메모리에 접근하는 연산을 수행

 

Memory Space

멀티프로그래밍 및 멀티프로세서 환경에서는 메모리에 각 프로세스가 자신들의 메모리 공간을 사용하고 있다는 점이 중요하다.

• 메모리 주소 공간을 따로따로 관리해야하는게 멀티 프로세싱의 목적 ⇒ base resigter & limit register가 필요
  
  • 특정 메모리 주소에 접근하고자 할 때 주소가 base와 limit 사이에 존재하는 합법적인 주소 접근일 때만 접근 가능
  • 잘못된 접근인 경우 세그멘테이션 오류 (segmentation fault)가 발생하여 프로그램 중단

 

 

Address Binding

프로그램은 실행되기 전까지 단지 디스크에 저장되어있는 이진 실행파일에 불과하다. 실행을 위해 메인 메모리에 올라가면 비로소 프로세스가 된다.

• 프로그램에서 주소를 다루는 방식은 단계별로 다름
• binary executable file로 디스크에 프로그램이 저장
• 실행시키기 위해 프로그램을 메모리로 가져옴
  • 프로세스의 주소는 OS커널에서 지정하기 때문에 00000000주소에서 시작 되지 않음
  • 컴파일러는 프로그래머가 symbolic하게 작성한 소스코드 내 주소를 재배치 가능한 주소에 바인딩 
• 소스 코드 단계 (symbolic한 코드) → 컴파일 (재배치 가능한 주소) → 링커 (논리적 주소) → 로더 (물리적 주소)
  ⇒ 각 단계마다 다른 주소 바인딩이 이뤄짐

 

 

논리 주소 공간 vs 물리 주소 공간

• 논리주소 (logical address) : 사용자 프로세스에서 사용하기 위해 CPU에서 생성된 주소
• 물리주소 (physical address): 실제 하드웨어 상의 주소, 메모리 유닛에 의해 보이는 주소
  논리 주소와는 아무런 관계가 없어야 하며, 메모리 주소 레지스터 (memory-address register)에 저장되는 주소

 

논리 주소를 물리 주소에 매핑하기 위해서 논리 주소 공간과 물리 주소 공간이 분리되어야 한다.

 

 

 

MMU (Memory Management Unit)

• 논리 주소를 물리 주소로 map하는 하드웨어 장치
• 재배치 레지스터 relocation register 존재 (Base register in MMU)

 

 

Dynamic Loading

• 전체 프로그램과 데이터가 물리적 메모리에 있는게 필수인가?
• 메모리 주소 공간을 효율적으로 쓰기 위해 필요할때만 routine 호출하는 프로그램
• 재배치 가능한 링킹 로더 lining loader가 필요할 때마다 호출되어 주소 테이블(address table)에 변화 반영

 

 

 

동적 링킹(Dynamic Linking) & 공유 라이브러리(Shared Libraries)

• DLLs (Dynamically Linked Libraries)
  • 프로그램 실행 중간에 유저 프로그램이 링킹되어 사용할 수 있는 시스템 라이브러리
  • 실행 시 한번에 링킹되지 않고 라이브러리만 로딩된 상태에서 필요할 때 링킹됨
  • 공유 라이브러리 shared library로 부르기도 함
• 정적 링킹 static linking : 시스템 라이브러리가 다른 오브젝트 모듈처럼 한꺼번에 로더에 의해 이진 프로그램 코드로 합쳐짐
• 동적 링킹 dynamic linking : 동적 로딩과 비슷하게 링킹 작업을 실행 시간 (execution time)에 수행하는 것

 

 

 

Contiguous Memory Allocation

 

 

• 여러 사용자 프로세스에 동시에 메모리 있을 수 있기에 사용 가능한 메모리 할당해야함
• 연속 메모리 할당 ⇒ 단일 구역 (single section)에 할당하는 방식 (한 구역에 할당되어 있으므로 연속적임)
• 메모리 보호 ⇒ 재배치 레지스터와 한계 레지스터를 통해 이뤄짐

 

 

프로세스의 할당 & 해제를 반복하다보면 빈 공간이 생기는데, 이를 구멍 (hole)이라고 한다. 구멍을 잘 관리하는 것이 중요한데, 저장 공간에 동적으로 메모리를 할당 시 크기 n만큼의 메모리를 어느 구멍에 할당할지에 대한 문제가 발생한다.

 

 

3가지 해결 방법

1. 최초 적합 (first-fit): 구멍들을 탐색하다가 할당할 수 있는 가장 첫 번째 구멍에 할당하는 것
2. 최적 적합 (best-fit): 할당할 수 있는 가장 작은 구멍에 할당하는 것 (구멍들의 리스트를 우선순위 큐로 구현)
3. 최악 적합 (worst-fit): 할당할 수 있는 가장 큰 구멍에 할당하는 것

 

 

Fragmentation 단편화 문제

• 외부 단편화 (external fragmentation)
  • 많은 수의 작은 구멍로 메모리가 단편화됨
  • 메모리 공간이 조각조각 나눠져 있어 메모리 할당 요청을 받을 수 없는 상태
• 내부 단편화 (internal fragmentation)
  • 빈 공간에 메모리를 할당하고 난 뒤 공간이 남아 다른 메모리를 할당할 수 없는 상태

 

페이징을 하면 내부 단편화 문제가, 연속 메모리 할당을 하면 외부 단편화 문제가 발생한다.

 

 

 

Paging

프로세스의 물리적 주소 공간을 불연속적 (non-contiguous)으로 나눠 관리하는 것이다.

외부 단편화 문제를 해결할 수 있으며, 여러 곳에 나눠져 있는 공간을 압축할 필요도 없다. 메모리 할당과 관련된 부분이기 때문에 OS와 하드웨어의 도움을 받아 구현해야 한다.

 

 

Basic Method

• 물리 주소를 fixed-sized block으로 부서짐 (frames)
• 논리 주소를 같은 사이즈의 block으로 부숨 (pages)
• 논리 주소를 물리적 주소와 분리
• 논리 메모리에 있는 프로그램을 물리 메모리에 올릴 때 연속 할당처럼 메모리 조각을 물리 메모리의 위치에 맞게 올리기

 

기본적인 paging 방법

• 주소를 넘겨줄 때 페이지 번호, 오프셋을 넘겨줌
  • page number (p)
  • page offset (d)

→ p 페이지에 있는 d번째 메모리에 할당해줘

 

프로세스마다 페이지 개수가 다르기에 페이지 테이블을 통해 관리해야 한다.

 

 

 

CPU에 의해 이뤄지는 단계 

• CPU는 논리 주소로부터 페이지 번호(p)를 얻어 이에 해당하는 프레임 번호(f)로 변환
• 그 결과 논리 주소가 물리 주소로 매핑됨

 

 

페이지 사이즈 (like frame size)

• 하드웨어에 의해 정해짐
• 논리 주소 : 2^m, 페이지 사이즈 : 2^n
  • high-order 페이지 개수는 m-n bits
  • low-order 페이지 크기는 n bit

 

페이지 테이블의 경우 프로그램의 크기가 다양하고 커지면서 더이상 하드웨어만으로 페이지 테이블을 관리하는 것이 어려워졌다.  PTBR (page-table base register)을 따로 만들어서 페이지 테이블의 시작 주소를 가리키게끔 한다.

• 페이지 테이블에서 시작
• 페이지 테이블이 메인 메모리에 있음
• 컨텍스트 전환 빠르지만 메모리 접근 시간 느림

 

 

Translation Look-aside Buffer(TLB)

• CPU에서 페이지 테이블에 바로 접근하기보다는 TLB를 중간에 거쳐서 접근
• 캐시 메모리기에 매우 빠른 속도로 메모리 접근 가능
• TLB hit : 캐시 메모리에 페이지 번호 O
  발생시 빠르게 하드웨어적으로 물리 주소로 변환
• TLB miss : 캐시 메모리에 페이지 번호 X
  발생시 페이지 테이블에서 실제 값을 찾아 물리 주소로 변환
• hit ratio : 페이지 넘버 수 

TLB hit가 얼마나 발생했는지에 따른 hit ratio에 따라 유효 메모리 접근 시간 (effective memory-access time)이 달라진다.

 

 

 

Memory Protection with Paging

• 페이징을 사용할 경우 보호 비트 (protection bit)를 통해 프레임별로 메모리를 보호
• 하드웨어적으로 유효-무효 비트 (valid-invalid bit)를 각 프레임에 추가하여 메모리 접근이 유효한 접근인지 확인
  • 유효한 비트라면 합법한 페이지
  • 무효한 비트라면 불법한 페이지 → 트랩 (인터럽트)를 걸어버림 

 

 

Structure of the Page Table

현대적인 시스템의 경우 논리 주소 공간이 매우 크기 때문에 페이지 테이블 또한 매우 크다. 따라서 페이지 테이블을 구조화하는 것이 필요하다.

 

1. 계층적 페이징 Hierarchical Paging

• 페이지 테이블의 페이지 테이블을 만들어 관리
• 페이지 테이블 자체가 너무 커서 묶어서 관리하는 방법

 

2. 해시 페이지 테이블 Hashed Page Table

• 해싱을 하드웨어적으로 구현한 테이블
• 논리 주소의 p, d 값을 해시 함수를 통해 해시 값을 생성한 뒤, 이를 물리 주소의 값으로 사용하여 매핑
• 주소 공간의 크기가 32 bit를 넘어갈 때 자주 사용

 

 

3. 역 페이지 테이블 Inverted Page Table

• 프로세스의 주소를 통해 페이지 테이블에 접근하는 방식을 역으로 적용
• pid (process identifier)를 추가하여 해당 pid의 페이지를 역으로 저장

 

 

Swapping

• 물리 주소 공간 크기보다 초과하는 경우 스와핑을 사용해 문제 없이 실행
• 하나의 페이지만 메모리에 올라가면 되므로 프로세스 동시 실행 가능 → multiprogramming 의 차수를 증가
• 메모리에 엑세스할 때만 지원

 

표준 스와핑 Standard Swapping

• 전체 프로세스를 메인 메모리와 보조 기억장치 (backing store) 사이로 이동시킴
• swap out & swap in
  • swap out : 메인 메모리 → 보조 기억장치
  • swap in : 보조 기억 장치 → 메인 메모
• 전체 프로세스를 swap하는 비용 & 부담이 큰 작업 

Standard Swapping

 

 

페이징을 통한 스와핑 Swapping with Paging

• 프로세스를 페이지 단위로 swap
• 오늘날 페이징 = swapping with paging
• swap in, swap out 대신 page in, page out (페이지 단위) 
• paging은 가상 메모리에서 잘 쓰임

 

Swapping with Paging