[운영체제] 7장: Memory Management

Real memory: 메인 메모리에 프로그램 전체가 포함된다.

Memory Management

• 메인 메모리에 여러 프로세스들을 적재시키기 위해 메모리를 여러 개로 나누는 것
• 메인 메모리 안에 가능한 많은 프로세스를 올리기 위해 메모리가 효율적으로 할당되어야 한다.

Memory Management Requirements

• Relocation: 프로그램 상 데이터들의 메모리 주소를 실제 메모리 주소로 변환하는 것
  • 0번지 기준으로 프로그램을 컴파일 하므로, 컴파일할 때 실제 메모리 주소를 모른다.
  • 프로그램을 실행하면서 relocation을 수행한다.
  • 프로세스가 메인 메모리와 하드디스크의 Swapping area를 오가면서, 메모리에 적재될 때 항상 같은 공간에 적재되지 않기에 필요하다.
• Protection: 자신에게 할당된 메모리 영역에만 액세스 하는 것
• Sharing: 여러 프로세스가 메모리를 공유하는 것

  프로세스의 메모리 관리 정보는 PCB의 Process control information에 저장된다.

Partitioning

• Fixed Partitioning: 처음부터 메모리를 여러 영역으로 분할해 놓고 프로세스를 할당한다.
  • 장점: 메모리에 들어갈 주소를 미리 정해 놓고 컴파일하는 것이 가능하다.
  • 단점: 다른 곳에 할당이 불가능하다.
  • 나눠진 영역보다 프로그램 크기가 작으면 메모리가 낭비되고(Internal fragmentation), 크면 할당이 불가능하다.
  • Equal-size partitions와 Unequal-size partitions 중 둘 중 무엇이 더 낫다고 단언할 수 없다.
• Dynamic Partitioning: 프로세스 크기만큼만 할당한다.
  • 여러 프로세스들이 메모리를 오가면서 External fragmentation이 발생한다.
  • Compaction: 프로세스를 메모리에 빈 공간이 없게 재배치하는 것으로 상당한 시간이 걸린다.
    • Compaction을 해도 external fragmentation 문제가 해결되는 것은 아니다.

Dynamic Partitioning Placement Algorithm

External fragmentation 최소화, Compaction 줄이기

• Best-fit: 프로세스 크기와 가장 유사한 공간에 배치하는 방법
  • 모든 free block의 크기를 확인하는 과정이 필요하므로 시간이 오래 걸린다.
• First-fit: 앞에서부터 free block을 탐색하면서 들어갈 수 있는 첫 번째 공간에 배치하는 방법
  • fragmentation이 클 수 있다.
• Next-fit: 프로세스가 마지막으로 할당된 위치부터 free block을 탐색하면서 들어갈 수 있는 첫 번째 공간에 배치하는 방법
  • 확률적으로 First-fit 보다 더 빠르게 적합한 공간을 찾을 수 있다.
• Worst-fit: 프로세스 크기와 가장 차이가 큰 공간에 배치하는 방법
  • External fragmentation의 크기가 커서 다른 프로세스가 배치될 수 있음을 고려한 것이다.
  • Best-fit과 유사하게 모든 free block의 크기를 확인하는 과정이 필요하므로 시간이 오래 걸린다.

Buddy System

• 2^(n-1) < 프로세스 크기 <= 2^n -> 2^n 크기의 공간을 할당해준다.
• 해당 공간을 할당해줄 수 있을 때까지 공간을 반으로 나눈다.
• buddy: 반으로 나눴을 때 생성되는 두 공간으로 서로 크기가 같다.
• 프로세스를 할당할 적합한 공간이 이미 존재한다면 메모리 분할 작업 없이 바로 할당한다.
• buddy 관계인 두 공간이 비어 있으면 하나로 합친다.
• Fixed Partitioning에서 partition보다 크기가 큰 프로세스를 실행할 수 없는 문제를 해결할 수 있다.
• Dynamic Partitioning에서의 External fragmentation, Compaction 문제를 해결할 수 있다.
• Internal fragmentation 발생 가능성은 여전히 있다.
  • 프로세스에게 할당되었으나 실질적으로 프로세스가 사용하지 않는 공간이다.
  • 그 크기는 할당된 공간 크기의 반보다 작다. 프로세스 크기가 할당된 공간의 반보다 작았으면 더 작은 공간을 할당했을 것이다.

Addresses

• Logical: 서로 다른 정보를 엮어서 하나의 주소로 간주한다.
• Relative: 프로그램이 0번지 기준으로 컴파일 되었을 때의 데이터 및 코드의 주소이다.
  • 시작 주소가 반드시 0번지인 것은 아니다.
• Physical: 메인 메모리 상에서의 실제 주소

- Base Register: 프로세스의 프로그램 코드 시작 주소로 PCB의 시작 주소가 아니다.
- Relocation: Base Register + Relative address -> Physical address
- Bounds Register: 프로그램 코드 및 데이터의 마지막 주소
-> Protection에 사용된다.
-> Relocation으로 얻은 Physical address가 Bounds Register 값보다 작거나 같으면 액세스가 가능하고, 크다면 Program interrupt가 발생한다.
- Fixed Partitioning, Dynamic Partitioning, Buddy System에 대해서 Relocation, Protection 문제의 해결이 가능하다.
- 프로세스를 실행하면서 한 명령씩 주소를 변환하는 방법이다.
-> 프로세스가 메인 메모리에 적재되는 시점에 모든 Relative address가 Physical address로 변환되어야 하는 것이 아니다.
- 메인 메모리에 여러 프로세스가 존재하더라도 한 번에 하나씩만 실행하기 때문에 Base Register와 Bounds Register는 하나씩만 필요하다. (Multiprogramming system)
-> 각 레지스터 값은 실행하는 프로세스가 교체될 때 바뀌는 것으로 메인 메모리에 적재될 때 바뀌는 것이 아니다.

Paging

• Page frame: 메인 메모리를 page 단위로 나눈 것
• Page: 프로세스를 page frame 크기로 나눈 것
• 프로세스를 연속된 공간에 할당할 필요가 없으므로 Base Register, Bounds Register와 Compaction이 필요 없다.
• External fragmentation X & Internal fragmentation O
  • 프로세스의 크기가 페이지 크기로 나누어 떨어지지 않으면 마지막 페이지에서 internal fragmentation이 발생한다.
• 각 프로세스마다 고유의 page table이 존재한다. (1차원 배열)
  • Relocation, Protection 해결 방법
  • 프로세스의 각 페이지가 메인 메모리의 몇 번 프레임에 들어가는 지를 저장한다.
  • 인덱스: 프로세스의 페이지 번호
    
• 메모리 주소는 페이지 번호와 페이지 내의 오프셋으로 구성되는데, 페이지 번호를 확인하여 Protection 문제를 해결한다.

• Logical address = Relative address
• Physical address = 페이지 테이블의 entry 값과 logical address의 오프셋을 연결한다.
• 6-bit page #: 각 프로세스는 최대 2^6개의 페이지를 가질 수 있다. (0 ~ (2^6)-1)
  • 프로세스의 페이지 테이블 최대 크기: 2^6 * 6 bits
• 10-bit offset: page 크기는 2^10 bytes
• 16-bit 주소 체계
  • 프로그램 최대 크기 2^16 bytes
  • 레지스터의 비트 수 16 bits
  • 메인 메모리 크기 2^16 bytes
• PCB와 프로그램 코드가 같은 페이지 안에 들어가는 경우가 발생할 수 있다.
  • PCB는 OS만 접근 가능하고 사용자는 접근 불가능하다.
• 프로그램 코드와 데이터가 같은 페이지 안에 들어가는 경우가 발생할 수 있다.
  • Segmentation으로 해결 가능하다.

Segmentation

• 프로세스를 세그먼트 단위로 나누어서 관리한다.
  • PCB, 코드, 데이터 ~
  • protection이 용이하다.
• 각 세그먼트의 길이는 다를 수 있다.
• 세그먼트가 가질 수 있는 최대 길이가 존재한다.
• 세그먼트 번호와 오프셋으로 구성된 Logical address를 사용한다.

- Relative address != Logical address

• 세그먼트 길이가 서로 다르기 때문에 Dynamic partitioning이 필요하다.
  • External fragmentation이 발생한다.
  • 프로세스 전체를 Dynamic partitioning 할 때보다 훨씬 문제가 적다.
  • Compaction이 필요하다.
• 레지스터로 Relocation과 Protection을 구현하려면 세그먼트 개수만큼 Base register, Bounds register가 필요하다.
  • 세그먼트 테이블 사용
  • 4-bit segment #: 세그먼트 최대 개수 2^4 개
  • 12-bit offset: 세그먼트 최대 크기 2^12 bytes
  • 4-bit segment # & 12-bit offset -> 세그먼트 테이블의 한 entry 길이 28 bits
  • 12-bit Length: 세그먼트가 가질 수 있는 마지막 오프셋
    • Bounds Register 역할
    • 오프셋과 비교하여 Protection을 구현한다.
  • 16-bit Base: 메인 메모리에서의 세그먼트 시작 주소
    • Base Register 역할
    • Physical address = Base + offset
  • 16-bit 주소 체계: 프로그램 최대 크기 2^16 bytes