[OS] 메모리 관리(Memory Management)

⚙️ Logical Address / Physical Address

• Logical Address(=Virtual Address)

  • 프로세스마다 독립적으로 가지는 주소 공각

  • 각 프로세스마다 0번지 부터 시작

  • CPU가 보는 주소는 logical address

    CPU는 instruction을 실행해야 되기 때문에 컴파일 된 코드에 들어 가 있는 Logical Address를 읽어들임

• Physical Address

  • 메모리에 실제 올라가는 위치

주소 바인딩이란? 주소를 결정하는 것(물리적인 메모리 주소가 정해지는 것)

• Symbolic Address
• Logical Address
• Physical Address
  실제 프로그래머는 숫자로 된 주소(Logical Address)를 사용하지 않고 Symbolic Address를 사용함. 예를 들어 프로그래밍을 할때 메모리 어디에 위치 해 있는 변수를 가져와 이런 식으로 명령하지 않고 변수명을 이용해서 값을 메모리에 할당하고 가져다 씀.
  Symbolic Address가 컴파일되면 Logical Address로 변환됨
  이제 프로그램이 실제 실행이 되려면 물리적인 메모리에 올라가야 하기 때문에 Physical Address로 주소변환이 실행됨

📌 Address Binding

물리적인 주소로 바인딩 되는 것인 주소 변환 시점에 따라 세가지로 나누어 볼 수 있음

• Compile time binding

  • 컴파일 시 주소변환이 실행되는 것
  • 물리적 메모리 주소(Physical Address)가 컴파일 시 알려짐
  • 시작 위치 변경 시 컴파일을 다시 해야함
  • 컴파일러는 절대 코드(Absolute Code) 생성
  • 현대의 시스템에서는 사용되지 않음

• Load time binding

  • 프로그램이 시작될 때 주소변환이 실행되는 것
  • Loader의 책임 하에 물리적 메모리 주소 부여
  • 컴파일러가 재배치가능 코드(Relocatable Code)를 생성한 경우 가능

• Execution time binding(=Run time binding)

  • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
  • CPU가 주소를 참조할 때마다 binding을 점검(Address Mapping Table)
  • 하드웨어적인 지원이 필요
  • 현대의 시스템에서 사용하는 바인딩 방식

🛠 Memory-Management Unit(MMU)

• MMU(Memory-Management Unit)
  logical address를 physical address로 매핑해주는 Hardware Device

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

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

• MMU는 register 2개를 이용해 주소 변환을 하게 된다.
  relocation register(=base register), limit register

Dynamic Relocation

• 프로그램이 메모리에 올라갈 때 통째로 올라가는 것을 전제로 함(Allocation of Physical Memory)
• 컴파일된 코드에 있는 instruction은 Logical Address를 사용하기 때문에 CPU가 요청을 할 때도 Logical Address를 이용해서 요청하게 됨
• 프로그램 크기 보다 더 큰 논리 주소를(relocation register + limit register) 요청하게 되면 trap이 걸리게 된다.
• 메모리에서 주소는 byte 단위

Hardware Support for Address Translation

Dynamic Loading

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

Overlays

• 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림
• Dynamic Loading과의 차이점?
  Overlays는 사용자가 직접 코드를 짜는 반면 Dynamic Loading은 라이브러리를 이용한다.
• 프로세스의 크기가 메모리보다 클 때 유용
• 운영체제의 지원 없이 사용자에 의해 구현

Swapping

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

Dynamic Linking

• Linking을 실행 시간(execution time)까지 미루는 기법

• Static Linking

  • 라이브러리가 프로그램의 실행 파일 코드에 포함됨
  • 실행 파일의 크기가 커짐
  • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로메모리 낭비(eg. printf 함수의 라이브러리 코드)

• Dynamic Linking

  • 라이브러리가 실행시 연결(link)됨
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
  • 운영체제의 도움이 필요

Allocation of Physical Memory

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

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

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

  • Contiguous Allocation(연속 할당) : 각각의 프로세스가 메모리의 연속적인 공간 에 적재되도록 하는 것
    • Fixed Partition Allocation
    • Variable Partition Allocation
  • Noncontiguous Allocation(불연속 할당) : 하나의 프로세스가 메모리의 여러 영 역에 분산되어 올라갈 수 있음
    • Paging
    • Segmentation
    • Paged Segmentation

Contiguous Allocation

• Fixed Partition(고정 분할 방식)
  • 물리적 메모리를 몇 개의 영구적 분할(Partition)로 나눔
  • 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
  • 분할 당 하나의 프로그램 적재
  • 융통성이 없음
    • 동시에 메모리에 load되는 프로그램의 수가 고정됨
    • 최대 수행 가능 프로그램 크기 제한
  • internal fragmentation 발생(external fragmentation도 발생)
• Variable Partition(가변 분할 방식)
  • 프로그램의 크기를 고려해서 할당
  • 분하르이 크기, 개수가 동적으로 변함
  • 기술적 관리 기법 필요
  • External fragmentation 발생

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

• First-fit

  • Size가 n 이상인 것 중 최초로 찾아지는 hole에 할당

• Best-fit

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

• Worst-fit

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

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

Compaction
: 사용 중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것

• external fragmentation 문제를 해결하는 한 가지 방법
• 매우 비용이 많이드는 방법
• 최소한의 메모리 이동으로 Compaction하는 방법(매우 복잡한 문제)
• Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다.

Noncontiguous Allocation

불연속 할당 기법은 크게 Paging기법과 Segmentation기법으로 나눌 수 있음

📌 Paging

하나의 프로그램을 구성하는 주소공간을 같은 크기의 페이지로 자르는 것.

• Process의 virtual memory를 동일한 사이즈의 page단위로 나눔
• Virtual memory의 내용이 page 단위로 noncontiguous하게 저장됨
• 일부는 backing storage에, 일부는 physical memory에 저장
• physical memory에 있는 page 저장 공간은 page frame이라 부름
• 장점
  한 페이지의 크기는 균일하게 4KB이기 때문에 프로그램을 할당할 때 크기를 고려할 필요 없음
• 단점
  주소변환을 페이지 별로 해야되기 때문에 주소변환이 복잡해짐
• Basic Method
  • physical memory를 동일한 크기의 frame으로 나눔
  • logical memory를 동일 크기의 page로 나눔(frame과 같은 크기)
  • 모든 가용 frame들을 관리
  • page table을 사용하여 logical address를 physical address로 변환
  • External fragmentation 발생 안함
  • Internal fragmentation 발생 가능

• 주소 변환을 위해서 page table을 사용하며 page table은 논리적 페이지들이 물리적 메모리 어디에 위치해 있는지 알려줌
• 테이블은 배열을 의미(실무에서는 배열이란 단어보다 테이블이란 단어를 사용)
• page table은 logical memory의 page 개수만큼 entry 생성
• 위와 같은 이유로 page table은 메인메모리나 캐시메모리에 위치하기엔 크기가 크기 때문에 물리적 메모리주소에 위치함

• 논리주소에서 앞부분은(p,f) 페이지 번호, 뒷부분(d)은 페이지 내의 거리(offset)을 나타냄
• 페이지 내에서의 offset(d) 부분은 주소변환에서 영향이 없음
• TLB(Translation Lookaside Buffer)는 주소변환을 위한 별도의 캐시메모리
• 자주 참조되는 페이지의 주소를 캐싱하고 있음
• 따라서 CPU는 가장 먼저 TLB를 먼저 조회함
• TLB는 모든 페이지 주소를 가지고 있는 것이 아니기 때문에 논리적 / 물리적 페이지 주소를(p,f) 쌍으로 지님

* cache memory는 운영체제한테는 감추어진 계층(Transparent 계층)

🚧 Implementation of Page Table

• Page table은 main memory에 상주
• page table은 프로세스마다 있음
• MMU에서의 2개의 레지스터는(relocation register / limit register)는 페이징 기법에서 PTBR과 PTLR로 사용됨
• 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 사용

🚧 Associative Register

• Associative Registers(TLB) : parallel search(병렬 검색)가 가능

  • TLB에는 page table 중 일부만 존재
  • 따라서 주소변환하려는 논리적 주소가 TLB에 존재하는지 빠르게 검색해야하기 때문에 병렬검색 이 가능하게 구현

• Address translation

  • page table 중 일부가 associative register에 보관되어 있음
  • 만약 해당 page #가 associative register에 있는 경우 곧바로 frame#를 얻음
  • 그렇지 않을 경우 main memory에 있는 page table로부터 frame#를 얻음
  • TLB는 context switch 때 flush(remove old emtries)

🚧 Effective Access Time

• TLB에 접근하는 시간을 엡실론이라 했을 때 엡실론은 메인 메모리에 접근하는 시간인 1보다 작다.

🚧 Two-Level Page Table

• page table이 2단계로 구성(outer-page table / inner-page table)
• 왜 사용할까?
  컴퓨터에서는 보통 목적이 2가지(속도를 빠르게 / 공간 절약)
  Two-Level Page Table은 공간을 줄이기 위해 사용
• 현대의 컴퓨터는 address space가 매우 큰 프로그램 지원

  • 32bit address 사용시 : 2의 32승(4G)의 주소 공간

    • page size가 4k일 시 1M개의 page table entry 필요
    • 각 page entry가 4B 시 프로세스 당 4M의 page table 필요
    • 그러나 대부분의 프로그램은 4G 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비됨

-> page table 자체를 page로 구성
-> 사용되지 않는 주소 공간에 대한 outer page table의 entry 값은 NULL (대응하는 inner page table이 없음)

논리적 주소를 바깥쪽 페이지 테이블에서 처리할 때 얻어지는 것은 안쪽 페이지테이블의 주소
바깥 페이지 테이블의 페이지 하나당 하나의 안쪽 페이지 테이블 생성
안쪽 페이지테이블의 크기는 물리적 메모리의 페이지 크기와 똑같음

CPU가 논리적인 주소를 주게 되면 페이지 테이블을 2단계 거쳐서 물리적 테이블 주소를 얻게 된다.
속도를 빠르게 하거나 / 공간을 늘리거나하는 방식 중에 페이지 테이블을 위한 공간을 줄이는 것이 Two-Level Page Table방식

프로그램이 사용하는 실제 주소 메모리는 적은데 page table은 entry를 빼고 갈 수 없기 때문에 일단 빼놓지 않고 페이지 Entry를 생성한다.

outter-page table entry 하나당 inner page table이 하나씩 생성됨

inner page table의 크기는 page의 크기와 똑같다.

1K개의 entry 위치를 구분하기 위해서 p2는 10bit가 되어야 함

2단계 페이지 테이블을 사용하는 이유
이론적으로 시간도 손해이고 공간도 손해이지만 Page Table의 공간을 줄일 수 있기 때문이다. Page Table의 공간을 줄일 수 있는 이유는
사용되지 않는 주소 공간에 대한 outer page table의 entry 값은 NULL (대응하는 inner page table이 없음)
이와 같다. 실제 사용되지 않는 주소 공간이 많은데 outer page table의 entry 값은 실제 사용되지 않는 주소 공간에 대해 NULL 값을 넣는다.

🚧 Multilevel Paging and Performance

• Address space가 더 커지면 다단계 페이지 테이블 필요
• 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요
• TLB를 통해 메모리 접근 시간을 줄일 수 있음
• 4단계 페이지 테이블을 사용할 때

  • 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns

  • TLB hit ratio가 98%인 경우

    effective memory access time
    = 0.98 X 120 + 0.02 X 520
    = 128 nanoseconds

    결과적으로 주소변환을 위해 28ns만 소요

🚧 Inverted Page Table

페이지 테이블은 주소변환을 위한 것인데 페이지 테이블 자체가 메모리 공간을 많이 차지하게 됨. 이런 공간 오버헤드를 해결해 보고자 나온 것

• Page frame 하나 당 page table에 하나의 entry를 둔 것(system-wide)
• 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시(process-id, process의 logical address)
• 단점 : 테이블 전체를 탐색해야 함
• 조치 : associative register 사용(expensive)

page table이 매우 큰 이유?

• 모든 process 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재
• 대응하는 page가 메모리에 있든 아니든 간에 page table에는 entry로 존재

Inverted Page Table Architecture

logical memory 부터 순차적으로 주소 변환이 진행되는 것이 아니라 physical address를 보고 logical address를 변경

🚧 Shared Page

공유할 수 있는 코드는 별도로 올리는 것이 아니라 같은 프레임으로 맵핑을 해서 메모리에 하나만 올림

• 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

  • 각 프로세스들은 독자적으로 메모리에 올림
  • Private data는 logical address space의 아무 곳에 와도 무방

Shared Code

shared code의 2가지 조건
1. 동일한 logical address에 위치해야함
2. read-only 속성을 가져야 함

📌 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 < STLR

• Protection

  • 각 세그먼트 별로 protection bit가 있음
  • Each entry :
    • Valid bit = 0 -> illegal segment
    • Read/Write/Execution 권한 bit

• Sharing

  • shared segment
  • same segment number

  * segment는 의미 단위이기 때문에 공유(sharing)와 보안(protection)에 있어 paging보다 훨씬 효과적임
  

• Allocation

  • first fit / best fit
  • external fragmentation 발생

  * segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들이 발생

🚧 Segmentation Hardware

세그먼트의 길이가 얼마인지 세그먼트 테이블 엔트리 중 리미트 부분에 지니고 있음. 세그먼트 안에서 얼마나 떨어져 있는가(offset, d)를 나타내는 값이 세그먼트 테이블 리미트보다 크다면 적절하지 않은 메모리 참조가 됨

따라서 오프셋 값이 리미트 보다 작은지 합당한 메모리 참조인지 체크를 해봐야함

세그먼트 번호가(s) STLR에서 세그먼트 수와 비교해봐야함 만약에 세그먼트 수가 3개 있는데 세그먼트 번호가 5번을 조회한다면 적절하지 않은 메모리 참조

세그먼트는 의미 단위로 나눈 것
페이지는 동일한 크기단위로 나눈 것

📌 Segmentation with Paging

pure segmentation과의 차이점은?

• segment-table entry가 segment의 base

세그먼트 당 페이지 테이블이 존재한다.
세그먼트의 길이로 페이지 테이블의 엔트리 개수가 결정됨.

메모리 관리 - 물리적 메모리

운영체제의 역할? 주소변환에 있어서 운영체제의 역할은 아직 안나왔다.
다 하드웨어가 주소변환을 함 (MMU 등)

어떤 프로세스가 CPU를 잡고 메모리 접근을 하는 것은 운영체제의 도움을 받지 않음

프로세스가 메모리에 접근할 때 마다 운영체제의 도움을 받아야 한다면 CPU가 프로세스와 OS 왔다갔다 해야함 - 비효율적

따라서 주소변환은 무조건 하드웨어적으로 이루어짐

운영체제가 끼어들 때는 메모리장치가 아닌 I/O 장치에 접근할 때