메모리 관리

메모리

메모리의 종류

✨ Logical address (논리적 주소 , =virtual address)

• 프로세스마다 독립적으로 가지는 주소 공간
• 각 프로세스마다 0번지부터 시작
• CPU가 생성하는 주소
• CPU가 보는 주소는 logical address

✨ Physical address (물리적 주소)

• 프로그램이 실행되기 위해 메모리(RAM)에 실제 올라가는 위치

📌 Logical address에서 Physical address로 변환하는 것은 하드웨어가 하는 일이다
📌 주소 바인딩 : 주소를 결정하는 것

 Symbolic Address → Logical Address → Physical address
                                     ↑
  프로그래머가 바라보는              이 시점이
         주소                      언제인가?                               

주소 바인딩

✨ Compile time binding

• 물리적 메모리 주소(physical address)가 컴파일 시 알려짐

• 컴파일러는 절대 코드(absolute code), 즉 고정된 주소를 생성한다

• 시작 위치 변경시 재컴파일

• Compile time binding은 프로그램 내부의 논리적 주소와 메모리상 물리적 주소가 동일하다

  🏴 문제점 : 주소가 고정되어 있기 때문에 메모리 상에 빈 공간이 많이 발생할 수 있어 비효율적이고, 로드하려는 위치에 이미 다른 프로세스가 존재할 수 있다.

✨ Load time binding

• 프로그램이 실행되는 시점
• Loader의 책임하에 물리적 메모리 주소 부여
• 컴파일러가 재배치가능코드(relocatable code)를 생성한 경우 가능
  Relocatable code는 메모리의 어느 위치에서나 수행될 수 있는 기계 언어 코드이다.

✨ Execution time binding (=Run time binding)

• 프로그램 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
• CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table)
• 하드웨어적인 지원이 필요
  (e.g., base and limit registers, MMU).

Memory Management Unit (MMU)

✨ MMU (Memory-Management Unit)란?

• logical address를 physical address로 매핑해주는 Hardware device

✨ MMU scheme

• 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register (=relocation register)의 값을 더한다

✨ user program

• logical address만을 다룬다
• 실제 physical address를 볼 수 없으며 알 필요가 없다

간단한 주소 변환

현대적 주소변환은 이렇게 간단하지 않다. 지금의 소개에는 메모리에 올라갈 프로세스의 주소들이 하나로 묶여서 올라가지만 현대의 운영체제 하에서는 쪼개져서 필요한 부분만 메모리로 올라가고 나머지는 디스크의 스왑영역에 저장된다.

basic register는 physical address의 프로세스 주소 최소값(14000)을 알고있고, 그 프로세서의 논리적 주소의 범위를 Limit register가 저장(3000).
346번만큼 올라가있는 주소를 더하면 바로 답이 나온다.

📌 Relocation register(= base register) 접근할 수 있는 물리적 메모리 주소의 최소값

📌 Limit register 논리적 주소의 범위 , 잘못된 메모리를 참조를 막아주는 기능을 한다

Some Terminologies

• Dynamic Loading

  1. 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것
  2. memory utilization의 향상
  3. 가끔씩 사용되는 많은 양의 코드의 경우 유용
     • 예: 오류 처리 루틴
  4. 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능 (OS는 라이브러리를 통해 지원 가능)
     'Loading: 메모리로 올리는 것'

• Dynamic Linking

  Linking : 내가 만든 코드와 library가 링크돼서 이루어 지는것

  1. Linking을 실행 시간(execution time)까지 미루는 기법
  2. Static linking (<- static library)
     • 라이브러리가 프로그램의 실행 파일 코드에 포함됨
     • 실행 파일의 크기가 커짐
     • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비 (eg. printf 함수의 라이브러리 코드)
  3. Dynamic linking (<- shared library) .so(linxu, shared object) .dll (windows, dynamic linking library)
     • 라이브러리가 실행시 연결(link), 실행 파일에 라이브러리가 포함 안됌
     • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
     • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
     • 운영체제의 도움이 필요

• Overlays (대단히 메모리가 작전 시절의 이야기)

  1. 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림
  2. 프로세스의 크기가 메모리보다 클 때 유용
  3. 운영체제의 지원없이 사용자에 의해 구현
  4. 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현
     ✓ "Manual Overlay"
     ✓ 프로그래밍이 매우 복잡

• Swapping

  1. 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것
  2. Backing store (=swap area)
     • 디스크 : 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
  3. Swapin/Swap out
     ✓ 일반적으로 중기 스케줄러 (swapper)에 의해 swap out 시킬 프로세스 선정
     ✓ priority-based CPU scheduling algorithm
     • priority가 낮은 프로세스를 swapped out 시킴
     • priority가 높은 프로세스를 메모리에 올려 놓음
     ✓ Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야 함(Swapping에 제한이 있다)
     ✓ Run time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음
     ✓ swap time은 대부분 transfer time(데이터 전송 시간)임

  여기서 말하는 Swapping은 통째로 쫒아내는 것을 의미. 현대적인 Swapping 방법은 통째로 쫒아내기도 하지만 부분부분 쫒아내는 것.

물리적 메모리

물리적 메모리의 관리 기법

✨ 메모리는 일반적으로 두 영역으로 나뉘어 사용

• OS 상주 영역
  ✓ interrupt vector와 함께 낮은 주소 영역 사용
• 사용자 프로세스 영역
  ✓ 높은 주소 영역 사용

✨ 사용자 프로세스 영역의 할당 방법

• Contiguous allocation (연속 할당)
  : 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
  ✓ Fixed partition allocation (고정 분할 방식)
  ✓ Variable partition allocation (가변 분할 방식)

• Noncontiguous allocation (불연속 할당)
  : 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
  ✓ Paging
  ✓ Segmentation
  ✓ Paged Segmentation

Contiguous Allocation

실제 현대의 운영체제에서는 사용하지 않는 방식

✨ 고정분할(Fixed partition) 방식

• 물리적 메모리를 몇 개의 영구적 분할(partition)로 나눔
• 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
• 분할당 하나의 프로그램 적재
  융통성이 없음
• 동시에 메모리에 Ioad 되는 프로그램의 수가 고정됨
  최대 수행 가능 프로그램 크기 제한
  Internal fragmentation 발생 (external fragmentation도 발생)

✨ 가변분할(Variable partition) 방식

• 프로그램의 크기를 고려해서 할당
• 분할의 크기, 개수가 동적으로 변함
• 기술적 관리 기법 필요
• External fragmentation 발생

📌 External fragmentation (외부 조각)

• 프로그램 크기보다 분할의 크기가 작은 경우
• 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할

📌 Internal fragmentation (내부 조각)

• 프로그램 크기보다 분할의 크기가 큰 경우
• 하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각
• 특정 프로그램에 배정되었지만 사용되지 않는 공간

✨ Hole

• 가용 메모리 공간
• 다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있음
• 프로세스가 도착하면 수용가능한 hole을 할당
• 운영체제는 다음의 정보를 유지
  a) 할당 공간 b) 가용 공간 (hole)

✨ Dynamic Storage-Allocation Problem
: 가변 분할 방식에서 size n인 요정을 만족하는 가장 적절한 hole을 찾는 문제

1. First-fit

• Size가 n 이상인 것 중 최초로 찾아지는 hole에 할당 (빠르게 결정)

2. Best-fit

• Size가 n 이상인 가장 작은 hole을 찾아서 할당
• Hole의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야함 (탐색의 오버헤드)
• 많은 수의 아주 작은 hole 들이 생성됨

3. Worst-fit

• 가장 큰 hole에 할당
• 역시 모든 리스트를 탐색해야 함 (오버헤드)
• 상대적으로 아주 큰 hole들이 생성됨

💡 First-fit best-fit worst-fit보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려짐 (실험적인 결과)

✨ compaction

• external fragmentation 문제를 해결하는 한 가지 방법
• 사용 중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것
• 매우 비용이 많이 드는 방법임
• 최소한의 메모리 이동으로 compaction하는 방법 (매우 복잡한 문제)
• Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우(Run time binding)에만 수행될 수 있다.

Noncontiguous allocation

프로그램을 구성하는 주소공간이 짤려져서 서로 다른 주소환경에 올라 갈 수 있다.
✨ Paging

• Process의 virtual memory를 동일한 사이즈의 page단위로 나눠 메모리에 올림
• Virtual memory의 내용이 page 단위로 noncontiguous하게 저장됨
• 일부는 backing storage에, 일부는 physical memory에 저장

✨ Basic Method

• physical memory를 동일한 크기의 frame으로 나눔
• logical memory를 동일 크기의 page로 나눔 (frame과 같은 크기)
• 모든 가용 frame들을 관리
• page table을 사용하여 logical address를 physical address로 변환
• External fragmentation 발생 안함
• Internal fragmentation 발생 가능

Paging Example

Address Translation

Page Table의 구현

• Page table main memory에 상주

• Page-table base register (PTBR)가 page table을 가리킴

• Page-table length register (PTLR)가 테이블 크기를 보관

• 모든 메모리 접근 연산에는 2번의 memory access 필요

• 주소 접근을 위해 page table 접근 1번, 실제 data/instruction 접근 1번

• 속도 향상을 위해 associative register와 translation look-aside buffer(TLB)라 불리는 고속의 lookup hardware cache 사용

  

  Page table은 인덱스를 통해 빠르게 서치 가능하지만 TLB는 인덱스가 없기때문에 논리적인 페이지 번호와 프레임 넘버를 쌍으로 가지고 있어야 한다.

  TBL를 일일이 하나씩 서치하는 것은 오버헤드가 너무 크다. 그래서 TLB는 병렬적 서치를 가능하게 해주는 associative register를 사용해 병렬적 서치를 한다.
  

Associative Register

• Associative registers (TLB): parallel search
  ✓ TLB에는 page table 중 일부만 존재
• Address translation
  ✓ page table 중 일부가 associative register에 보관되어 있음
  ✓ 해당 page#가 TBL에 있는 경우 곧바로 frame#를 얻음
  ✓ 그렇지 않은 경우 main memory에 있는 page table로부터 frame #를 얻음
  ✓ TLB는 context switch 때 flush(remove old entries) 된다.
  • 왜 flush 되나? -> 다른 프로세스의 page table을 저장해야됨.

Effective Access Time

 TLB 접근 시간 = ε
 메모리 접근 시간 = 1

 α는 대단히 1에 가까운 값을 가지고 있다.
 (TLB를 통해 주소 변환이 이루어지는 확률) Hit ratio = α
 (TLB를 통해 주소 변환이 이루어지지 않는 확률) TLB miss ration = 1-α
  
 Effective Access Time(EAT)
 EAT = (1+ε)ε + 2(+ε)(1-α) = 2+ε-α

✨ Structure of the Page Table
현대의 컴퓨터는 address space가 매우 큰 프로그램 지원

• 32 bit address 사용시 : 2³²(4GB)의 주소 공간
• page size가 4K시 100만개가 조금 넘는 page table entry 필요
• 각 page entry가 4B시 프로세스당 4Mb의 page table 필요
• 그러나, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비됨

1. Two-level page talbe

→ page table과 메모리 사이에 page table을 하나 더 둠으로써 총 세번의 메모리 로드를 거치는 방법이다. 얼핏 듣기에는 2번을 로드하는 것 보다 안좋게 느껴질수 있다.

→ 하지만 100만개가 넘는 page table중 실제 사용되는 것은 정말 얼마 되지 않지만 기존은 전부 로드 했어야 됐다.

→ Two-level page table은 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 Null로 나타낸다(대응하는 inner page table이 없음)

→ 이를 통해 모든 page를 로드해야 하는 부담을 줄일 수 있다.

→ 기존에는 32 bit 논리적 주소 공간이라면, 20 bit는 page number, 12 bit는 page offset을 나타냈는데, Two-level인 경우, page table 자체가 page로 구성되기 때문에 page number는 10 bit의 page number와 10 bit의 page offset으로 또 나뉘게 된다.

→ 2단계 페이징에서의 Address-translation scheme

• Address space가 더 커지면 다단계 페이지 테이블 필요
• 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 hysical address 변환에 더 많은 메모리 접근 필요

더 많은 메모리 접근이 필요하다면 이걸 사용할 필요가 있을까???

• TLB를 통해 메모리 접근 시간을 줄일 수 있음
• 4단계 페이지 테이블을 사용하는 경우
  ex) 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns이고 TLB hit ratio가 98%인 경우
  effective memory access time(eat)= 0.98 x 120 +0.02 x 520 = 128 nanoseconds.
  결과적으로 주소변환을 위해 28ns 소요
  

2. Inverted Page Table

• 물리적인 주소를 가지고 논리적인 주소를 얻어 내는 페이지 테이블(역방향으로 되어있다.)

• page table은 각 page마다 하나의 항목을 가졌다. 반대로 Inverted page table은 메모리의 frame마다 한 항목씩 할당.

• physical frame에 대응하는 항목만 저장하면 되므로 메모리를 훨씬 적게 사용한다. (장점)

• 각 page table entry는 각각의 메모리의 frame이 담고 있는 내용(PID, logical address)을 표시한다.

  🏴 단점 : 테이블 전체를 탐색해야 하므로 시간이 오래 걸린다.(associative register 사용해서 문제해결 가능. 다만 비싸짐) 어떤 프로세스의 주소인지도 함께 가지고 있어야됨.
  

3. Shared Pages Example

• 똑같은 프로그램의 코드들이 중복해서 올라가는 것을 방지한다.

• Shared code
  ✓ Re-entrant Code (=Pure code)
  ✓ read-only로 하여 프로세스 간에 하나의 code만 메모리에 올림
  (eg, text editors, compilers, window systems).
  ✓ Shared code는 모든 프로세스가 logical address space(논리주소공간)을 가져야 된다.

• Private code and data( Shared Code의 반대)
  ✓ 각 프로세스들은 독자적으로 메모리에 올림
  ✓ Private data는 logical address space의 아무 곳에 와도 무방

✨ Segmentation

• 프로그램은 의미 단위인 여러 개의 segment로 구성
  ✓ 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
  ✓ 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능

• 일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의됨

Segment는 다음과 같은 logical unit 들임
  
  main (),
  function,
  global variables,
  stack,
  symbol table, arrays

✨ Segmentation Architecture

• Logical address는 다음의 두 가지로 구성 : < segment-number, offset >

• Segment table
  ✓ each table entry has :
  base-starting physical address of the segment
limit-length of the segment

• Segment-table base register (STBR)
  ✓ 물리적 메모리에서의 segment table의 위치(시작 위치)

• Segment-table length register (STLR)
  ✓ 프로그램이 사용하는 segment의 개수 : segment number s is legal if s smaller then STLR
  

✨ Segmentatino Hardware

📌 Paging 기법과 시작위치만 담고 있는 것이 아니고 Segment의 길이(limit)를 가지고 있어야됨. paging에서는 크기가 다 똑같으니 가지고 있을 필요가 없었지만 Segmentation에서는 segment의 크기가 같지 않으므로 얼마만큼에 걸쳐 존재하는가를 담고 있어야됨.

Example of Segmentation

프로세스가 5개의 세그먼트로 이루어진 예제

📌 Allocation 문제 : external fragmentation 발생
Segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제들이 발생.
ex) frist fit/ best fit 등의 방법 사용

📌 Protection : 각 세그먼트별로 protection bit가 있음.

Each entry :
  Valid bit = 0 => illegal segment
  Read/Write/Execution 권한 bit

📌 Sharing

• shared segment
• same segmentnumber
  *** Segment는 의미 단위. 의미 단위로 해야하는 공유(Sharing)와 보안(Protection)에 있어 paging보다 훨씬 효과적임.

Segment에서의 Sharing

💡 세그멘테이션은 코드와 데이터의 논리적 구성을 더 잘 지원하고 세그먼트 사이를 Protection하는 것과 같은 이점이 있지만 단순성, 조각화 방지 및 하드웨어 지원 측면에서 페이징의 이점으로 인해 페이징 기법이 지배적인 기술이 되었다.

현대 시스템에서는 세그먼테이션과 페이징의 조합을 사용하여 두 기술의 장점을 결합

Segmentation with Paging

• 기본적으로 Segmentation방법을 사용
• Segment가 물리적 메모리에 올라간는 것이 아닌 여러개의 Page로 올라간다
• 메모리는 동일한 크기에 페이지로 관리
• 의미 단위로 관리하는 것은 Segment table로 관리

공유나 보안 문제는 Segment로 해결. Allocation의 external fragmentation은 Paging단위로 올라가기에 발생하지 않음.