Chap 7. Memory Management

메모리안에는 여러개의 프로그램이 동시에 들어가서 실행한다.

메모리를 나눠서 여러 프로세스가 동시에 들어갈 수 있게 해야한다.

메모리는 크기가 한정적이고 실행을 동시에 하고싶어하는 프로세스의 개수는 많기 때문에 가급적이면 많은 프로세스들이 동시에 메모리에 들어갈 수 있도록 자른다.

어떻게 메모리를 효율적으로 할당하는지가 중요한 문제다.

Memory Management Requirements

메모리 관리에 있어서 3가지가 있다.

• Relocation
• Protection
• Sharing

위 이미지는 프로세스 이미지이다.

• PCB
• 프로그램 영역
  • Program Code
  • Data
• stack

Relocation

위 모양 그대로 프로세스가 메모리 안으로 들어가야 한다. 그런데 명령이나 데이터의 주소를 알 수 없다. 메모리를 4개로 잘라서 프로그램을 집어넣고 실행한다. 그런데 프로그램은 1, 2, 3, 4 중 어디에 들어갈지 알 수 없다. 컴파일해서 기계어로 바꾸는 단계에서는 메모리의 몇 번지로 가는지 알 수 없기 때문에 다음 명령이 몇번지인지 알 수 있는 방법이 없다. 그래서 항상 컴파일할 때는 0번지 기준으로 컴파일한다.

그래서 시작주소가 1000번지라면 350번지라고 생각한 지점은 1350번지가 된다. 모든 주소에다가 1000씩 더해야 실제 주소가 나오게 된다.

위 과정을 Relocation이라 한다.

즉, 우리의 프로그램이 메모리 상에 어떤 위치에 들어가느냐에 따라서 모든 프로그램 안에 있는 데이터와 명령어들의 주소가 바뀌어야 하는데, 주소를 바꿔주는 작업을 Relocation이라 한다.

실제 메모리 상황에 맞게 주소 변경을 해줘야 한다.

Protection

우리의 프로그램이 실행될 때 1000~2000번지에 있을 때, 데이터 저장을 2500번지에 저장하면 안된다. 프로그램은 자신한테 할당된 이외의 영역에 접근해서는 안된다.

이를 Protection이라 부른다.

Sharing

하지만 가끔은 Sharing을 한다. OS가 공유할 수 있게 허용한 공간이 존재한다.

Partitioning

• Fixed Partitioning
  • 처음부터 메모리 공간이 나뉘어져 있다.
  • 장점 : 각 파티션의 시작점이 정해져 있음 ⇒ Relocation 작업이 간단하다.
  • 단점 : 실제 프로그램의 크기가 만들어놓은 메모리 공간의 크기보다 작아서 발생하는 공간의 낭비 = Internal Fragmentation
  • equal-size partition
    • 동일한 사이즈로 자른다.
    • 시작번지가 정해져 있다.
    • 시작번지에 맞춰서 컴파일하면 되기 때문에 relocation 문제 걱정할 필요가 없다.
    • 프로그램 크기가 공간 크기랑 같을 수는 없다. 실제로 프로그램이 굉장히 작다면 나머지 공간은 낭비가 된다.
  • unequal-size partition
    • 크기를 다양하게 나눈다.
    • equal-size partition보다 꼭 효과적인 것은 아니다.
      • 왜? 2메가, 4메가, 6메가 짜리 프로그램은 아예 들어오지도 않고 8메가 짜리 프로그램만 실행된다면, 2, 4, 6은 사용할 수 없는 장소가 된다. 12, 16메가는 결국 남는 공간이 생기게 된다.
        

• Dynamic Partitioning
  • 필요한 만큼의 공간만 제공
  • 프로세스를 하드디스크로 옮기는 과정에서 프로세스와 프로세스 사이 공간 발생 ⇒ External fragmentation
  • Fixed Partitioning보다 더 심하게 공간 낭비가 발생할 수 있음
  • 위 문제를 해결하기위해 Compaction 주기적으로 실행
    • 프로그램들을 다 위로 밀어붙인다. 최악의 경우 메모리 전체를 한 번 읽기/쓰기 해야할 수 있다.

Dynamic Partitioning Placement Algorithm

EX) 16M 프로그램

• best-fit
  • 남는 공간이 제일 작은 곳
  • 공간의 낭비가 적어짐
  • 남아있는 공간만큼 확인 ⇒ 공간만큼 시간 소요
• first-fit
  • 앞에서부터 들어갈 수 있는 첫 번째 공간
  • best-fit에 비해 적은 시간 소요
  • external fragment 크기가 커질 수 있음
  • 앞에서부터 찾기 때문에 앞쪽에 있는 공간들만 자주 사용, 뒤쪽 공간은 잘 사용 X
• next-fit
  • 마지막으로 할당된 공간의 다음 공간 탐색
  • first-fit과 유사하게 해당하는 프로그램이 들어갈 수 있는 공간 탐색
    • first-fit은 처음부터, next-fit은 마지막으로 할당한 공간 다음부터 탐색
  • first-fit보다 좋은 점은 공간활용을 전체적으로 할 수 있고, 공간을 찾는데 시간 적게 소요
    • first-fit에서 앞쪽의 공간은 대부분 사용되거나 작은 공간일 확률이 높아서 앞에서 오래 찾아야 하기 때문
• worst-fit
  • 공간이 가장 큰 곳
  • worst-fit을 사용하는 경우, 프로그램을 집어넣어도 공간이 많이 남는다.
    • external fragment라고 부를 수 없을 정도로 큰 공간이 남아서 다른 프로그램을 넣는다.

Buddy System

Fixed Partitioning에서 파티션안에 프로그램이 들어가는데, 프로그램의 크기가 파티션보다 작으면 공간이 남는다. 이러한 공간을 Internal Fragmentation 이라 부른다.

Dynamic Partitioning에서는 프로그램과 프로그램 사이에 External Fragmentation 이 존재한다.

Internal Fragmentation 은 파티션 개수로 정해져 있다.

Buddy System은 Fixed + Dynamic Partitioning 이라고 볼 수 있다.

dynamic 처럼 공간인 필요할 때마다 할당해서 공간을 나눠준다. 그런데 적당한 크기의 공간은 프로세스가 요청한 크기가 아니라, 어떠한 규칙을 가지고 크기를 정한다.

• 메모리 전체 공간이 $2^U$ 이다.
• $2^{U-1}$ < S ≤ $2^U$인 S 공간을 요청하면, $2^U$만큼 나눠준다.
  • 원하는 공간이 나올 때까지 전체 공간을 반으로 나눈다.

• 공간을 합칠 때는 Buddy 끼리만 합친다.
• External Fragmentation X
• Buddy 끼리 합치기 때문에 Compaction 수행 X
• Internal Fragmentation 존재.

각 방법(Fixed, Dynamic, Buddy)의 장단점을 잘 알고있어야 한다.

---

메모리 매니지먼트에서 중요한 것

• 가급적 많은 프로세스를 메모리에 집어넣는다.
• relocation과 protection을 할 수 있어야 한다.

---

Address

• Logical
  • 특정한 목적으로 프로그램에 특정한 주소 부여
  • x번 페이지 안에서 offset y 처럼 있기 때문에 연속된 주소 X
• Relative
  • 어떠한 기준점을 기준으로 해서 주소를 붙인 것
  • 프로그램을 컴파일할 때 메모리 0번지에 들어간다고 생각하고 컴파일
  • relative 주소는 physical address로 고쳐야 relocation이 된다.
  • 특정 기준점을 가지고 주소가 연속된다.
• Physical
  • absolute address 라고도 한다.
  • 실제 메모리의 주소

Relocation + Protection

아래의 Relocation, Protection 방식은 Fixed/Dynamic Partitioning, Buddy System에서 사용한다.

Relocation

모든 번지에 1000씩을 더하는 방법은 컴파일을 다시하는 것이다. 이 것은 시간이 굉장히 많이 걸린다. 이 방법보다는 Base Register 를 사용한다. 프로그램의 시작 번지가 3000이면, Base Register에 3000을 집어넣는다.

JMP 300 ⇒ 300 주소에다가 Base Register값을 더한다 ⇒ JMP 3300

Relocation : Relative Address + Base Register ⇒ Physical Address

Base Register는 프로그램 영역의 시작점이다. 프로세스의 시작점인 PCB가 있는 영역이 아니라 프로그램 코드의 시작점이 들어있어야 한다.

Relocation 하는 부분은 Relative Address랑 Base Register값을 더해서 Physical Address가 되는 부분까지이다.

Protection

Protection을 하기 위해서 Bounds Register를 사용한다.

Bounds Register 에 프로그램 영역(프로그램 코드와 데이터)의 마지막 주소값을 넣는다. 스택 영역은 프로세스가 관리하는 영역이다.

0번지 기준으로 컴파일 했을 때 프로그램의 마지막 주소가 1000번지이고 프로그램을 3000번지에 집어넣는다면, 마지막 주소값은 4000번지가 된다.

Base Register에는 3000을 넣어두고 Bounds Register에는 4000을 넣는다.

Base Register + Relative Address > Bounds Register ⇒ 인터럽트 발생

💡시스템안에 Base Register와 Bounds Register는 몇 쌍이 있어야 할까?

만약 시스템이 메모리안에 동시에 최대 10개의 프로그램이 들어갈 수 있다면, Base Register와 Bounds Register는 몇 개가 필요할까?

1개, 한 번에 한 프로그램만 실행되므로

Paging

메모리를 동일한 크기의 조각으로 전부 자른다. 이런 한 조각을 page frame 이라고 부른다.

그 다음 프로그램을 이 조각에 맞춰서 자른다. 이 조각을 page 라고 부른다. 마지막 페이지는 실제 프레임보다 작기 때문에 마지막 페이지에 한해서는 Internal Fragmentation 이 발생한다. 하지만 External Fragmentation 은 발생하지 않는다.

Dynamic Partitioning이었다면 D를 실행시킬 수 없다. 하지만 paging 시스템이기 때문에 연속되지 않은 5개의 프레임을 할당해서 프로그램을 실행할 수 있다.

• Dynamic Partitioning에 존재하는 External Fragmentation X
  • Compaction X
• Real Memory 시스템에서는 전체 프로세스의 모든 페이지가 다 메모리 안으로 들어와야 실행
• 기존 방법의 relocation, protection 사용 X
  • 기존 방법의 Relocation, Protection은 연속된 공간에 있다고 가정
• Page Table 이용
• OS가 각각의 프로세스마다 페이지 테이블 생성하여 관리

페이지 테이블에는 각 프로세스의 각 페이지가 몇 번 프레임에 들어있는지를 나타낸다. 그리고 relocation하기 위해서 프로그램에서 사용하는 주소도 컴파일할 때 x번 페이지의 오프셋 y 형식으로 주소를 만들어서 컴파일한다.

Page Tables

• 페이지 번호 = 인덱스 번호
• 안에 들어있는 원소 값 = 프레임 번호

Logical Addresses

Paging

page size = 1K = $2^{10}$= 1024

• 페이지의 크기 = $2^{10}$
• 페이지의 개수 = $2^{10}$
• 전체 주소가 16비트 ⇒ 프로그램 자체가 $2^{16}$ 보다 더 커질 수 없다.
  • 프로그램에 붙일 수 있는 페이지 하나 = $2^{10}$
  • 프로그램 최대 크기 = $2^{10} * 2^6$

Relocation

1502 ⇒ 1502/1024 번째 페이지, 1502 % 1024 offset ⇒ 2번째 페이지 478번지 offset

• relative address = logical address
• relative address ⇒ logical address : 페이지 크기로 나눔
  • 몫 : 앞부분 6비트
  • 나머지 : 뒷부분 10비트

그래서 paging 시스템의 장점은 우리가 컴파일하는 방식을 바꾸지 않아도 된다.

Protection

오프셋은 10비트로 표현된다. 따라서 오프셋은 10비트보다 더 큰 수일 수 없다. 결국 오프셋은 페이지 안에 있는 어떤 주소를 나타낸다.

하지만 다른 사람의 페이지 프레임 번호에 접근하게 되면 문제가 된다. 이 부분은 페이지 테이블을 찾을 때 페이지 번호를 확인해서 해결한다. 자신에게 할당된 페이지 프레임에 접근해야 한다.

이렇게 paging 시스템을 사용하면 relocation과 protection을 동시에 할 수 있다.

Segmentation

real memory 시스템에서는 Segmentation 기법을 사용할 필요가 없다. 그러나 Virtual Memory 시스템이 되면 Segmentation 기법이 일부 도입되어야 한다. 왜냐하면 Virtual Memory 시스템에서는 전체 프로그램이 다 메모리에 들어가는 것이 아니라 일부만 메모리에 들어온다.

• 의미있는 단위로 프로그램을 자른다.
  • EX) PCB 영역, 프로그램 코드 영역, 데이터 영역, 스택 영역을 서로 다른 4개의 Segment로 나눈다. 프로그램이나 데이터 영역의 경우 더 자를 수 있다.
• segment 길이는 다 다르지만, 최대 길이는 고정

Dynamic Partitioning은 프로그램 전체가 들어갔다 나갔다해서 공백에 전체 프로그램이 들어가기엔 공백이 너무 작다. 하지만 Segmentation 기법에서는 Segment 하나가 들어왔다 나갔다 하기 때문에 공백이 작아도 Segment를 집어넣을 수 있다.

따라서 External Fragmentation 이 발생하기는 하지만, 생각처럼 자주 Compaction을 할 필요는 없다.

주소는 paging과 마찬가지로 세그먼트 번호와 offset으로 나뉜다.

Relative Address = 1502 ⇒ Logical Address

첫 번째 Segment는 750 bytes이다. 따라서 1502번지는 1번 Segment의 752 offset에 위치한다.

Segmentation 기법에서 Relative Address를 주고 Segmentation 시스템에서 사용하는 주소로 바꾸라고 한다면 Segment 크기를 확인해야 한다.

Segmentation 기법에서 Logical Address는 주소가 달라진다. 왜냐하면 나누는 것이 아니라 Segment 크기를 빼기 때문이다.

• Segment → 4 bit 사용
  • 한 프로그램 당 최대 $2^4$개의 Segment 사용 가능
• Offset → 12 bit 사용
  • Segement의 최대 크기 : $2^{12}$
• 전체 Logical Address → 16 bit 사용
  • 프로그램의 최대 크기 : $2^{16}$
• Physical Address → 16 bit 사용
  • 메모리 크기 : $2^{16}$

Segment Table

• Base ⇒ Relocation
  • Base : 각 Segment의 시작 위치
  • Base + Offset = Physical Address
• Length ⇒ Protection
  • Length : 해당 Segment의 마지막 Offset
  • Offset ≤ Length

💡Segment Table의 한 Entry 길이?

한 Entry 에는 Length와 Base를 가지고 있다.

• Base = Segment가 Physical Address 몇 번지에서 시작하는지 나타냄
  • Physical Address = 16 bit ⇒ Base = 16 bit
• Length = 한 Segment의 최대 길이
  • Segment의 최대 길이 = 12 bit ⇒ Length = 12 bit

따라서, Segment Table 한 Entry의 길이 = Base + Length = Physical Address의 길이 + Segment의 길이 = 16 bit + 12 bit = 28 bits