Memory Management_운영체제(9)

Memory Management

Goals

• programming을 하는데 있어서 편의성을 제공하는 것
• 한정된 memory를 여러 process가 최고의 performance를 수행하고 minimal overhead를 가지게 하는 것
• 각 process 사이에 철저한 isolation(보호, 독립)

Single/Batch Programming

• OS를 제외한 나머지 영역은 하나의 process가 독점적으로 사용하는 방식
• OS가 RAM, ROM 영역에 수반되어 있는 경우도 있었다.
• 조금 더 진화해서 Device Driver가 ROM에 수반되어 있는 것이 생겼다.
• 크게 memory management가 필요 없었다.

Multiprogramming

• CPU, I/O를 동시에 할 수 있도록 작업한다. - Concurrency
• 각 process는 다양한 size와 연속적인(contiguous) 공간을 할당받는다.

Requirement

• Protection : 각 process가 사용할 수 있는 address space를 지원한다.
• Fast translation : 빠르게 접근 가능한 영역을 구분하기 위해 checking하는 것
• Fast context switching : 각 process가 context switching을 하면서 사용할 memory를 빠르게 updating해야한다.

Address binding

• address가 결정되면 해당 지점으로 호출을 한다.
• program이 정상실행 되려면 memory에 program을 올려야하는데, 만일 해당 memory 주소에 다른 process가 있다면 첫 주소에서부터 전체적으로 옮겨야한다.
• 주소 변경은 multiprogramming system에 좋지 한다.
  • physical memory의 available space 상태는 계속해서 변한다.
  • 비현실적, 비실용적인 방법이다.
• application address space와 physical address space를 완전히 분리시킨다.
• virtual address space(logical address space) : application이 사용하는 영역, 사용자가 임의로 사용하는 영역
• OS는 virtual address를 translate하여 physical memory에 할당한다.

Fixed Partitions

• memory를 같은 크기로 분할하고, 이는 고정되어있다.
• user process의 영역을 virtual address space라고 한다. 그리고 application이 생각하는 address를 virtual address라고 한다.
• Base register address + virtual address = physical memory address로 할당하는 방식
• address translation : virtual address에서 physical address로 전환하는 것, hardware에서 이루어진다.
• 다른 partition으로 옮기려면 base register만 전환하면 된다.
• multiprogramming degree : 한번에 동시에 동작할 수 있는 multiprogramming 수
• degree는 partition의 수로 결정된다.
• base register의 값을 정하는 것은 OS가, 전환하는 것은 hardware가 한다.
• 장점 : 구현, translation, context switch가 쉽다.
• 단점
  • Internal fragmentation : program의 크기가 어떻든간에 한 개의 partition을 할당하는데, 만약 사용공간이 적은 program이라면 낭비가 심해지며, 해당 남은 공간을 다른 process에게 할당해줄 수 없다. 이러한 남는 공간을 Internal fragment라고 한다.
  • partition size : 크기를 크게하면 fragment가 커지고, 작게 한다면 fragment는 작아지지만 큰 process는 들어가지 못하는 문제가 생긴다.

Improvement

• partition을 동일한 크기가 아니게 나눈다.
• First fit : 쭉 순회하며 해당 process가 들어갈 수 있는 처음 마주한 공간에 할당
  • 금방 찾지만 internal fragment가 커질 수 있다.
• Best fit : 해당 process와 internal fragment가 가장 적은 공간에 할당
  • internal fragment는 작지만 시간적으로 오래 걸린다.

Variable Partitions

• OS가 특정 partition을 결정해두는 것이 아닌, 각 시점마다 가용한 memory 주소를 찾아 시작 주소와 끝 주소를 결정하는 방식
• Base register : 시작 주소를 결정 해준다.
• Limit register : 끝 주소를 결정한다.
• size 이내에 할당할 수 없다면 protection fault로 판단한다.
• 각 process의 limit과 base는 PCB에 저장되고 관리된다.
• limit register도 OS가 관리한다.
• virtual address(offset) < limit : protection fault
• First fit : 빈 hole에 넣을 수 있다면 바로 넣는 방식
• Best fit : 모든 hole을 찾아보고, 현재 요청 program과 크기가 가장 근사한 곳에 넣는 방식
• Worst fit : 가장 큰 hole에 할당하는 방식
• 장점
  • 필요한 만큼만(base to limit) 사용하기 때문에 internal fragmentation이 없다
• 단점
  • External fragment : 사용할 수 있지만 크기가 작아서 실제로 사용이 불가능한 hole
• solution of external fragment
  • compaction(coalescing) : 작은 fragment들을 모아서 사용함
  • paging/segmentation

Overlays

Overlays

• 언제든지 필요한 instruction과 data만 memory에 저장
• 2개의 pass는 exclusive하다.
• User에 의해 관리

Advantage

• OS의 도움이 없어도 된다.
• process가 할당된 메모리의 양보다 클 때 유용하다.

Problem

• programming이 어려워지고 복잡해진다.

Dynamic Linking

• linking(binding) : 여러 obj file들을 결합시키는 작업, 각 실행 file의 위치에 대한 주소를 결정된다.
• static linking : 실행 파일을 만들 때 라이브러리를 같이 포함시켜서 .exe 파일을 만드는 것
• dynamic linking : 작은 stub을 만들어 사용하며 많이 쓰이는 라이브러리는 메모리에 하나만 올리는 방법
• stub : 껍데기 코드 → ex) call stub to printf()
• 실행시간을 줄여준다.
• linux : shared library(.so) / windows : DLL(.dll)

Swapping

• swapping space(backing store) : memory에 있는 program image를 copy하는 공간
• 잠시 memory에 있는 process를 swapping space로 대피시켜 메모리를 잠시 확장하는 것
• swap space는 같은 HDD를 쓰더라도 구조 공간이 다르다.
• Hardware가 Main memory를 support하는 개념
• data transfer time이 중요하다.
• I/O를 하고 있는 pending process는 swap하지 않거나 모든 I/O는 kernel buffer에 담아서 한번에 전달하는 방식을 사용한다.

Virtual Memory

Virtual Memory(VM)

• 모든 접근은 Virtual address를 사용한다.
• virtual address space는 굉장히 크고 연속된 공간이라고 가정한다.
• virtual address는 반드시 physical address로 translate 해야 한다.
• physical memory는 요청에 의해서 할당하고 release한다.
• 각 process마다 독립적이다.
  • A의 0x7000과 B의 0x7000은 같아보이지만 다른 것이다.

lazy loading (loading on demand)

• program들은 전체 크기만큼 physical memory에 전부 올리지 않아도 실행이 된다.
• ex) 1GB짜리 program이 1GB만큼 전부 올리지 않고 일부만 올려도 실행이 된다.

example

• 출력되고 있는 hexa 주소는 가상의 주소이다.
• physical address를 출력하면 매번 바뀌는 다른 주소가 나올 것이다.

Virtual Address(Logical Address)

• cpu에서 주는 address는 virtual address다
• 이러한 virtual address는 hardware에서 translate가 되는데, 결과로 나온 address는 OS가 할당하는 것이다. - previleged instruction
• VAS : virtual address space를 모아둔 집합

Advantage

• 사용자, program으로부터 논리적인 공간과 물리적인 공간을 분리시킬 수 있다.
  • programmer에게 memory 할당에 따른 부담을 덜어준다.
• lazy loading과 같은 방법으로 program의 일부만 memory 공간에 올라가도 작동할 수 있도록 한다.
• degree of multi-programming : 얼마나 많은 program이 함께 작동하는가?
• degree of MP가 늘어난다.
• 단위 시간당 발생하는 I/O가 줄어든다.
• process들의 file이나 memory를 공유하기가 쉬워진다.(OS의 허락하에)
• protection이 확실해진다.
• process creation이 효율적이게 된다.

Disadvantages

• 매 instruction마다 translate를 하기 때문에 time / space에서 성능 저하 요소가 있다.

Implementation

• Paging
• Segmentation

Paging

• physical address space가 불연속적인 상황도 가능(uncontiguous)
• process를 분할하여 physical memory의 빈 공간에 나누어 넣는 방식
• page : 분할된 process의 조각(virtual memory에서)
• 각 page가 memory에 들어가 있는 정보(주소)가 있는 table은 OS가 관리한다.
• 1개의 page는 1개의 frame안에 들어간다.
• page/frame size는 2의 지수 크기이다.
• n pages program을 실행하려면 n개의 frame이 필요하지만, 초기에는 lazy loading 때문에 n개가 모두 필요하지는 않다.
• page table : page의 정보들이 담겨있는 공간
• 각 page table의 index는 page 번호를 의미하고, 해당 index의 내용에는 frame의 위치(번호)가 입력되어 있다.
• 각 process마다 자기 자신을 위한 page table이 존재한다.
• context switch가 된다면 page table도 switch가 된다.

User perspective

• user는 물리적인 메모리에 대해 모른다.
• 실제로는 page가 physical memory에 분할되어 나누어져 있고, 이는 page table과 mapping이 되어있다.
• page table에서 이상한 주소 값이 들어가도 결국 자신의 process 내로 가기 때문에 protection은 완벽하게 지켜진다.

Translating addresses

• <virtual page number(VPN)::offset>
• VPN : VA(virtual 주소) / page(n)
• offset : VA(virtual 주소) % page

Protection

• page table의 각 entry마다 frame number 외에도 protection에 관련된 정보 등 여러 정보를 담고 있다.
• Valid / Invalid bit
  • Valid : 해당 page가 process 안에 들어있는 적법한 page이고, 그 page가 frame에 적재되어 있다.
  • Invalid : 해당 page number가 process의 virtual address space에 들어있지 않다. 경우에 따라 적법한 page여도 frame에 적재되어 있지 않다.
• read-only, read-write, execute-only protection을 적용할 수 있다.

Page tables

• Valid bit(V) : page table이 사용될 수 있는지, 적법한지를 나타내는 bit, virtual address가 사용될 때마다 check
• Reference bit(R) : 해당 page가 access, reference가 된 적 있는지 나타낸다. read/write가 된 적 있는지 check
• Modify bit(M) : page가 처음 내용과 변경되었는지 나타낸다.
• Protection bits(Prot) : read/write/execution 등 operation control
• Page frame number(PFN) : frame number가 담겨져 있다.

Advantage

• physical memory를 할당하는 것이 비교적 쉽다.
  • frame의 free list를 가지고 있다가 1개씩 할당하면 된다.
• external fragmentation이 없다.
• program의 일부분을 page out(내보내기)하기 쉽다.
  • invalid라면 paged-out하면 된다.
  • disk block size의 배수로 page size를 정한다.
• 불법적인 접근으로부터 page를 보호할 수 있다.
• 서로 다른 process간의 page 단위로 정보를 교환하기 쉽다.

Disdvantage

• internal fragmentation이 존재한다.
• 시간측면에서 overhead가 존재한다.
  • address마다 2번의 reference가 필요하다. TLB를 통해 해결한다.
• page table을 저장하는 memory가 크기 때문에 overhead가 있다.

Demand Paging

• 요구가 있을 때 paging을 하는 방식
  • I/O가 비교적 적게 일어난다.
  • memory를 적게 사용한다.
  • response time이 빨라진다.
  • 동시 user가 늘어난다. → Multiprogramming degree가 증가한다.
• OS 입장에서 main memory를 system에서 동작하는 모든 process들이 사용하는 data, instruction 중 필요한 page만 memory에 올리는 cache처럼 사용하는 것이다.
  • 초기 physical memory에서만 할당하다가 physical memory가 가득 차면 안쓰는 부분을 빼고 채우면 된다.
• page replace를 했을 때 evict된 page는 swap file(disk partition)로 이동한다.
• OS에 의해 memory/disk 사이에 이동이 발생한다.

Page Fault

• page table에 translation을 하려고 하는데, page가 main memory에 올라와있지 않은 상황
• invalid page를 access하면, PTE를 통해 알게되고 exception(fault)가 발생한다. → OS에게 전달
• fault가 발생하면 OS는 page fault handler를 작동한다.
• swap file에 있는 page를 찾아서 physical frame으로 읽어들인 뒤, PTE가 frame을 가리키도록 update하고 valid하다고 설정한다. 이 후 멈춘 process에게 제어가 넘어간다.
• page replacement algorithm에 의해 page가 evict된다.
• Locality
  • Temporal locality : data, memory의 위치에 접근했다면, 그 위치에 다시 접근할 확률이 매우 높다.
  • Spatial locality : data, memory위치에 접근했다면, 해당 위치의 가까운 주변에 다시 접근할 확률이 매우 높다.
• locality는 일반적으로 paging이 빈번하지 않게 일어난다는 것을 보여준다.
• 아래의 경우에는 paging 횟수가 달라질 수 있다.
  • application에서 locality의 정도
  • page replacement 정책
  • physical memory의 양
  • reference pattern이나 memory footprint

Segmentation

• program의 논리적인 내용에 따라 주소변환을 지원하는 방식
• Code, stack, heap, function, data array 등 논리적인 정보를 활용한다.
• 각 논리적인 객체마다 segment 번호를 매긴다. 그리고 offset 또한 매긴다.
• variable partition은 한 process에 1 개의 segment를 부여하지만, Segmentation은 한 process에 여러 개의 segment를 부여하는 방식
• segment number는 compiler가 지원해서 부여한다.

Segmentation Advantage

• 논리적인 data structure를 독립적으로 다룰 수 있다.
• protect를 하기 쉽다.
• 서로 다른 process간에 base/limit만 공유하면 되기 때문에 segment를 공유하기 쉽다.

Segmentation Disadvantages

• Cross-segment addresses : 서로 다른 process간에 segment를 공유할 때, 같은 segment 번호를 사용해야 주소값이 valid해진다.
  • 다른 변수를 거쳐 segment 번호를 사용하는 indirect addressing을 사용한다.
• segment table size가 커질 수 있다.
• External fragmentation이 발생할 수 있다.

Segmentation Advantage

• 논리적인 data structure를 독립적으로 다룰 수 있다.
• protect를 하기 쉽다.
• 서로 다른 process간에 base/limit만 공유하면 되기 때문에 segment를 공유하기 쉽다.

Segmentation Disadvantages

• Cross-segment addresses : 서로 다른 process간에 segment를 공유할 때, 같은 segment 번호를 사용해야 주소값이 valid해진다.
  • 다른 변수를 거쳐 segment 번호를 사용하는 indirect addressing을 사용한다.
• segment table size가 커질 수 있다.
• External fragmentation이 발생할 수 있다.

Segment with Paging

• 하나의 segment를 여러 개의 page로 분할하는 기법
• segment의 정보를 관리하면서 segment를 page 기법을 이용하여 chunk로 나눈다.
• segment 전체를 memory로 올리는 것이 아닌 일부 page를 memory에 올리는 것 ← demand paging
• external fragmentation을 없앨 수 있다.