09. Main Memory

메모리 할당 기법에는 Contiguous(가장 기본적)과 Multiple partition이 있다. 이때 발생하는 Swapping, Fragmentation 문제를 알아둬야한다.

 

Main Memory

메모리는 데이터를 저장하고 불러오는 장치이다. 컴퓨터는 RAM을 메인메모리로 쓰고 있고 RAM을 구현하는 기술 중 하나가 DDR이다. 이렇게 하드웨어는 오랫동안 변화가 없었다. 메모리 abstraction은 physical address space를 말한다. 메모리라는 디바이스는 abstraction 하기가 아주 쉽고 간단하다. 다른 회사의 메모리라고 해도 별 차이가 없기 때문이다. 메모리는 write(저장), read(읽기) 이 두가지 오퍼레이션만 할 수 있다. 이 기능들을 사용하려면 꼭 주소를 알아야하는데 메모리의 주소는 0번부터 시작하며 byte 단위로 읽고 쓸 수있다. 이것이 pysical address space이다. protection기능( ex)유저는 커널에 접근하지 못함)은 메모리 자체에서 하는게 아니고 OS, CPU가 하는 것이다.

 

알고 가야할 배경 지식

• 프로그램과 프로세스의 차이: 프로그램은 하나의 이미지이다. 스토리지로부터 메모리로 로드되어야 프로세스로써 실행이 된다.
• 메인 메모리와 레지스터는 CPU가 직접적으로 access할 수 있는 스토리지 장치이다.
• 메모리는 address의 데이터를 읽고 쓰기만 할 수 있다.
• 레지스터 접근 시간은 CPU clock보다 적거나 같다. (파이프 라인때문에 평균을 내면 1 아래일 수도 있기때문)
• 메모리에 접근하는건 많은 사이클을 요구하기 때문에 CPU stall을 일으킨다.
• 캐시가 메인메모리와 레지스터 사이의 속도 차이를 완화시켜준다. 메인메모리의 access stall을 낮춰준다.
• CPU의 기능을 이용해서 OS가 제공하는 메모리 protection은 매우 중요하다.

 

복습

배치 프로그래밍과 멀티 프로그래밍

CPU의 효율을 높이기 위해 메인 메모리에 최대한 많은 프로세스들을 넣어두게 되면 하나의 프로세스가 I/O burst에 빠질때 다른 프로세스가 스케줄링되어 CPU burst를 진행하고 또 그 프로세스가 I/O에 빠질때... 무한반복. 따라서 CPU가 쉬는 시간이 없어 전체적인 CPU util을 높일 수 있다. 

이전에는 하나의 프로세스가 피지컬 메모리를 독점하여 메모리 관련 문제가 없었다. 현재는 멀티프로그래밍을 하면서 하나의 Pysical address space안에 여러개의 logical address space가 공존하는 상태이다. (편의상 PAS, LAS로 줄여부르도록 하겠다.) 따라서 메모리 utilization을 얼마나 가져갈것이냐, 이를 얼마나 공평하게 해결할 것이냐의 문제가 생겼다.

 

Pysical address space VS Logical address space

PAS는 OS가 관리하는 피지컬 메모리의 abstraction이다. 이것을 LAS에 나눠주는 것이 메모리 관리의 핵심이다.

컴파일 time이나 load time에서는 LAS와 PAS의 차이가 없다.

run time에는 차이가 생긴다. 달라진 간격을 맞춰주기 위해 MMU가 abstraction translate 해야한다.

 

 

사용자가 소스코드를 짤때 address space를 생각하지 않아도 되는 이유

컴파일러가 관리해주기 때문이다. 컴파일이라는 과정을 거치면 LAS가 생긴다. 컴파일러가 없던 시절엔 PAS에 직접 데이터를 썼다. 이때 LAS를 쓰는 프로세스는 반드시 한개여야한다. 컴파일러는 프로그램이 쓰려는 변수들만 LAS에 배치한다. 주소를 0x0004 이런 숫자로 변환하여 메모리 공간을 만들어낸다. 컴파일 단계에서 필요한건 코드, 데이터이고 이 단계에서 LAS의 크기가 결정된다. 다시 말하면, 우리가 짠 소스코드의 주소는 변수로 구성되고 이 주소가 컴파일되어 LAS라는게 생성되면 거기에 코드와 데이터가 배치된다. LAS의 최대크기는 4GB이다. 이 중 유저가 쓸 수 있는 메모리 공간은 3GB이다. 4GB가 주어지지만 사실상 최대 3GB까지 쓸 수 있는 것이다. LAS가 컴파일 했을때 쓰는 영역은 프로그램마다 다르지만 컴파일 단계에서 영역이 결정되는건 동일하다. 이때 LAS를 PAS에 어떻게 붙일것인가에 대한 문제가 있다. stack, heap은 각각의 프로세스이다. LAS가 로딩되면 실제 프로세스의 AS로서 동작하는데, 이때 여기에 heap, stack을 붙인다.

ex) A의 LAS는 0부터 3이고 B의 LAS는 0부터 4이다. 이를 한 PAS에 순서대로 붙여주면 A는 PAS의 0~3을 차지하고 B는 4~7을 차지한다. A는 우연히 기존의 주소와 같아서 데이터에 접근이 가능하지만 B는 기존의 주소인 0~4와 달라 로딩할 수 없다. 이때 LAS와 PAS가 안 맞아 문제가 생긴다.(멀티프로그래밍에서 흔하게 나타남) 이런 indirect 문제는 해결할 수 없기때문에 runtime에 메모리 접근할때마다 어디에 접근하는지 보고 주소에 +3을 해줘야한다. 결국 컴퓨터가 아주 느려지게된다. 소프트웨어적으로 해결할 수 없으므로 하드웨어 CPU의 도움을 받아야한다. CPU가 메모리 addressing을 할때 자동으로 +3을 해주면 된다. MMU를 만드는 것이다.

 

Memory management

메모리 관리에서 집중적으로 봐야할 것

• Utilization ) 물리 메모리를 얼마나 아껴쓰는지. Fragmentation은 Util을 방해하는 요소이다.
• Performance ) 메모리 접근 속도가 얼마나 빠른지. address transration과 swapping 문제 발생.

메모리 관리의 네가지 기법

• Contiguous allocation
• Segmentation
• Paging
• Demand paging(paging+virtual AS) 실제 대부분의 OS는 이 방식으로 메모리를 관리함

Address translation with MMU

LAS와 PAS의 미스매치를 맞춰주는 디바이스이다.

relocation 레지스터에 각각의 LAS의 시작주소를 넣어놓고 CPU가 접근하는 메모리 주소마다 주소를 더해주는것 -> address translation됨

각 프로세스는 자기에게 할당된 PAS 밖으로 접근하려고 하면 안된다. 접근하면 안되는 메모리 공간에 접근하게 되면 segmentation fault가 발생한다. 이를 막기 위해 limit 레지스터에 프로세스의 크기를 담아놓고 over되면 trap이 발생하면서 addressing 에러를 낸다.

 

1. Contiguous Allocation (연속적인 할당)

LAS를 그대로 PAS에 붙이는 것이다. Address translation 관점에서는 큰 문제가 없다. 하지만 utilization때문에 countiguous allocation에서는 속도 문제가 발생한다. 이를 메모리 복사나 swapping으로 해결하려고 하면 utilization을 올리려다가 성능이 엄청 떨어지는 또 다른 문제가 발생한다. (util과 performance 사이의 트레이드 오프는 심각해서 사실상 해결하기 어려움) 메모리 카피를 하게되면 메모리 접근을 반복하기도 하고 캐시가 엉망이 되기때문에 아주 오랜 시간이 걸린다. 따라서 메모리 공간을 조각내는 방법을 사용해야한다.

 

Multiple-partition allocation

이 기법의 한계는 fragmentation 되어있는 공간을 활용할 수 없다는 것이다. 8, 6의 크기로 나뉜 공간에 10을 할당하고 싶을때 못함.. 3을 할당하려고 할때도 8에 할지 6에 할지, 남은 공간의 앞에 할지 뒤에 할지 고민해야함.

• Firts-fit: 앞에서부터 빈공간을 찾고 비어있으면 할당한다
• Best-fit: 프로세스가 들어갔을때 더 적게 남는 공간에 할당한다. 나중에 더 큰 프로세스가 올 것을 대비하는 것.

 

메모리 할당에서 발생하는 문제

Fragmentation

조각이 여러개로 나뉘어져있어서 문제가 발생한다.

• External Fragmentation) 위의 모든 예제에 해당한다. 조각의 외부에서 발생한다. 요청을 충족할 메모리공간이 있지만 연속적이지 않다.
• Internal Fragemntation) 조각 내부(LAS)에서 발생한다. 할당을 해줬는데 쓰지 않는 문제이다. utilization이 낮아진다.

Swapping

메모리에 큰 공간을 만들기 위해 여러 프로세스들을 정리해야할때가 있는데 이런 경우엔 어쩔 수 없이 프로세스들을 스토리지로 옮겼다가 메모리에 다시 할당해야한다. 예를 들어, 크기가 10인 공간의 3~4, 7~9번째 주소에 프로세스가 돌고 있다. 이때 5짜리 프로세스가 들어오고 싶어한다. 하지만 공간이 남지 않으니 앞의 프로세스를 잠깐 스토리지에 swap out하고 정리하여 메모리로 swap in한다. 메모리 복사와 할당 등의 문제로 현실적으로 쓸 수 없다.

 

 

 

2. Segmentation

• segmentation과 paging은 조각을 어떻게 내는지의 차이이다. segmentation은 조각 크기를 프로그래머가 임의적으로 결정한다. paging은 사이즈가 정해져있고 프로그래머가 신경쓰지 않아도 된다.
• 프로그램은 main program, procedure, stack 등의 여러 세그먼트들의 결합으로 볼 수 있다. 각 segment들은 LAS을 가진다고 생각하고 PAS에 분배하는 것이다. 순서도 아무렇게나 할 수 있다.
  ex) <1,100> //1번 segment의 100번 주소에 접근한다는 뜻
• os는 segment를 관리하기 위해 segment table을 만든다. 프로세스의 base address는 프로세스 고유의 데이터로, PCB에서 관리되어야하므로 (P1, 100)과 같은 튜플이 생긴다. //P1의 base는 100
• segment table은 base, limit 두가지 정보를 가지고 있다.
• segment table의 크기가 커서 레지스터에 저장 못하고 메모리에 저장한다. segtable은 프로세스마다 따로 있다. 
• segment의 address translation 과정
  CPU가 address를 부름 <segment 번호, offset> -> segment를 segment table에 보내고 base에서는 해당 base address값을 찾아 더해주고 limit에서는 크기 over의 여부를 파악함->PAS로 보냄
• utilization은 높아지나 성능은 낮아진다. 메모리에 있는 table에 접근해야하므로 데이터를 가져오는 시간이 두배가 되기 때문이다.

=> segmentation은 Utilization 관점에서 external은 완화됐지만 Internal은 여전하다. Performance는 나빠졌다. address translation이 오래걸리며(캐시없이 쓸 수 없는 정도) swapping을 한다고 해도 프로그래머가 segment를 하나로 만들면 나아지는건 없다.

 

 

3. Paging
프레임이란? PAS를 나눈 조각. ex) 16GB를 4GB로 나누면 4개의 프레임이 나옴. 4MB로 나누면 4096프레임이 나옴. 한 한 프레임의 크기는 보통 4KB임.

• LAS는 페이지로, PAS는 프레임으로 만들어준 후 페이지에 대해 프레임을 할당한다. PAS의 어디에 넣든 속도가 똑같으므로 아무곳에 넣어도 된다(메모리의 랜덤 엑세스 특성 / 하드디스크 , SSD는 속도가 다름). LAS크기는 4GB
  ex) <0,100>이라고 하면 0번째 페이지의 100번째 데이터에 접근한다는 뜻이다. 0번째 페이지가 1번 프레임에 할당되어있다면 1번 PAS의 100번째 데이터를 가져오면 된다.
• 페이지 테이블의 총 공간은 4byte로 이는 32bit이다. 페이지는 page number과 page offset으로 이루어져있는데 offser의 크기는 4KB이다. 12bit으로 표현할 수 있다. number은 20bit가 된다.
• 한 프로세스에서 발생할 수 있는 Internal의 최대 크기는 1frame-1byte이다. ex)4KB에서 최대 4095byte 낭비가능
• 4, 4짜리 공간이 있다고 하자. 8크기의 프로세스가 들어오려고 하고 이때 페이지의 크기는 1이다. 8을 페이지 단위로 나누면 1짜리 공간이 8개 나온다. 페이지와 프레임을 연결시켜주면 8개의 공간을 모두 활용할 수 있다.
  =>external 문제가 완전히 없어진다. Internal 문제도 최소화된다. 성능은 segment와 마찬가지로 메모리에 있는 Paging table을 이용하므로 캐시의 도움없이는 너무 느리다. 이는 페이지 테이블 구조상의 문제이므로 하드웨어의 도움을 받아야한다.

TLBs

페이지 테이블을 담을 수 있는 커다란 레지스터를 CPU에 넣는 방법은.. 비용문제가 있다.

TBL를 MMU에 꽂는 방법으로 해결할 수 있다. TLB은 페이지 테이블의 프레임 번호를 알고 있다. 그러므로 페이지 테이블(메모리)에 가지않고도 TLB에게 물어보면 프레임 번호를 알아낼 수 있다. 캐시와 비슷한 역할을 하는 것이다. 페이지 테이블의 1024*1024개의 엔트리중 일부만 알고 있으므로 페이지 테이블보다 크기가 훨씬 작다. 

TLB는 메인 메모리보다 빠르고 레지스터보다 싼 associative memory로 이루어져있다.

처음엔 TLB가 비어있다. logical address를 pysical address로 바꿔주기 위해 CPU가 TLB에 데이터가 있는지 물어본다. TLB는 비어있으니 없다고 대답한다. 그럼 CPU가 페이지 테이블에 접근해서 프레임번호를 참조하여 PAS에 접근한다. 이것을 TLB miss라고 부른다. 이때 찾은 프레임 번호를 TLB에 업데이트 해준다. 이렇게 점점 TLB에서 정보를 찾을 확률이 높아진다.

 

EAT(Effective Access Time)

실제 메모리에 가서 내가 원하는 데이터를 찾아올 수 있는 시간 계산

EAT=TLB access time + Hit case + Miss case
     =TLB access time + hit ratio*memory access time + 2*memory access time*(1-hit ratio)

 

여러개의 LAS가 같은 PAS를 가리키도록 해서 메모리를 공유하는 법

공유할 프레임의 번호를 각 프로세스의 페이지 테이블에 모두 넣어준다.

ex) 공유할 프레임 번호가 3,4,6 이라면 각 프로세스에는 3,4,6 그리고 자신의 데이터가 담긴 프레임 번호를 넣어준다.

 

 

Hierarchical Paging

이제 남은 문제는 페이지 테이블의 크기가 너무 크다는 것이다. 이는 페이지 테이블을 계층적 구조화하여 해결할 수 있다. 페이지 테이블에 다시 페이징 기법을 적용하여 계층적 구조화한다. 페이지 테이블을 쪼개서 PAS에 연속적이지 않게 배치한다. 페이지 테이블 중 사용하지 않는 영역은 배치하지 않는다. 이 방식을 쓰면 2 level 페이지를 조각내서 관리할 수 있고 필요하지 않은 프레임 조각을 할당하지 않아도 되므로 Utilization 측면에서 용량이 훨씬 줄어든다.

 

이 부분 그림 보기

 

=>Paging의 Utilization은 Fragmentation보다 낫다. 페이징 기법으로 Internal, external 문제를 해결했고 거기서 일어나는 또 다른 문제는 계층적 구조화를 통해 해결했다. Performance 문제는 TLB로 해결했다.