[Operating System Concepts] Chapter9 Main Memory

너겟

 

 

1. Background
2. Contiguous Memory Allocation
3. Paging
4. Structure of the Page Table
   • Hierarchical Page
   • Hashed Page
   • Inverted Page Table
5. Swapping

 

---

 

Background

• CPU가 접근할 수 있는 저장장치는 메인 메모리(RAM)와 레지스터에만 접근 가능하다. 메인메모리 이외의 다른 저장장치에 대해서는 직접적으로 CPU가 접근 할 수 없다.
• CPU 가 레지스터에 접근하는 시간은 RAM에 접근하는 시간보다 빠르다. (그러나 캐시를 통해 빠르게 접근할 수 있도록 도와준다.)
• 메모리는 바이트의 배열로 구성 되어있고, 각각의 영역에 대한 주소를 가지고 있다. 명령어들은 메모리로부터 load, store 된다.
• 따라서, 하드웨어는 각 프로세스에 대해 메모리 영역을 침범하지 않고 할당해 주어야 한다. (base, limit 으로 제한을 준다)

#Hardware address Protection

Hardware address protection with base and limit registers

• 잘못된 접근인지 확인하고 잘못 접근하게 된다면, segmentation fault 출력하고 프로세스를 종료 시킨다.

 

#Address Binding
(Symbolic address → Virtual address → Physical address)

 

 

단계별로 바인딩이 다르고, 주체도 다르다.

• 변수명으로 지정한 곳이 메모리 공간에서, 기호를 통해서 메모리 주소공간에 써달라고 요청할 뿐이지, 어느번지에 있어야하는 것은 컴파일러가 알아서 지정해줘야 한다.
• 컴파일 시켜주기 전까지는 쓸모없는 정보에 불과하다. 메모리에 가지고 올라오면 그제서야 프로세스가 된다고 볼 수 있다.

1. .o 파일들에 대해 objective file이 생성되고, 컴파일 되는 과정에서 이걸 하나로 묶어서 ‘a.out’ 이라는 파일이 생성될 때 .o 에 있는 전역변수, 함수의 주소따위들이 주소가 할당된다. 이 과정에서 '심볼릭 주소' 에서 '논리주소' 로 바인딩 된다.
2. 'a.out' 실행 파일로 만들 때 '링커(linker)'가 하나의 주소 공간으로 바인딩 된다.
3. '로더(loader)'는 '절대 주소(물리 주소)'를 만들어준다.

 

• 유저 프로세스 가 사용하고 있는 주소(논리적 주소공간)을 하드웨어에 있는 주소 영역과 어떻게 매핑을 시켜줄 것인가에 대한 문제
  → relocation 을 해주기 위해서는 하드웨어와 OS의 역할이 크다.
• 논리적(logical)(= virtual memory) / 물리적(physical) 주소공간 에 대한 분리가 잘 이뤄져야한다. → MMU가 하는일

 

#MMU(Memory-Management Unit) : relocation register(virtual to physical)

• 논리주소에 존재하는 주소값들을, MMU를 경유하게 하여 논리주소를 물리주소로 변환할 수 있도록 한다.
• relocation register: base register in MMU
• 위의 예시로 346의 논리주소를 MMU에서 받고 14000으로 설정된 MMU에서 메모리 위치에, '10' 을 쓰라고 해석할 수 있다. 

 

#Dynamic Loading

• 프로그램을 사용하기 위해, 항상 메모리를 물리주소로 바인딩 시켜주는 작업은 효율적이지 않다.
• 메모리 주소공간을 효율적으로 사용하기 위한 방법으로 고안된 것이 'dynamic loading' 이다.
• 루틴이 필요해서 불러오기 전까지는 가만히 있는다. 불러온 루틴들만 address table에 반영해준다.

 

#Dynamic Linking and Shared Libraries(DLL)

• 실행되는 도중에 라이브러리가 링킹되는 것을 의미함
• 가령, object file 을 모두 묶어서 .exe 파일로 만들어 줄 수 있다. printf 따위는 실행파일안에 포함된다. 그러나, fork, wait 같은 시스템 콜은 포함되면 실행하다가 정의되어있는 .dll 파일에서 가져온다.
• linux 에서는 .so windows 에서는 .dll 파일로 존재함 (Mac OS는 .dylib)

Contiguous Memory Allocation

• 메인메모리는 가능한 효율적인 방법으로 할당해야 한다.
• 메모리는 두 파티션으로 나뉘어진다. 하나는 OS로, 다른 하나는 user process로 구분된다.
• 메모리를 프로세스한테 할당을 해줘야하는데, 메인 메모리에 user process를 한꺼번에 로딩할 수 있도록 메모리에 옮겨가는 과정을 Contiguous Memory Allocation(연속 메모리 할당)이라고 한다.
• 여러 user process는 메모리에 동시에 올라가야 하기 때문에, 어떻게 할당해야 하는지가 문제가 된다.
• 통짜로 올리기 때문에 single section of memory가 생긴다 (단편화 문제는 적어도 존재하지 않게된다).

#Memory Protection

• 프로세스가 할당된 메모리 이외의 다른 메모리를 참조할 수 없도록 해야한다.
• relocation register + limit register 을 통해 메모리 영역 위치를 조절한다.

 

#Memory Allocation

 

• 프로세스가 종료될 때마다, 빈 공간이 생김 → 이러한 빈 공간들을 어떻게 관리할것인가?

 

#Problem of Dynamic Storage Allocation

• 여러개의 free hole이 존재하고 있을 때 n개의 (메모리 할당에 대한) 요청을 어떻게 처리할 것인가?

1. First-Fit : 일단 맞는거를 최초로 맞춘다.
2. Best-Fit : 가장 작은것 부터 찾아나간다. (우선순위 큐를 생성하여 찾아나가는 방법)
3. Worst-Fit : 가장 큰 곳에다가 넣는다.

 

#Fragmentation

단편화 문제에 GC를 쓰기에는 상당히 번거로운 부분이다. 다른 방법으로 두가지 해결책을 제시한다.

 

1. external fragmentation (외부 단편화)

• 많은 개수의 작은 공간들이 존재한다. 메모리는 존재하지만 사용이 불가능한 상태이다.
• 외부 단편화는 주로 first, best, worst fit 알고리즘을 사용할 때 발생하고, 최대 전체의 1/3의 메모리가 낭비될 수 있다.
• 만약, 프로세스가 동적으로 메모리를 이동가능할 수 있다면 OS 는 외부 단편화를 최대한 줄여서 '사용가능한 영역'을 최대화 해야한다.
  (Contiguous Memory allocation)

2. internal fragmentation (내부 단편화)

• 프레임 안에 남아 있는 것들이다. 메모리 내부에 할당되었지만 사용되지 않는 것을 의미한다. (Paging 기법으로 해결한다)

연속적으로 메모리 할당하는 방법과 페이징 기법(메모리영역을 쪼개는 방법 추후서술) 중간에 구획화(Segmentation) 방법이 존재한다. 이는 분류를 나누어서 페이징하는 기법인데 페이징 기법만큼 효과적이지 않다.

 

Paging

• 페이징은 메모리관리를 만들고않고 쪼개버리는 것이다. 페이징을 통해 두가지 효과를 얻을 수 있다.
  • '외부 단편화'를 피할 수 있다.
  • 압축시키기 위한 별도의 노력이 필요 없다.
• Paging 기법은 OS 와 하드웨어를 통해 제공해준다.
• 컴파일러가 알아서 논리주소만 접근 가능하게 해두면 물리주소의 매핑은 운영체제가 알아서해준다.
  (물리주소를 고정된 사이즈의 블록으로 나눈다.(frames) / 논리주소를 같은 사이즈의 블록으로 나눈다.(pages))
• 페이징을 사용함으로써 논리주소와 물리주소는 서로 분리된다.

 

#Basic Method for Paging

• 모든 주소는 CPU에 의해 두가지 파트로 나뉘어진다.
  
  • 페이지 갯수 (p)
  • 페이지 오프셋 (d)

• page number는 페이지 테이블에 따로 관리되어야 함. 몇번 페이지에 몇번 오프셋에 있는지 찾아가는 과정을 가진다.
  1. 기록된 p, d 주소에서 p만큼의 오프셋을 페이지 테이블에서 찾고 f라고 가정한다.
  2. 또한, 프레임 f에서의 d의 오프셋만큼 떨어져 있는 물리주소를 가져오면 된다.

• 순서에 상관없이 논리적으로 프로그램이 로드되어있다. (파란색 부분은 free-hole)

#page size

• 페이지 사이즈를 구하는 방법과 프레임 사이즈를 구하는 방법과 동일하다.
• 2^n 을 가지는 페이지 사이즈는 high-order bit 와 low-order bit를 구분하여 페이지 넘버, 페이지 오프셋 을 구분한다. 
  • high-order m-n 비트는 페이지 넘버로 할당된다.
  • low-order n 비트는 페이지 오프셋으로 할당된다.

n=2, m=4 로 설정된 32-byte 메모리를 가지는 프로그램이다.

• 하드웨어에서 CPU 스케쥴러가 프로세스를 선택하여 실행을 하려고 할 때, 페이지 테이블은 갱신되어 컨텍스트 스위칭이 일어난다.
• 페이지 테이블에서의 포인터는 각 프로세스의 PCB 내부에 있는 register값이 저장된다.

 

#PTBR (page-table base register)

• 페이지 크기가 매우 큰 프로세스들을(구글 크롬 등..) 관리하는 것도 일이다.
• 해결하기 위한 아이디어로 PTBR(Page Table Base Register)을 통해 페이지 테이블을 생성
• ptbr만 pcb에 저장하면 되기 때문에 컨텍스트 스위칭 할 때도 빠르다.  
• 메모리 엑세스는 느리다. 페이지 테이블접속과 실제 데이터를 엑세스 하기 때문에 느려진다.

#TLBR(Translation 'Look-aside' Buffer)

Redis 캐시를 'Look Aside'로 놓는법 : https://mola2.tistory.com/41

• 캐시메모리를 활용하여 이전보다 빠르게 연산하는 방법이 있다.
• TLB hit : 찾고자 하는 페이지 번호가 TLB 내부에 존재할 때를 의미함
• TLB miss : 찾고자 하는 페이지 번호가 TLB 내부에 존재하지 않을 때를 의미함
• 적중률(hit ratio) 따라서 메모리 접근 시간이 빨라진다. (적중하면 10ns, 적중하지 않으면 20ns 가 걸린다고 할 때)
  • 80% 적중률: EAT = 0.8 * 10 + 0.20 * 20 = 12 ns
  • 99% 적중률: EAT = 0.99 * 10 + 0.01 * 20 = 10.1 ns

#Memory Protection with Paging

페이징이 들어올 때에 대한 valid-invalid 를 검증할 수 있는 비트를 추가해서 유효성을 검증한다.

• 페이징이 들어오면 유효함(legal) 못들어오면 무효(illegal)
• 페이징이 들어오게 된다면 protection bit 추가해주어야함
• 하드웨어서부터 valid 한지 알아봐야함 → 모두 검증이 완료되면 해당되는 페이지는 legal하다고 판단.
• 만약, 무효한 주소 (illegal address)가 들어온다면 트랩 걸어준다.

각각 legal, ilegal 한 경우를 나타냈다.

 

#Shared Pages (reentrant code)

• 페이지 쉐어링은, .dll 등 동일한 코드를 공유하기 좋은 상황에 유리함
• C 의 라이브러리인 libc 모든 프로세스가 카피를 가지고 있다고 생각했을 때 공유하는 방법 'reentrant code'
• 'reentrant code' 는 실행중에 자신을 바꿀 가능성이 없는 코드들을 의미함 (런타임 도중에 변하지 않음)

 

libc 라는 물리적인 공간을 카피하는게 아니라 논리적인 공간을 참조한다.

• 동시성이 안 생기나요? → reentrant한 읽기만 하는 공간이라 데드락 등 동기화 문제가 전혀 생기지 않는다.

 

Structure of the Page Table (Hierarchical, Hashed, Inverted)

매우 큰 논리 주소의 공간을 사용할 때, 매우 큰 영역을 참조할 수 있는 페이지 테이블을 만든다.

 

Hierarchical Paging

Two-level page-table scheme

• 논리주소의 영역을 여러개의 테이블로 나누는 것을 의미한다.
• 페이징 테이블이 너무 커지면, 페이징 테이블 내부의 페이징 테이블을 거쳐서 만들어 나간다.

 

Hashed Page Tables

Hashed Page Table

• 32비트 값보다 더 큰 주소공간을 다룰 때에, 가장 좋은 자료구조는 해시 테이블(hash table)이다.
• 해시 테이블을 통해서 해시값을 통해 물리적인 주소를 얻어낸다.

 

Inverted Page Table (pid 추가됨, 가장 유용함)

• 페이지 테이블이 너무 클 경우에 대해 처리해준다.
• pid가 어떤 page를 가지고 있는지를 대해 역으로 저장하면 더 효율적이다.

 

Swapping

• 조금만 로딩하다가 쓰고 필요한걸 쓰고 다시 올리는 식으로 한다. Swap in ↔ Swap out
• 여기에서 '가상 메모리'를 사용할 수 있다.
• 프로세스 전체를 Swap in / out 하는것은 부담되는 작업이다 → 페이징을 사용하면 더 효율적이게 할 수 있다.
• 페이징은 가상 메모리 사용에 있어서 큰 위력을 발휘한다.