Operating Systems 9. Main Memory - (1)

 

Background

메모리는 각각 주소가 할당된 일련의 워드 또는 바이트로 구성되어 있다.

CPU 는 PC가 지시하는 주소에서 메모리로부터 다음 명령어를 가져온다.

해당 명령어는 필요한 경우 추가적인 데이터를 가져올 수 있고, 반대로 데이터를 메모리로 내보낼 수도 있다. 

 

 

우리가 작성한 code 는 compile (목적파일 생성, 기계가 이해할 수 있도록 번역) 과 linking (library 와 obj 파일들을 모아서 실행가능한 파일로 바꾸는 과정) 을 거쳐서 실행가능한 FILE 을 생성한다.

이 실행가능한 파일이 Loading 되면 메모리에 올라오는 것이다. 

 

기계어 명령어를 하나 실행하는데 최소 1번에서 최대 3번의 메모리 접근이 일어날 수 있다.

최소 1번은 메모리의 text에서 명령어를 가져오는 것이고, 최대 3번의 경우에는 피연산자를 가져오는 데 1번, 결과를 다시 메모리에 저장하는데 1번 , 총 2번이 추가된 결과이다. 

 

프로그램은 disk 에서 메모리로 적재된 후 프로세스가 되어 실행된다.

CPU가 직접 접근 가능한 기억장치는 CPU register 와 Main Memory이다.

CPU register 는 하나의 CPU clock에 접근 가능하며, Main memory 는 접근에 여러 CPU cycle이 소요되어 processor stall 이 발생한다.

따라서 CPU 와 main memory 사이에 cache 메모리를 추가하여 processor stall 빈도를 감소할 수 있다. 한편, 메모리는 주소와 읽기 요청 또는 주소+데이터와 쓰기 요청의 단위만 볼 수 있다. 

 

 

 

Base and Limit Registers

시스템 성능 향상을 위해서 메모리에 여러 개의 프로세스들이 동시에 유지되어야 한다.

이러한 올바른 동작을 보장하기 위해선 메모리 보호가 필요하다.

메모리 보호방법은 프로세스에게 독립된 주소 공간을 제공하는 것이다.

각 프로세스는 분리된 메모리 공간을 확보하는데, base register 와 limit register 를 통해 물리 메모리 내의 프로세스 주소 공간을 결정하는데 사용된다.

즉, 주소 공간이 서로 중첩되지 않게 모든 프로세스의 base/limit 를 설정해야 한다.

base register 은 가장 작은 물리 메모리 주소를 가지고 limit register 은 프로세스 주소 공간의 크기를 지정한다.

 

합법적이지 않은 주소(base 보다 작거나, base + limit 보다 큰 경우) 에 대해서는 trap을 발생시켜서 메모리를 보호한다. 

 

 

Address Binding

주소 바인딩이란 프로그램의 명령어/데이터 주소(논리적 주소)를 물리적 메모리 주소로 바인딩 하는 것이다. 

주소 바인딩 시점은 다음과 같다.

 

Compile time : 컴파일 시점에서 적재될 메모리 위치를 미리 안다면, absolute colde 를 생성할 수 있다. 그러나 시작 위치가 변경된다면, 코드를 다시 컴파일 해야 한다. (특수목적의 임베디드 시스템이 사용)

Load time : 메모리 위치는 적재 시에 결정된다. 따라서 relocatable code 를 생성해야 한다.

compile, load time 시에 주소가 적재된다면 주소가 Static 한 상태이다. 따라서 프로그램이 실행 중에 메모리에서 쫓겨나거나 swapping 될 때에도 똑같은 주소로 결정이 되어 문제가 발생하고, 논리적 주소와 물리적 주소가 동일하다.

 

따라서 주소 바인딩은 대부분 실행시간에 일어난다. Execution time 에 일어나는 주소 바인딩은 동적 바인딩으로, 논리적 주소와 물리적 주소가 동일하지 않다.

 

 

 

Logical  vs Pyshical Address Space

논리 주소란 프로그램이 사용하는 주소이고, 물리적 주소란 물리적 메모리 장치가 사용하는 주소이다. 논리 주소를 물리 주소로 맵핑하는 작업을 실행시간에 수행하는 것이 Memory-Management Unit 인 MMU이다.

프로그램은 논리 주소만 사용하며, 실제 물리적 주소를 알지 못한다. 

 

 

 

Memory-Management Unit (MMU)

MMU는 가상의 주소(논리 주소)를 실제 물리적 주소로 실행시간 때 맵핑해주는 하드웨어 장치이다. 프로세스에 의해 생성된 모든 주소값이 메모리로 보내질 때는 Base register (기준점) 이 더해져야 한다. Base register 은 relocation register(재할당) 레지스터이다.

 

 

 

Dynamic Loading

실제로 호출되기 전에 각 루틴은 메모리로 적재되지 않고, 필요할 때마다 storage 에서 메모리로 불러서 사용하는 것을 동적 적재라고 한다.

따라서 메모리에 올라올 때마다 주소가 바뀔 수 있다.

이러한 적재의 장점은 향상된 메모리 공간 활용이다.

사용하지 않는 루틴은 적재되지 않기 때문에 많은 양의 코드가 덜 빈번히 사용되는 경우에 유용하다. 

 

 

 

Dynamic Linking

동적 링크란 올라온 routine 들이 동적으로 shared library 를 통해 참조하는 코드에 접근하는 것이다. 따라서 동적 링크는 library 의 링크가 실행시간까지 미루어진다.

또한 stub 라는 작은 코드는, library 를 어떻게 찾는 지를 알려주는 코드로, 실행 시에는 stub 코드가 shared library 코드로 치환된다.

 

 

shared library 란 동적링크 라이브러리(DLL) 로, 공유 라이브러리를 사용하는 모든 프로세스는 한 개의 library 코드만 공유하여 사용한다.

여러 프로세스들이 pointing 하여 사용하기 때문에 메모리에 한 번만 차지하게 된다.

만약 static library 라면, library 를 사용하는 프로세스마다 중복되어 메모리에 올라올 것이므로 메모리 공간 낭비가 생길 것이다. 

 

 

 

메모리 할당

프로세스가 차지해야 할 크기만큼 메모리의 빈 공간에 할당해야 한다.

연속적인 공간에 메모리를 할당하는 방법으로는 고정 분할 기법과 가변 분할 기법이 있다.

고정 분할 기법은 메모리를 동일한 크기의 파티션으로 분할 하는 것으로, 요즘은 거의 사용되지 않는다.

가변 분할 기법은 가용 공간과 운영체제가 사용되는 부분을 테이블로 관리하고, 가용 공간에 프로세스를 할당하는 것이다. 

요즘은 조각된 메모리를 이어서 프로세스에 할당하는 비 연속적인 메모리 할당도 사용되고 있다. 

 

가변 분할 방식에서 운영체제는 할당된 공간과, 할당 가능한 free 공간(hole) 에 대한 정보를 관리해야 한다.

 

 

Contiguous Allocation

메인 메모리는 두 부분으로 구분되는데,  low memory 에는 커널을, high memory 에는 사용자 프로세스를담는다.

이때 연속적인 메모리 할당 시스템에서는 각 프로세스들이 연속적인 메모리 공간을 차지하게 되고, 프로세스가 자신의 범위를 넘지 못하도록 하기 위해 base/limit 레지스터를 사용한다. 

 

 

 

Dynamic Storage-Allocation Problem

동적 메모리의 free hole 에 할당하는 여러가지 방법이 있다.

 

- First-fit : 요청을 수용할 수 있는 첫 번째 hole 을 할당한다. 

- Best-fit : 요청을 수용할 수 있는 smallest hole 을 할당한다. 

- Worst-fit : 요청을 수용할 수 있는 largest hole 을 할당한다.

 

 

 

Fragmentation 

물리적인 공간을 연속적으로 사용해서 생기는 문제이다. 메모리 단편화의 종류는 다음과 같다.

 

- 외부 단편화(External fragmentation) : 요청한 크기보다 작은 메모리 블록들만 존재한다. 즉, 할당되지 않은 공간이 분포되어서 낭비되는 경우이다.

전체 메모리 크기의 합이 요청한 크기보다 큰 경우에도 요청한 크기의 메모리를 할당할 수 없다.

 

- 내부 단편화(Internal fragmentation) : 요청한 것 보다 더 큰 메모리를 할당하여, 할당된 메모리의 일부가 사용되지 않아 낭비되는 경우이다. 

 

 

Segmentation

논리 주소 공간은 segment 들의 집합으로 이루어졌는데, 이는 사용자 관점의 메모리이다.

즉, 사용자 공간에서 여러 개의 segment 로 나누고 각 segment 를 메모리 공간에 재할당하는 방식이다.

논리 주소는 <segment number, offset> 으로 이루어진 주소이다. 

 

이러한 방법은 Segment table 을 만들어 수행된다.

이 table 에는 프로세스의 번호와 base 와 limit 가 저장되어 있다. 따라서 Logical 주소를 segment table 을 보고 physical 주소로 매핑시켜주는 것이다. 

segment 별로 보호비트인 read/write/execute 권한을 지원할 수 있으며, 유효비트도 존재하여 0 일 경우 유효하지 않은 경우를 나타낸다. 

 

Paging

페이징이란 비연속적인 물리적 메모리 할당 방법 중 하나로, 논리 메모리를 같은 크기의 블록으로 나눈 페이지 단위로 할당하는 것이다.

Page 는 논리적 단위이고, Frame 은 물리적 메모리를 고정된 크기의 블록들로 나눈것이다.

따라서 Page 를 Frame 에 맵핑하여야 하는데, N pages 사이즈의 프로그램을 돌리기 위해선 N free frames 이 필요하다는 뜻이다.

page 단위가 작을수록 external fragment 가 줄어들 것이다. 

 

논리 주소를 물리 주소로 맵핑하기 위하여 page table 이 필요하다. 

page table이란 각 페이지의 base address 들을 저장한 물리적 메모리에 있는 테이블이며, page number 가 index처럼 사용된다.

 

 

Address Translation Scheme

CPU 에 의해 만들어진 주소는 page number (p) 와 page offset (d) 두 부분으로 나뉜다.

 

page number 은 page table 의 index 로써 page table에 접근할 때 사용된다.

page offset 은 physical address 를 얻을 때 쓰이며, page table 의 base address 에 page offset 을 더하면 physical address 를 구할 수 있다.

 

다음 그림에서 page크기가 4kb 라고 가정하면, logical address 의 상위 20개 number 은 page number가 되며, 하위 12개의 number 은 offset이 된다. 

 

따라서 논리주소의 p (20bit) 를 보고 page table 에서 몇 번째 page 인지 index 를 찾고, page내부에서 offset 을 얼마를 더할지 d (12bit) 를 보고 정한다.

그렇게 찾아온 page table 에 있는 정보를 보고, physical address 로 접근할 수 있다. 

 

 

 

Paging Hardware

페이지 테이블은 물리 메모리 각 페이지의 기본 주소를 포함하고 있으며, 페이지 테이블은 각 프로세스 별로 생성된다. 

 

 

 

Paging Example 

위 그림에서 페이징의 동작 과정을 살펴보자. 논리적 주소는  n = 2, m = 4 인 상태이다. 

물리 메모리는 32byte , 페이지의 크기는 4byte 이므로 메모리에는 총 8개의 frame 이 존재한다.

 

논리적 주소 0 은 0000으로 p = 0, d = 0으로 변환되고, 테이블에서 0번 페이지는 5번 프레임에 대응한다.

따라서 실제 물리적 메모리 주소는 5 * 4(페이지크기) + 0(d) = 20이다.

 

논리적 주소 11은 1011으로 p = 2, d = 3으로 변환되고, 테이블에서 2번 페이지는 1번 프레임에 대응한다. 

따라서 실제 물리적 메모리 주소는 1 * 4(페이지 크기) + 3(d) = 7이다.

 

 

페이징 기법을 사용할 때, 외부 단편화는 거의 발생하지 않는다.

그러나 내부 단편화는 발생할 수 있다.

만약 페이지 하나의 크기가 2048 byte 일 때 프로세스의 크기가 72776byte 라면 35 페이지 + 1086 byte 로 변환될 수 있다.

하지만 프레임은 고정된 크기로 할당되기 때문에 실제로 할당되는 프레임 수는 36개이고, 마지막 1개의 프레임에는 926byte 의 내부 단편화가 발생하게 된다.

최악의 경우에는 단 1byte 때문에 하나의 프레임을 더 할당해야 할 수도 있다. 이 경우에는 2047byte 의 내부 단편화가 발생할 것이다.

 

그러나 평균적으로 발생하는 내부 단편화는 1 / 2 frame size로 낭비되는 공간이 매우 작으며, 최악의 경우에도 frame - 1 만큼의 낭비가 발생하므로 그리 큰 값은 아님을 알 수 있다.

또한 page size 가 작으면 내부 단편화는 작아지겠지만, paging table 크기는 커짐을 명심해야 한다.

 

 

Free Frames

프로세스가 실행을 요구하면, 몇 개의 페이지가 필요한지 조사하여 할당해야 한다.

즉 frame 의 free/allocated 여부를 표시하고, 할당되었다면 어느 프로세스의 어느 페이지에서 맵핑되었는지를 기록해야 한다.

이러한 프레임 테이블은 운영체제가 유지한다.

 

 

 

 

 

Implementation of Page Table

page table 을 메인 메모리에 유지해야 하므로, 물리 메모리에 접근하기 위해서 page table 에 접근하는 것은 결국 메모리 접근이 2번 필요한 것이다.

 

page-table base register (PBTR) 은 page table 의 시작 주소이며, page-table length register (PTLR) 은 page table 의 크기이다.

따라서 메모리 2회 접근 문제를 해결하기 위해서 Translation look-aside buffers (TLB) 를 사용한다. TLBs는 page table entry 용 캐시로, 메모리 접근에 드는 시간을 줄여준다.

 

 

 

TLB

TLB 는 소형 하드웨어 캐쉬로 key, value 로 구성되어 있다.

CPU 에서 논리 주소를 생성하면, 해당 페이지 번호가 TLB에 전달된다.

만약 페이지 번호가 발견되면 해당 프레임을 즉시 알 수 있고, 바로 메모리 접근이 가능하다.

 

만약 페이지 번호가 없으면(TLB 미스), 페이지 테이블을 접근하기 위해 메모리 참조가 이루어져야 하므로 메모리접근은 총 2번이다. 따라서 자주 쓰이는, 최근에 접근한 page number 을 TLB 에 저장한다.

 

TLB가 가득 차면, 교체될 page number 을 선택하는데, 중요 커널 코드 같은 몇몇 항목은 TLB 에 고정하기도 한다. 

 

 

Paging hardware with TLB

논리 주소의 page number 을 찾기 위해 TLB와 page table 에 동시에 접근하며, TLB 에서 찾으면 page table 의 탐색을 종료하고 바로 메모리에 접근 가능하다.

 

Effective Access Time

Hit ratio 는 TLB 에서 찾아질 확률이다. EAT 는 Hit ratio×Memory access time+(1−Hit ratio)×(2×Memory access time) 로 hit ratio 값이 클수록 시간이 줄어들며, 아주 작은 시간에 불과해 실제 메모리 접근 시간 만큼만 걸린다.

 

 

Memory Protection

각 page 에서 valid-invalid bit 를 통해 해당 page 가 프로세스의 유효한 page 인지 무효한 page 인지에 대한 정보를 알 수 있다.  

PTLR(Page Table Length Register) 은 page table 의 크기를 나타내기 위해 사용된다.

 

 

 

Shared Pages

페이징의 장점은 코드를 쉽게 공유 할 수 있다는 것이다.

재진입 코드(reentrant code)는 공유될 수 있는데, 이는 수행 동안 변하지 않는 읽기전용 코드이다.

공유 코드는 모든 프로세스의 논리 주소 공간에서 같은 위치에 있어야 한다.