Computer Science Basics/운영체제

OS - 6. Main Memory

타자치는 문돌이 2024. 4. 23. 11:57

메모리 기본 상식

Program Execution

프로그램은 하드 디스크에서 메모리에 로드되어야 CPU가 실행할 수 있다.
프로그램은 실행 전에 아래 절차를 거친다.

  1. 메모리에서 명령어 불러오기
  2. 명령어 해석
  3. (Operand 불러오기)
  4. 명령어 실행
  5. (메모리에 실행 결과 저장)

Memory Access Speed

CPU는 메모리와 레지스터만 직접 접근할 수 있다.
레지스터 접근은 1 CPU Clock Cycle 이내에 이루어진다.
메모리 접근은 몇 Cycle이 걸려, Stall을 일으킬 수 있다.
Stall이 일어나면 CPU는 연산할 데이터가 없기 때문에 기다릴 수 밖에 없다.

Stall을 줄이기 위해 CPU와 레지스터 사이에 Cache를 둔다.

Memory Protection Hardware

프로세스는 메모리의 특정 범위를 할당받는다.
프로세스가 다른 프로세스의 메모리 범위를 접근하는 일을 막기 위해 Base Register와 Limit Register에 프로세스의 시작 주소와 끝 주소를 저장해둬 범위를 넘어가는 접근을 막는다.

Address Binding

프로그램이 실행되려면 메모리의 어느 위치에 로드되어야 한다. 프로그램이 로드될 위치를 결정하는 것을 Address Binding이라고 한다.
Address Binding은 세 시점 중 하나에서 일어난다.

  • Compile Time : Absolute Code를 로드할 수 있다. 메모리 위치가 변경된다면 다시 컴파일 해야 한다.
  • Load Time : Compile Time에 코드가 로드되지 않았다면 Relocatable Code를 Load Time(프로그램이 시작될 때)에 로드해야 한다.
  • Execution Time : 메모리 주소가 프로그램 실행 이후에도 변경된다면, Execution Time에 메모리 주소가 결정된다.

Logical & Physical Address Space

메모리 관리를 효율적으로 하기 위해 CPU는 Logical Memory Address라는 가상의 메모리 주소를 사용하고, 이 주소를 실제 RAM의 주소인 Physical Memory에 매핑시켜 사용한다.
이 매핑은 Memory Management Unit (MMU)라는 하드웨어가 처리한다.

Static vs Dynamic Link Library

프로그램이 불러오는 Library는 Static 하거나 Dynamic Link일 수 있다.

  • Static Library : Compile Time에 불러와져 Linker에 의해 Target Application에 복사된다. (.lib, .a)
    • 프로그램의 크기가 커질 수 있다.
  • Dynamic Link Library (Shared Library) : Runtime에 불러와지는 Library로 하나의 복사본만 로드되고 여러 프로그램이 공유해서 사용한다. (.dll, .so)
    • 메모리가 절약된다.
    • Dynamic Link Library도 두 종류로 나뉜다.
    • Dynamic Loading : Load와 Link가 Runtime까지 미뤄지고 함수가 실행될 때 로드된다.
    • Dynamic Linking : Load와 Link가 프로그램이 시작될 때 이뤄진다. Library의 호출 부분에 Stub이라는 코드 조각을 넣어두고 Stub을 통해 함수를 호출하면 함수의 실제 주소를 찾는다.Swapping프로세스는 Swap 되어 메모리에서 디스크로 일시적으로 빠질 수 있다.
      메모리가 꽉 찬 상태에서 프로세스를 실행해야 할 경우 어느 프로세스는 메모리에서 빠져야 한다. 이런 경우 프로세스의 정보를 디스크에 임시로 저장해 둔 뒤(Swap out), 다시 해당 프로세스가 필요할 때 로드한다. (Swap in)
      Swapping 대부분의 시간은 Transfer Time으로 Swap 되는 프로세스 메모리의 크기에 비례한다.

Memory Allocation

프로세스에 메모리를 어떻게 할당해야 할까?

Contiguous Allocation

먼저 메모리를 적당한 크기로 잘라 사용하는 Contiguous Allocation을 살펴보자.

단순한 방법으로는

  • Two-Partition Allocation : 단순하게 맨 아래에 OS를 로드하고, 위에서부터 프로세스를 하나씩 쌓아간다.

가 있을 것이다. 이 방법은 Multiprogramming을 지원하기 위해

  • Multiple-Partition Allocation : 메모리를 고정된 크기로 자르고, 한 조각에 한 프로세스를 할당한다.
    로 진화하였다.

Variable Partition Allocation

프로세스에 남은 공간에서 적당한 크기를 잘라서 할당한다.

프로세스의 실행과 종료가 계속되면 중간에 비어있는 공간이 생기게 되는데, 이 공간을 Hole이라고 한다.
Variable Partition Allocation에서는 이 Hole에서 적당한 부분을 잘라 나눠준다.

Dynamic Storage Allocation Problem

비어 있는 Hole 중에서 어느 부분을 할당해 줘야 할까?

  • First-Fit : 알맞은 크기의 Hole 중에서 첫 번째 Hole을 할당한다.
  • Best-Fit : 알맞은 크기의 Hole 중에서 가장 작은 Hole을 할당한다.
    • 가장 작은 Hole을 남긴다.
    • 전체 메모리를 탐색할 시간이 필요하다.
  • Worst-Fit : 가장 큰 Hole을 할당한다.
    • 가장 큰 Hole을 남긴다.
    • 전체 메모리를 탐색할 시간이 필요하다.

 

 

Fragmentation

메모리의 할당은 낭비를 피할 수 없다.

  • External Fragment : 메모리에 여러 프로세스를 할당하면 Hole이 생기고, 이 부분은 낭비된다.
  • Internal Fragment : 프로세스에 메모리를 할당할 때도 실제로 필요한 메모리보다 살짝 크게 할당한다. 이 부분도 사용되지 않는 부분이다.


External Fragment를 줄이기 위해 Compaction 작업을 수행하기도 한다.
Compaction은 빈 공간을 조각 모음 하기 위해 메모리를 다시 정렬하는 과정이다. Relocation이 Execution에 가능한 경우만 가능하다.

Paging

Paging과 Segmentation은 연속된 메모리 공간을 할당하지 않는 방식이다.

Logical Memory를 고정된 크기(주로 2의 n 제곱)의 Page로 나눈다. 이 크기는 하드웨어가 결정한다.
Physical Memory도 같은 크기의 Frame으로 나누고 두 메모리를 매핑시킨다.

Paging은 External Fragment는 존재하지 않지만, 여전히 Internal Fragment는 존재한다.

프로세스가 실행되려 하면,

  1. 몇 개의 Page가 필요한지 검토한다.
  2. n개의 Page가 필요한 프로그램이면, n개의 Frame을 찾아서 로드한다.
  3. 각 Page가 빈 Frame에 로드되면 Page Table에 Frame 번호를 기록한다.

다음 단원에서 다룰 Virtual Memory 개념을 사용하면 Page의 개수가 Frame의 개수보다 많을 수도 있다.

Address Translation Scheme

Paging에서 Logical Address로 Physical Address를 찾는 속도를 단축시키기 위해 Address Translation Scheme을 사용해 주소를 결정한다.

Logical Address는

  • Page Number : Page Table의 Index로 사용된다. Index를 통해 Physical Address의 Base Address를 찾을 수 있다.
  • Page Offset : Base Address에서의 Offset으로 Page Number로 찾은 주소 + Offset이 Physical Address이다.

전체 주소가 m 자리이고, Page Offset이 n 자리일 때, Page의 크기는 $2^n$  이고, Page Table은 $2^{m-n}$개의 행을 가진다.

Page Table

한 프로세스는 하나의 Page Table을 메인 메모리에 저장하고 있다.
Page Table의 시작 주소는 Page-Table Base Register에, 크기는 Page-Table Length Register에 저장하고, 레지스터의 정보는 프로세스의 PCB에 저장된다.

TLB

메모리에 접근할 때는

  1. Page Table에서 주솟값을 찾고
  2. 메모리에 접근하는
    두 번의 Memory Access가 필요하다. 이때 시간을 단축하기 위해 Associative Memory와 Translation Look-Aside Buffers(TLBs)라는 하드웨어 캐시를 사용한다.

TLB는 Page Number와 Frame Number의 쌍을 저장해둔다. TLB는 Associative Memory를 사용한 병렬 탐색으로 Page Table보다 더 빠르게 접근할 수 있다.
TLB에서 필요한 값을 찾으면 찾은 주솟값으로 메모리에 접근한다.
찾지 못했다면 Page Table에서 필요한 주소를 찾는다.

TLB에서 필요한 주소를 찾으면 TLB 검색 시간 + 메모리 접근 시간만 소요된다.
찾지 못하면 TLB 검색 시간 + Page Table에서 주소를 찾는 시간 + 메모리에 접근하는 시간이 소요된다.
따라서 TLB의 적중률에 따라 성능이 달라진다.

$$
TLB의\,적정률이\,\alpha,\,
메모리\,사이클이 \, \beta,\,
TLB\,검색\,시간이\,\epsilon일\,때, \\
Effective\,Access\,Time \\
EAT\,=\,(\beta\,+\,\epsilon)\,\alpha\,+\,(2\beta\,+\,\epsilon)(1\,-\,\alpha) \\
$$

Memory Protection

Paging에서 다른 프로세스가 메모리에 접근하는 것을 막기 위해 Valid-Invalid Bit 정보를 Page Table에 저장하기도 한다.

  • Valid면 Page가 사용 중인 Logical Address이고, 유효한 Page임을 암시한다.
  • Invalid면 Page를 사용하는 프로세스가 없다는 뜻이다.

또는 위에서 언급한 Page Table Length Register를 사용해 유효한 범위인지 계산하기도 한다.

Page Table Structure

Page Table의 구성 방식도 다양하다.
이건 몇 가지 예시들이다.

  • Hierarchical Paging : Logical Address가 다중 Page Table Number와 Offset을 담게 한다.
    • 64비트 이상 주소는 2-Level로 감당하기 힘들다. (3-Level 이상 필요)

  • Hashed Page Table : Hash Table을 사용해 Page Table을 구성한다.
    • 주소가 32비트 이상인 경우 자주 사용한다.

  • Inverted Page Table : 메모리 Frame마다 하나의 Page를 저장한다.
    • Frame 기준 Page Table이므로 모든 프로세스가 하나의 Page Table을 사용한다.
    • 탐색 속도는 늘어나지만, 프로세스가 증가해도 Page Table을 위한 메모리가 증가하지는 않는다.

Segmentation

Paging은 프로세스를 내용에 상관없이 일정한 크기로 잘라 메모리에 로드했다. Segmentation은 사용자 관점으로 프로세스를 나눈다.
프로그램은 Main Program, Procedure, 전역 변수, 지역 변수, Stack, Array 등의 Segment의 집합이다. Segmentation은 Segment를 기준으로 Logical Address Space를 자른다.

Segmentation도 Paging과 마찬가지로 Segmentation Table을 사용해 Physical Address를 찾는다.
Logical Address는 Segment Number와 Offset으로 이뤄진다. 단, Segment의 크기가 일정하지 않기 때문에 Table은 Limit과 Base 정보를 저장한다. CPU에서 Segment의 크기를 넘어서는 주소가 들어오면 Trap을 발동시켜 막는다.

 

 

OS - 0. Index

저작자표시 비영리 변경금지