Memory Management

Disk에 있는 프로그램을 main memory에 올리기 위해 

1. 언제 올릴건지

2. 어디에 올릴건지

3. 어떤 프로세스를 올릴건지 

를 결정해야한다.

 

주 요구사항은

Allocation, Relocation, Protection, Sharing

 

이러한 내용들이 효율적이고 transparent하게 관리되어야 한다.

 

먼저 address에 대해 살펴보자

 

Address Types

• Symbolic address
  - 변수 이름같은 상징적인 주소를 의미한다.
  - 소스코드에 사용된다.
• Logical or relative address (or virtual address)
  - 프로세스의 위치를 상대적으로 나타내는 주소이다.
  - 시작위치로부터 떨어진 거리를 의미한다.
• Physical or absolute address
  - main memory에 있는 실제 위치로 나타낸다.
  - logical address형태로 컴파일을 하여 run time에 실제 물리적 주소로 들어가게 된다.

 

 

Address binding

symbolic address를 physical address로 mapping하는 것을 말한다.

address binding은 아래의 시간에 이루어진다.

Compile time : 어셈블리어같은 경우는 compile되면 logical/physical address 모두에 binding이 된다.

Load time : load time엔 프로세스(프로그램)가 메모리에 올라간다.

Execution time : 대부분의 프로세스는 execution time에 binding된다. 

나중에 더 추가하기...

 

Memory allocation

연속할당방식

• 고정분할 : 메모리가 미리 partition되어있음
  - 균등고정
  - 비균등고정
• 동적분할 : load time에 partitioning함
• 버디시스템 : 두가지의 hybrid방식

불연속할당방식

• paging
• segmentation

 

---

연속할당

1 - 1)균등고정분할방식

고정된 boundary에 process 집어넣음

[장점]

구현쉬움

단순

[단점]

partition보다 큰 메모리가 필요할 때 

partition 내부에서 사용될 수 없는 메모리 영역 : 내부단편화 -> 메모리 이용률 낮아짐

미리 할당했기에 multi programming정도가 제약됨

 

새 프로세스를 위한 공간을 만들기 위해 swap in / swap out 해줘야 함

1 - 1)비균등고정분할방식

 

multiple queue는 partition마다 queue가 존재하는 것 같음 : 메모리이용률높임

single queue는 하나의 queue로 partition에 집어넣음 : 유연함

[장점]

상대적으로 구현 쉬움

os overhead가 낮음

[단점]

메모리 이용률이 낮음 : 내부단편화로 인함

멀티프로그래밍의 정도가 낮음

프로세스 사이즈의 한계

 

2)동적분할방식

고정분할방식의 한계를 극복하기 위해 나옴

partition은 메인 메모리에 올라갈 때 load될 때, 즉 run time에 동적으로 생성된다.

위 그림처럼 차곡차곡쌓았다가 가용공간이 부족해 swap out을 하게되면,

공간이 생겨버린다...

이런 공간은 외부단편화라고한다.

동적분할방식은 내부단편화는 없지만 외부단편화 문제가 발생한다.

그래서 주기적으로 memory compaction을 할 필요가 있다. 즉 프로세스를 이동시켜서 외부단편화를 줄이는 것이다.

이런 활동은 CPU overhead가 별도로 필요해진다.

 

여기서 가용역역중 어디에 올릴지에대한 문제가 있다.

• first-fit : 가장 많이 사용되는 방식으로 위에서부터 scan한다. 바로바로결정한다.
• next-fit : pointer을 이용해서 골고루 scan할 수 있다. compaction주기를 짧게한다.
• best-fit : 가장 fit한 공간을 고른다. compaction overhead가 높아서 그렇게 좋진 않다.
• worst-fit : 가장 안맞는 공간을 고른다. compaction주기가 길어진다.

best,worst fit은 시간적비용이 다소 높다. O(n), 기껏해야 O(logn)시간이 소요된다.

 

동적분할방식의

[장점]

내부단편화 x

메모리를 효율적 사용 가능

[단점]

외부단편화 발생

compaction으로 인한 CPU time 낭비

 

 

3)Buddy System

메모리 요청이있을 때 커널은 여유 공간을 분할한다.

 

메모리 블럭은 2^k words를 가지고 있다.(대충 2의 제곱수라는 말)

 

 

처음에 1M가용메모리가 있다.

100K의 메모리가 요구되면 들어갈 수 있는 것 중 가장 작은 사이즈인 128K를 내어준다.

그 다음 240K 요구되면 256K준다.

그다음 64K요구되면 64K준다.

256K요구되면 256K준다

B가 끝나서 해제된다. 256K공간이 생겼다.

A도 끝나서 해제되고 128K 공간이 생겼다.

75K 요구되어 128K공간 내어주었다.

C도 끝나서 해제해주고 64K+64K공간을 128K로 합칠 수 있게된다. 두 영역을 merging해준다.

그후 또 128K+128K합치면 256K생기고 256K+256K하면 512K공간으로 복구된다.

D까지 해제되면 1M공간으로 돌아온다.

 

이러한 점을 볼 때, 병렬 프로그램에 성능이 더 좋을 수 있다.

 

 

---

불연속할당

1)Paging(분산적재)

분산적재란 조각으로 나누는 것.

fixed size의 조각 : paging

가변길이의 조각 : segmentation

 

process는 작은 고정사이즈의 덩어리로 나눠진다. 

page : process의 덩어리 (일반적으로 4KB)

frame : page가 들어갈 수 있는 메모리

보통 page의 크기 = frame의 크기

 

분산적재를 하기때문에 시작주소만으로는 어디에 위치해있는지 알 수 없다.

page table : 프로세스마다 frame의 위치정보를 포함한다.

PMT(page mapping table)이라고도 한다.

 

[장점]

외부단편화 x

내부단편화는 마지막 Page의 일부에만 발생한다.

 

 

f에서 D는 분산적재 되어있다.

각각의 A,B,C,D는 page table을 가지고 있어야한다.

B는 실제로 디스크에있다.

 

Address Translation

분산적재에서 중요한 Issue!

Base&Bounds 문제 -> 새로운 주소변환접근법이 필요하다.

 

relative address = logical address

-> 런타임에 동적 주소 변환을 수행하는 기능을 하드웨어에 구현하기 쉽게한다.

(번역기돌렸는데 먼말일까)

..바쁘니까 생략

 

 

1)Segmentation(분산적재)

segment로 나누어 물리적인 단위로 분산해서 독립적으로 mapping하는 방식

프로세스는 균일하지않은 사이즈의 segment로 나눠진다.

segment table : process가 segment 별로 위치를 알고있어야한다.

 

[장점]

내부단편화x

[단점]

외부단편화로 인한 compaction 필요

 

 

위 그림보면 segment는  permission이라는 칸이 있어서 share와 protect 가능

 

 

 

 

 

 

 

 

요약!!!