CH8. Memory Management

유지언·2023년 9월 15일
0

운영체제

목록 보기
8/8

목차 정리

  • Memory Address
    • Logical address
    • Physical address
    • Symbolic address

  • 주소 바인딩
    • Compile time binding
    • Load time binding
    • Execution time binding (=Run time binding)

  • Memory-Management Unit (MMU)

  • Terminalogy
    • Dynamic Loading
    • Overlays
    • Swapping
    • Dynamic Linking (vs. Static Linking)

  • 사용자 프로세스 영역의 할당 방법
    • Contiguous allocation (연속 할당)
      • Fixed partition allocation (고정 분할)
      • Variable partition allocation (가변 분할)
        • Hole
          • Dynamic Storeage-Allocation Problem
          • Compaction
    • Noncontiguous allocation (불연속 할당)
      • Paging
        • Page table and Effective Access Time
        • Two-Level Page Table
        • Multi-level Paging and Performance
        • Memory Protection
        • Inverted Page Table
      • Segmentation
      • Paged Segmentation

Memory Address

Logical addresss (=virtual address)

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

Physical address

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

Symbolic Address

프로그래머가 변수 정의를 통해 특정 메모리를 할당하고 변수를 호출하여 이를 사용하는 것

주소 바인딩 (Address Binding)

주소 바인딩이란 주소를 결정하는 것을 의미한다.

Symbolic Address → Logical address → Physical address 과정에서 Logical address → Physical address 사이에 결정된다.

(1) Compile time binding

  • 물리적 메모리 주소가 컴파일 시 정해진다
  • 시작 위치 변경시 재컴파일
  • logical address가 physical address와 같을 수 밖에 없기 때문에 컴파일러는 절대코드(absolute code)를 생성한다.

(2) Load time binding

  • Loader의 책임 하에 물리적 메모리 주소를 부여한다.
  • 컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우 가능하다.

(3) Execution time binding (=Run time binding)

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

Memory-Management Unit (MMU)

앞서 설명한 주소 바인딩의 방법 중 run time binding의 경우 MMU와 같은 하드웨어적인 지원이 필요하다고 하였다.

MMU란 logical address를 physical address로 매핑해주는 Hardware device이다.

Dynamic relocation 과정을 그림으로 표현하면 아래와 같다.

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

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

운영체제 및 사용자 프로세스 간의 메모리 보호를 위하여 relocation register와 limit register를 사용한다.

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

  • Limit register:
    논리적 주소의 범위

Terminalogy

Dynamic Loading

프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것을 말한다. 이를 통해 memory utilization을 향상시킬 수 있다.

가끔씩 사용되는 코드(ex. 오류처리 루틴)가 많은 경우에 유용하며 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능하다. (OS는 라이브러리를 통해 지원 가능하다)

* Loading: 메모리로 올리는 것

Overlays

메모리에 프로세스의 부분 중 실제 필요한 정보만을 올리는 것을 의미한다.

프로세스의 크기가 메모리보다 클 때 유용하며, 운영체제의 지원 없이 사용자에 의해 구현된다.

작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현하던 것에서 유래하여 Manual Overlay라고도 하며, 프로그래밍이 매우 복잡하다.

📍 [ Dynamic loading vs. Overlays ]

  • 공통점: 프로세스에서 당장 필요한 부분만을 메모리에 올린다.
  • 차이점: Dynamic loading은 라이브러리를 통해 운영체제를 통해 지원하고나 프로그램 자체에서 구현 가능한 반면, Overlays는 운영체제의 지원 없이 프로그래머가 직접 구현해야한다.

Swapping

프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것을 말한다.

프로세스를 통째로 메모리에 올렸다가 디스크에 내렸다가 하는 것이기 때문에 swap time의 대부분은 transfer time(swap되는 양에 비례하는 시간)이다.

  • backing store (=swap area):
    많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간 (ex. 디스크)

Swapping은 Swap in과 Swap out으로 구성된다.

일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스를 선정한다.

  • priority-based CPU scheduling algorithm:
    • priority가 낮은 프로세스를 swapped out 시킨다.
    • priority가 높은 프로세스를 메모리에 올려놓는다.

swapping을 시스템 관점에서 표현하면 아래 그림과 같다.

complie time binding과 load time binding을 사용하는 경우에는 swapping이 발생하더라도 반드시 원래 있던 메모리 위치에 다시 들어가야한다.

즉, 다른 메모리 영역이 비어있더라도 반드시 원래 있었던 자리로 올라가야하기 때문에 swapping의 효과를 온전히 발휘하기 어렵다.

하지만 Execution time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있다.

따라서 swapping이 온전히 제 효과를 발휘하기 위해서는 run time binding이 지원되는 것이 좋다.

Dynamic Linking

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

라이브러리가 실행시 연결(link)되는 구조로, 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾는데 사용되는 stub라는 작은 코드를 둔다.

라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어온다. 때문에 운영체제의 도움이 필요하다.

vs. Static Linking

라이브러리가 프로그램의 실행 파일 코드에 포함되어 있어 실행 파일의 크기가 크고, 동일한 라이브러리를 각각의 프로세스가 메모리에 올리기 때문에 메모리가 낭비된다.

Allocation of Physical Memory

물리적 메모리를 어떻게 관리할 것인가에 대한 부분이다.

메모리는 일반적으로 두 영역으로 나누어 사용한다

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

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

Contiguous allocation (연속 할당)

각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 방식이다.

Fixed partition allocation (고정 분할)

  • 물리적 메모리를 몇 개의 영구적 분할(partition)으로 나누고 분할 당 하나의 프로그램을 적재하는 방식
  • 분할의 크기를 모두 동일하게 하는 방식과 모두 다르게 하는 방식이 존재
  • 동시에 메모리에 load되는 프로그램 수가 고정되어있고, 최대 수행 가능 프로그램 크기가 제한되어 융통성이 없다.
  • Internal, External fragment 발생

Variable partition allocation (가변 분할)

  • 프로그램의 크기를 고려해서 할당하는 방식
  • 분할의 크기, 개수가 동적으로 변한다.
  • 기술적 관리 기법이 필요
  • External fragmentation 발생

가변분할 방식의 경우 프로그램마다 필요한 메모리의 크기가 다르기 때문에 외부 조각이 발생한다.

[ Terminalogy ]

* External fragmentation (외부조각): 
프로그램에 비해 분할된 메모리 크기가 작아 아무 프로그램도 배정되지 못한 공간

* Internal fragmentation (내부조각):
프로그램에 비해 분할된 메모리 크기가 커서 프로그램을 할당하고 남은 공간으로,
특정 프로그램이 배정되었지만 사용되지 않는 공간

Hole

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

hole 중에서 어느 곳에 새로운 프로세스에게 줄 메모리를 할당해야할까?

Dynamic Storeage-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

external fragmentation 문제를 해결하는 한 가지 방법이다.

사용 중인 메모리 영억을 한 군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만든다. 매우 비용이 많이 들기 때문에 최소한의 메모리 이동으로 compaciton할 수 있도록 하려고 하지만 매우 복잡하다.

Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우 (run time binding이 지원되는 경우)에만 수행할 수 있다.

Noncontiguous allocation (불연속 할당)

하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있는 방식이다.

  • Paging
  • Segmentation
  • Paged Segmentation

Paging

Process의 virtual memory를 동일한 사이즈의 page 단위로 나눈다.
Virtual memory의 내용이 page 단위로 noncontiguous하게 저장된다.
일부는 backing storeage에, 일부는 physical memory에 저장된다.

  • Basic Method
    • physical memory를 동일한 크기의 frame으로 나눈다.
    • logical memory를 동일한 크기의 page로 나눈다. (frame과 같은 크기)
    • 모든 가용 frame들을 관리한다.
    • page table을 사용하여 logical address를 physical address로 변환한다.
    • External fragmentation은 발생하지 않지만, Internal fragmentation은 발생할 수 있다.

아래 그림은 paging의 예시이다.

paging의 방법론이 실행되는 과정을 컴퓨터 구조 측면에서 나타내면 아래 그림과 같다.

<추가 설명 필요>

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를 사용한다.

TLB를 사용한 paging은 다음과 같이 진행된다.

TLB에는 자주 사용되는 page number에 대한 page table 데이터가 들어있다.

TLB를 사용하기 전에는 무조건 page table에서 page number에 대응하는 frame number을 찾았는데, TLB가 있을 때는 TLB에서 먼저 탐색한 뒤 없는 경우(TLB miss)에만 page tabe에서 탐색한다.

Effective Access Time

TLB 사용 여부에 따른 access time은 얼마나 차이가 날까?

  • Associative register lookup time = ε\varepsilon
  • memory cycle time = 1
  • Hit ratio = α\alpha (associative register에서 찾아지는 비율)

일 때,

  • hit인 경우 걸리는 시간
    = associative register에서 탐색하는 시간 (ε\varepsilon) + 메모리에 있는 실제 data / instruction 접근 (1)
    = (1 + ε\varepsilon)

  • miss인 경우 걸리는 시간
    = associative register에서 탐색하는 시간 (ε\varepsilon) + memory에서 탐색하는 시간 (1) + 메모리에 있는 실제 data / instruction 접근 (1)
    = (2 + ε\varepsilon)

여기에 각각 hit ratio(α\alpha)와 miss ratio(1 - α\alpha)를 곱해 구한 Effective Access Time (EAT)는

  • EAT = (1 + ε\varepsilon ) α\alpha + (2 + ε\varepsilon )(1- α\alpha)
            = 2 + ε\varepsilon - α\alpha

Two-Level Page Table

현대의 컴퓨터는 address space가 매우 큰 프로그램도 지원한다.

  • 32 bit address 사용시: 2322^{32}B(4GB)의 주소 공간이 필요
    • page size가 4K일 경우, 1M개의 page table entry가 필요
    • 각 page entry가 4B일 경우 프로세스 당 4MB의 page table이 필요
    • 그러나, 대부문의 프로그램은 4GB의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비된다.

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

210=K2^{10}=K
220=M2^{20}=M
230=G2^{30}=G

그냥 page table은 중간에 사용되지 않는 주소 공간이 있어도, 이를 제외하고 page table을 만들 수 없기 때문에 page table 공간이 낭비된다.

two-level page table은 page table 두 개를 거쳐야 주소를 알아낼 수 있기 때문에 시간적 측면에서는 불리하지만, 중간에 사용되지 않는 주소공간에 대해서는 page table을 생성하지 않을 수 있어 page table에 사용되는 메모리 줄일 수 있다는 장점이 있다.

two-level page table의 구조와 과정을 그림으로 표현하면 아래와 같다.

two-level page table를 사용할 경우 p1,p2,dp_1, p_2, d에 메모리를 각각 얼마나 할당해야할지 알아보자.

가장 하단부부터 필요한 만큼의 메모리를 할당하는 방식으로 분배하면 된다.

  • logical address (on 32-bit machine with 4K page size)의 구성
    : page size가 4K ( = 2122^{12})
    → 각 page size를 구분하기 위해서는 12 bit가 필요
    • 20-bit의 page number
    • 12-bit의 page offset
  • page table 자체가 page로 구성되기 때문에 page number는 다음과 같이 나뉜다. (각 page table entry가 4B)
    : 32-bit address 사용시 232=4G2^{32}=4G의 주소 공간이 필요하다. 위에서 page size가 4K라고 하였으니 page table entry 개수는 4G / 4K = 1M ( = 2102^{10}). 2102^{10}개를 서로 구분하기 위해서는 10-bit가 필요하므로
    • 10-bit의 page number
    • 10-bit의 page offset
  • 따라서, logical address는 다음과 같다
    • p1p_1: 10 (outer page table index)
    • p2p_2: 10 (outer page table의 page에서의 변위(displacement)
    • dd: 12

Multi-level Paging and Performance

  • Address space가 더 커지면 다단계 페이지 테이블이 필요하다.
  • 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근이 필요하다.
  • TLB를 통해 메모리 접근 시간을 줄이는 방법을 사용할 수 있다.
  • 예시) 4단계 페이지 테이블을 사용하는 경우
    • 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns
    • TLB hit ratio가 98% 인 경우
    • effective memory access time = (0.98 × 120) + (0.02 × 520) = 128ns
      → 결과적으로 주소 변환에 28ns가 소요

Memory Protection

Page table의 각 entry마다 아래의 bit를 둔다

  • Protection bit
    : page에 대한 접근 권한 (read / write / read-only)
  • Valid-invalid bit
    • "valid"는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 의미한다. (접근 허용)
    • "invalid"는 해당 주소의 frame에 유효한 내용이 없음을 의미한다 (접근 불허)
      • 프로세스가 그 주소 부분을 사용하지 않는 경우
      • 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우

Valid(v)-Invalid(i) Bit를 Page Table에 사용한 예시는 아래 그림을 통해 확인할 수 있다.

Inverted Page Table

page table이 큰 이유는

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

이런 문제를 해결하기 위해서 inverted page table을 사용한다.

Inverted page table은

  • Page frame 하나당 page table에 하나의 entry를 둔 것 (system-wide)
  • 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용을 표시 (process-id, process의 logical address)
  • 단점: 테이블 전체를 탐색해야 해서 시간적으로 overhead가 발생.
  • 조치: associative register 사용하여 병렬적으로 탐색할 수 있도록 해 시간적 overhead를 줄일 수 있도록 한다. (expensive)

Shared Page

  • Shared code
    • Re-entrant code (=Pure code)
    • read-only로 하여 프로세스 간에 하나의 code만 메모리에 올린다.
    • Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 한다.
  • Private code and data
    • 각 프로세스들은 독자적으로 메모리에 code를 올린다.
    • Private data는 logical address space의 아무 곳에 와도 무방하다.

Segmentation

  • 프로그램은 의미 단위인 여러 개의 segment로 구성된다.
    • 작게는 프로그램을 구성하는 함수 하나하나를 segment로 정의한다.
    • 크게는 프로그램 전체를 하나의 segment로 정의 가능하다.
    • 일반적으로는 code, data, stack 부분이 하나씩의 segment로 정
  • Segment는 다음과 같은 logical unit이다.
    • main()
    • function
    • global variables
    • stack
    • symbol table, arrays

  • 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

Segment hardward 그림에는 없지만 원래 s값과 STLR의 값을 비교하여 s값이 STLR보다 작은지 확인해야한다. 크다면 잘못된 참조이므로 trap을 발생시켜 주소변환이 일어나지 않게 해야한다.

paging의 경우 모든 page의 크기가 같지만, segmentation의 경우 의미 단위로 자르기 때문에 크기가 각기 다를 수 있다 (segment마다 limit이 다르다). 때문에 paging의 경우 page의 index와 상관없이 limit이 같았지만 segmentation의 경우 index에 따라 limit이 다르기 때문에 해당하는 limit을 찾아 확인해주어야한다.

  • Protection
    • 각 segment 별로 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의 길이가 동일하지 않으므로 가변 분할 방식에서와 동일한 문제점들이 발생한다.

Segment 방식의 장단점을 정리하면 다음과 같다.

  • 단점: 가변분할방식의 단점처럼 hole이 발생한다 (allocation).
  • 장점: 의미 단위로 하는 업무의 경우에서 공유와 보안 면에서 효율적이다 (protection & sharing).

paging의 page table은 entry 수가 process의 주소공간이 가질 수 있는 최대 개수만큼 만들어진다.
segment table의 entry 개수는 segment의 개수와 같다.
실제로 paging이 segmentation보다 생성되는 entry개수가 훨씬 많기 때무에 paging의 경우 table로 인한 메모리 낭비가 심하다.

Shared Segment

Page Segmentation

  • pure segmentation과의 차이점
    - segment-table entry가 segment의 base address를 가지고 있는 것이 아니라 segment를 구성하는 page table의 base address를 가지고 있다.

profile
유지언
신입 데이터 엔지니어
이전 포스트

CH7. Deadlock

0개의 댓글