CH07 메모리 관리 1b36c524aebc4550908d46538a87c73e.md

CH07.메모리 관리

메모리는 주소를 통해 접근하는 저장장치

• 주소(address)란?

  : 서로 다른 위치를 구분하기 위해 사용하는 일련의 숫자로 구성

1. 주소 바인딩

• 논리적 주소(logical address) or 가상 주소(virtual address) 란?

  : 프로그램이 실행을 위해 메모리에 적재되면 그 프로세스를 위한 독자적인 주소 공간이 생성 되는데 이를 말함

CPU는 이와 같이 프로세스마다 독립적으로 갖는 논리적 주소에 근거해 명령을 실행함

• 물리적 주소(physical address)

  : 물리적 메모리에 실제로 올라가는 위치

보통 물리적 메모리의 낮은 주소 영역에는 운영체제가 올라가고, 높은 주소 영역에는 사용자 프로세스들이 올라감

CPU가 기계어 명령을 수행하기 위해 논리적 주소를 통해 메모리 참조를 하게 되면 해당 논리적 주소가 물리적 메모리의 어느 위치에 매핑되는지 확인해야 함

⇒ 이렇게 프로세스의 논리적 주소를 물리적 메모리 주소로 연결시켜주는 작업을 주소바인딩 이라고 함

• 주소 바인딩 방식 (프로그램이 적재되는 물리적메모리의 주소가 결정되는 시기에 따라 분류)

1. 컴파일 타임 바인딩(compile time binding) 방식

: 물리적 메모리 주소가 프로그램을 컴파일할 때 결정됨

컴파일을 하는 시점에 해당 프로그램이 물리적 메모리의 몇 번지에 위치할 것인지를 결정함

프로그램이 절대주소로 적재된다는 뜻에서 주소 바인딩 방식 or 절대코드(absolute code)를 생성하는 바인딩 방식 이라고도 말함

• 단점

  : 프로그램이 올라가 있는 물리적 메모리의 위치를 변경하고 싶다면 컴파일을 다시 하는 수고가 필요. 즉, 비현실적이고 현대의 시분할 컴퓨팅 환경에서는 잘 사용하지 않는 기법

2. 로드 타임 바인딩(load time binding) 방식

: 프로그램의 실행이 시작될 때에 물리적 메모리 주소가 결정되는 주소 바인딩 방식

로더(loader)의 책임하에 물리적 메모리 주소가 부여되며 프로그램이 종료될 때까지 물리적 메모리상의 위치가 고정됨

• 로더란?

  : 사용자 프로그램을 메모리에 적재시키는 프로그램을 말함

이 바인딩 방식은 컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우에 가능한 주소 바인딩 방식

3. 실행시간 바인딩(execution time binding 또는 run time binding) 방식

: 프로그램이 실행을 시작한 후에도 그 프로그램이 위치한 물리적 메모리상의 주소가 변경될 수 있는 바인딩 방식. CPU가 주소를 참조할 때마다 해당 데이터가 물리적 메모리의 어느 위치에 존재하는지, 주소 매핑 테이블을 이용해 바인딩을 점검해야 함

또한 다른 방식들과 달리 실행시간 바인딩 방식이 가능하기 위해서는 기준 레지스터(base register)와 한계 레지스터(limit register)를 포함해 MMU(Memory Management Unit : 메모리 관리 유닛)라는 하드웨어적인 지원이 뒷받침되어야 함

• MMU는 논리적 주소를 물리적 주소로 매핑해주는 하드웨어 장치

• 기본적인 방식으로 주소 변환을 수행하는 MMU 기법(MMU scheme)

CPU가 특정 프로세스의 논리적 주소를 참조하려고 할 때 그 주소값에 기준 레지스터의 값을 더해 물리적 주소값을 얻어냄 이때 기준 레지스터는 재배치 레지스터(relocatation register)라고도 부르며 그 프로세스의 물리적 메모리 시작 주소를 가지고 있음

프로그램의 주소공간이 물리적 메모리의 한 장소에 연속적으로 적재되는 것으로 가정함. 따라서 그 프로그램이 적재되는 물리적 메모리상의 시작 주소만 알면 주소 변환을 쉽게 할 수 있음

재배치 레지스터에는 현재 CPU에서 수행중인 프로세스의 물리적 메모리 시작 주소가 저장되어 있음. CPU가 논리적 주소 123번지에 있는 내용을 요청할 경우 재배치 레지스터에 저장된 23000이라는 값에 이 주소를 더해 물리적 메모리 23123번지에 있는 내용을 참조하게 됨. 그러면 물리적 메모리 23123번지에서 CPU가 요청한 정보를 찾게 됨.

논리적 주소 123번지는 물리적 메모리의 시작 위치인 재배치 레지스터값으로부터 요청된 위치가 얼마나 떨어져 있는지를 나타내는 일종의 오프셋(offset)개념으로 생각할 수 있음.

프로세스는 자기 자신만의 고유한 주소 공간을 가지고 있으므로 동일한 주소값이라 하더라도 각 프로세스마다 서로 다른 내용을 담고 있게 됨. 따라서 CPU가 논리적 주소 100번지를 참조한다고 했을 때 현재 CPU가 수행되고 있는 프로세스가 무엇인지에 따라 이 100번지가 가리키는 내용은 상이해짐.

흔히 사용하는 다중 프로그래밍 환경에서 MMU 방식을 사용할 경우 CPU가 요청한 논리적 주소값+재배치 레지스터 안에있는 값 = 결과가 해당 프로세스의 주소 공간을 벗어나는 경우가 발생할 수 있음. 이렇게 되면 메모리 보안(memory protection)이 이루어지지 않아 시스템에 치명적인 결과를 초래할 수도 있음.

⇒ 운영체제는 이를 방지하기 위해 한계 레지스터(limit register)를 사용함.

• 한계 레지스터?

  : 프로세스가 자신의 주소 공간을 넘어서는 메모리 참조를 하려고 하는지 체크하는 용도로 사용되며, 현재 CPU에서 수행 중인 프로세스의 논리적 주소의 최댓값, 즉 그 프로세스의 크기를 담고 있음

2. 메모리 관리와 관련된 용어

1) 동적로딩(dynamic loading)

: 여러 프로그램이 동시에 메모리에 올라가서 수행되는 다중 프로그래밍(multi-programming) 환경에서 메모리 사용의 효율성을 높이기 위해 사용하는 기법 중 하나

• 프로세스가 시작될 때 그 프로세스의 주소 공간 전체를 메모리에 다 올려놓는 것이 아니라 메모리를 좀 더 효율적으로 사용하기 위해 해당 부분이 불릴 때 그 부분만을 메모리에 적재하는 방식을 사용함

실제로 프로그램의 코드 중 상당 부분은 오류 처리루틴과 같이 아주 특별한 경우에 가끔씩 사용되는 방어용 코드 → 메모리의 낭비가 초래됨

⇒ 이를 막아 메모리를 효율적으로 사용 !!

• 운영체제의 특별한 지원 없이 프로그램 자체에서 구현이 가능하며 운영체제가 라이브러리를 통해 지원할 수도 있음
• 라이브러리가 실행시점에 연결됨. 실행파일에 라이브러리 코드가 포함되지 않음.
• 실행파일의 라이브러리 호출 부분에 해당 라이브러리의 위치를 찾기 위한 스텁(stub)이라는 작은 코드를 둠
• 라이브러리 호출시 스텁을 통해 해당 라이브러리가 메모리에 이미 존재하는지 살펴보고 그럴 경우 그 주소의 메모리 위치에서 직접 참조하며, 그렇지 않을 경우 디스크에서 동적 라이브러리 파일을 찾아 메모리로 적재한 후 수행하게 됨

2) 동적연결

: 컴파일을 통해 생성된 목적 파일과 라이브러리 파일 사이의 연결을 프로그램의 실행 시점까지 지연시키는 기법

• 연결(linking)이란?

  : 프로그래머가 작성한 소스 코드를 컴파일하여 생성된 목적 파일(object file)과 이미 컴파일된 라이브러리 파일(library file)들을 묶어 하나의 실행파일을 생성하는 과정을 말함

↔ 정적연결(static linking)

: 프로그래머가 작성한 코드와 라이브러리 코드가 모두 합쳐져서 실행파일이 생성됨. 따라서 실행파일의 크기가 상대적으로 크며, 동일한 라이브러리를 각 프로세스가 개별적으로 메모리에 적재해야 하므로 물리적 메모리가 낭비되는 단점이 있음.

이는 비효율적이라 동적연결.

→ 메모리에 쓸데없이 똑같은게 너무 많이 올라가더라 !

많이 쓰는 라이브러리는 메모리에 하나만 올리자로 ...

3) 중첩(overlays)

: 프로세스의 주소 공간을 분할해 실제 필요한 부분만을 메모리에 적재하는 기법을 말함. (동적로딩과 개념적으로 유사)

• 엄밀히는, 초창기의 컴퓨터 시스템에서 물리적 메모리의 크기 제약으로 인해 하나의 프로세스조차도 메모리에 한꺼번에 올릴 수 없을 때, 프로세스의 주소 공간을 분할해서 당장 필요한 일부분을 메모리에 올려 실행하고 해당 부분에 대한 실행이 끝난 후에 나머지 부분을 올려 실행하는 기법을 뜻함.
• 운영체제의 지원 없이 프로그래머에 의해 구현되어야 했다 해서 수작업 중첩(manual overlays)이라고도 부름. 구현하는 것 상당히 복잡함
• 동적 로딩 vs 중첩
  • 중첩 : 단일 프로세스만을 메모리에 올려놓는 환경에서 메모리 용량보다 큰 프로세스를 실행하기 위한 어쩔 수 없는 선택
  • 동적로딩 : 메모리에 더 많은 프로세스를 동시에 올려놓고 실행하기 위한 용도

4) 스와핑(swapping)

: 메모리에 올라온 프로세스의 주소 공간 전체를 디스크의 스왑 영역에 일시적으로 내려놓는 것을 말함.

• 스왑 영역(swap area)란?

  : 백킹스토어(backing store)라고도 부르며, 디스크 내에 파일 시스템과는 별도로 존재하는 일정 영역을 말함

  • 프로세스가 수행중인 동안에만 디스크에 일시적으로 저장하는 공간이므로 저장 기간이 상대적으로 짧은 저장공간
  • 다수의 사용자 프로세스를 담을 수 있을 만큼 충분히 큰 저장공간이어야 하고 어느 정도의 접근 속도가 보장되어야 함

⚠️주의할 점 !

스와핑이라는 개념이 프로세스가 종료되어 그 주소 공간을 디스크로 내쫓는 것이 아니라, 특정한 이유로 수행 중인 프로세스의 주소 공간을 일시적으로 메모리에서 디스크로 내려놓는 것을 의미한다는 것

• 일어나는 작업의 방향에 따라
• 스왑 인(swap in) : 디스크에서 메모리로 올리는 작업
• 스왑 아웃(swap out) : 메모리에서 디스크로 내리는 작업

스와핑이 일어나는 과정

1. 스와퍼(swapper)라고 불리는 중기 스케쥴러(medium-term scheduler)에 의해 스왑아웃시킬 프로세스를 선정함

2. 스왑 아웃 대상으로 선정된 프로세스에 대해서는 현재 메모리에 올라가 있는 주소 공간의 내용을 통째로 디스크 스왑 영역에 스왑 아웃시키게 됨

• 스와핑의 가장 중요한 역할은 메모리에 존재하는 프로세스의 수를 조절하는 것임. 즉 다중 프로그래밍의 정도(degree of muliprogramming)를 조절 할 수 있음
• 너무 많은 프로그램이 메모리에 동시에 올라오게 되면 프로세스당 할당되는 메모리의 양이 지나치케 적어져 시스템 전체의 성능이 크게 떨어짐. 그래서 몇몇 프로그램을 통째로 디스크의 스왑 영역으로 내쫓음으로써 메모리에 남아 있는 프로그램들에게 적절한 메모리 공간을 보장함.
• 앞에서 본 컴파인 타임 바인딩 방식 & 로드 타임 바인딩 방식에서는 스왑 아웃된 프로세스가 다시 스왑 인될 때에는 원래 존재하던 메모리 위치로 다시 올라가야 함. but, 실행시간 바인딩 기법에서는 추후 빈 메모리 영역 아무 곳에나 프로세스를 올릴 수 있음

보통 디스크 내의 스왑 영역에 프로세스의 주소 공간이 순차적으로 저장되기 때문에, 스와핑에 소요되는 시간은 디스크의 탐색시간이나 회전지연시간보다는 디스크 섹터에서 실제 데이터를 읽고 쓰는 전송시간이 대부분을 차지함

• 탐색시간(seek time)이란 ?

  read/write 헤드를 데이터가 저장되어 있는 트랙 위치로 이동시키는데 소요되는 시간

• 회전지연시간(rotational latency)이란?

  read/write 헤드를 데이터가 위치하는 트랙으로 이동시킨 순간부터 원하는 섹터에 헤드가 다다를 때까지 소요되는 시간

• 전송시간(transfer time)이란?

  read/write 헤드가 찾은 데이터를 실제로 디스크로부터 사용자의 버퍼로 보내지는데 소요되는 시간

현재 물리적 메모리에 워드프로세서 프로그램이 올라가 있다고 가정. 이때 사용자가 웹 브라우저 프로그램을 사용하고자 하는데 이를 실행하기 위한 메모리 공간이 충분하지 않을 경우, 운영체제는 메모리 내에 이미 존재하는 워드프로세서에 할당된 메모리 공간을 통째로 빼앗아 디스크의 스왑영역으로 스왑 아웃시키고 그렇게 해서 생긴 여유 공간에 웹 브라우저 프로그램의 주소 공간을 스왑 인시킬 수 있게 됨.

3. 물리적 메모리의 할당 방식

물리적 메모리는 운영체제 상주 영역과 사용자 프로세스 영역으로 나뉘어 사용됨.

운영체제 상주 영역은 인터럽트 벡터와 함께 물리적 메모리의 낮은 주소 영역을 사용하며, 운영체제 커널이 이곳에 위치하게 됨.

사용자 프로세스 영역은 물리적 메모리의 높은 주소 영역을 사용하며 여러 사용자 프로세스들이 이곳에 적재되어 실행됨.

<요약>

사용자 프로세스 영역의 관리 방법 → 프로세스를 메모리에 올리는 방식에 따라

• 연속할당(contiguous allocation) 방식

  : 각각의 프로세스를 물리적 메모리의 연속적인 공간에 올리는 방식. 물리적 메모리를 다수의 분할로 나누어 하나의 분할에 하나의 프로세스가 적재되도록 함.

  물리적 메모리를 고정된 크기의 분할로 미리 나누어 놓는가 아닌가에 따라

  • 고정분할(fixed partition allocation) 방식

    : 물리적 메모리를 고정된 크기의 분할로 미리 나누어두는 방식

  • 가변분할(variable partition allocation) 방식

    : 분할을 미리 나누어놓지 않은 채 프로그램이 실행되고 종료되는 순서에 따라 분할을 관리하는 방식

• 불연속할당(noncontiguous allocation) 방식

  : 하나의 프로세스를 물리적 메모리의 여러 영역에 분산해 적재하는 방식

  • 페이징(paging) 기법 : 각 프로세스의 주소 공간을 동일한 크기의 페이지로 잘라서 메모리에 페이지 단위로 적재시키는 것
  • 세그먼테이션(segmentation) 기법 : 프로그램의 주소 공간을 코드, 데이터, 스택 등 의미 있는 단위인 세그먼트로 나누어 세그먼트 단위로 적재하는 것
  • 페이지드 세그먼테이션(paged segmentation) 기법 : 세그먼트 하나를 다수의 페이지로 구성하는 것

1-1) 연속할당 방식

: 프로세스를 메모리에 올릴 때 그 주소 공간을 여러 개로 분할하지 않고 물리적 메모리의 한 곳에서 연속적으로 적재하는 방식

1-2) 고정분할 방식

: 물리적 메모리를 주어진 개수만큼의 영구적인 분할(partition)로 나누어두고 각 분할에 하나의 프로세스를 적재해 실행시킬 수 있게 함. 이때 분할의 크기는 모두 동일하게 할 수도 있고 서로 다르게 할 수도 있음. → 프로그램 수가 고정되어 있어 가변분할 방식에 비해 융통성 떨어짐

• 외부조각과 내부조각이 발생할 수 있음

• 외부조각(external fragmentation)이란?

  : 프로그램의 크기보다 분할의 크기가 작은 경우 해당 분할이 비어 있는데도 불구하고 프로그램을 적재하지 못하기 때문에 발생하는 메모리 공간

• 내부조각 (internal fragmentation)

  : 프로그램의 크기보다 분할의 크기가 큰 경우 해당 분할에 프로그램을 적재하고 남는 메모리 공간을 뜻함. 특정 프로그램에 이미 배당된 공간으로 볼 수 있으므로 내부조각에 수용할 수 있는 충분히 작은 크기의 프로그램이 있다 해도 공간을 활용할 수 없어 메모리가 낭비됨.

1-3) 가변분할 방식

: 메모리에 적재되는 프로그램의 크기에 따라 분할의 크기, 개수가 동적으로 변하는 방식을 말함.

프로그램의 크기를 고려해서 메모리를 할당하고 이를 기술적으로 관리할 수 있는 기법을 필요로 함.

• 분할의 크기를 프로그램의 크기보다 일부러 크게 할당하지 않기 때문에 내부 조각은 발생하지 않음.
• but, 이미 메모리에 존재하는 프로그램이 종료될 경우 중간에 빈 공간이 발생하게 되며, 이 공간이 새롭게 시작되는 프로그램의 크기보다 작을 경우 외부조각이 발생할 가능성이 있음.

동적 메모리 할당 문제(dynamic storage-allocation problem) : 주소 공간의 크기가 n인 프로세스를 메모리에 올릴 때 물리적 메모리 내 가용 공간 중 어떤 위치에 올릴 것인지 결정하는 문제

• 가용 공간이란?

  : 사용되지 않은 메모리 공간으로서 메모리 내의 여러 곳에 산발적으로 존재할 수 있음

  운영체제는 이미 사용중인 메모리 공간과 사용하고 있지 않은 가용 공간에 대한 정보를 각각 유지하고 있음

동적 메모리 할당 문제를 해결하는 대표적인 방법

1. 크기가 n 이상인 가용 공간 중 가장 먼저 찾아지는 곳에 프로세스를 할당하는 최초적합(first-fit) 방법

• 메모리에 존재하는 가용 공간을 차례대로 살펴보면서 가용 공간이 프로그램 크기보다 작으면 건너뛰고, 그렇지 않은 가용 공간이 최초로 발견되면 그 공간에 프로그램을 올림
• 시간적인 측면에서 효율적

2. 크기가 n 이상인 가장 작은 가용 공간을 찾아 그곳에 새로운 프로그램을 할당하는 최적적합(best-fit) 방법

• 가용 공간들의 리스트가 크기순으로 정렬되어 있지 않은 경우에 모든 가용 공간 리스트를 탐색해야 하므로 시간적 오버헤드가 발생하고 다수의 매우 작은 가용 공간들이 생성될 수 있다는 단점.
• but, 공간적인 측면에서 효율적

3. 가용 공간 중에서 가장 크기가 큰 곳에 새로운 프로그램을 할당하는 최악적합(worst-fit) 방법

• 모든 가용 공간 리스트를 탐색해야 하므로 시간적 오버헤드가 발생
• 상대적으로 더 큰 프로그램을 담을 수 있는 가용 공간을 빨리 소진한다는 문제점

실제 시스템에서 실함한 결과 !

최초적합 & 최적적합 방식 > 최악적합 방식 (속도와 공간 이용률 측면)

가변분할 방식에서 발생하는 외부조각 문제를 해결하기 위한 방법 : 컴팩션(compaction)

• 물리적 메모리 중에서 프로세스에 의해 사용 중인 메모리 영역을 한쪽으로 몰고 가용 공간들을 다른 한쪽으로 모아서 하나의 큰 가용 공간을 만드는 방법
• 현재 수행 중인 프로세스의 메모리상의 위치를 상당 부분 이동시켜야 하므로 비용이 매우 많이 드는 작업
• 효율적인 컴팩션을 수행하는 방법? 이론적으로 매우 복잡한 문제
• 효율적인 메모리 공간의 사용을 위해 수행 중인 프로세스의 물리적 메모리 위치를 옮겨야 하므로 프로그램의 실행 도중에 프로세스의 주소가 동적으로 바뀔 수 있는 실행시간 바인딩 방식이 지원되는 환경에서만 수행될 수 있음.

2) 불연속할당 기법

: 하나의 프로세스가 물리적 메모리의 여러 위치에 분산되어 올라갈 수 있는 메모리 할당 기법을 말함

• 페이징(paging) 기법 : 각 프로세스의 주소 공간을 동일한 크기의 페이지로 잘라서 메모리에 페이지 단위로 적재시키는 것
• 세그먼테이션(segmentation) 기법 : 프로그램의 주소 공간을 코드, 데이터, 스택 등 의미 있는 단위인 세그먼트로 나누어 세그먼트 단위로 적재하는 것
• 페이지드 세그먼테이션(paged segmentation) 기법 : 세그먼트 하나를 다수의 페이지로 구성하는 것

4. 페이징 기법

(=프로세스를 일정한 단위로 잘라서 사용하자는 방식)

: 프로세스의 주소 공간을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장하는 방식을 말함.

• 각 프로세스의 주소 공간 전체를 물리적 메모리에 한꺼번에 올릴 필요 x, 일부는 백킹스토어에, 일부는 물리적 메모리에 혼재시키는 것이 가능함.
• 물리적 메모리를 페이지와 동일한 크기의 프레임(frame)으로 미리 나누어둠
• 메모리에 올리는 단위가 동일한 크기의 페이지 단위이므로, 메모리를 같은 크기로 미리 분할해두더라도 빈 프레임이 있으면 어떤 위치이든 사용될 수 있기 때문
• 동적 메모리 할당 문제가 발생하지 않음

주소 변환 절차가 다소 복잡. 하나의 프로세스라 하더라도 페이지 단위로 물리적 메모리에 올리는 위치가 상이하므로, 논리적 주소를 물리적 주소로 변환하는 작업이 페이지 단위로 이루어져야 하기 때문.

• 특정 프로세스의 몇 번째 페이지가 물리적 메모리의 몇 번째 프레임에 들어 있다는 페이지별 주소 변환 정보로써 주소 변환을 위한 페이지 테이블(page table)을 가지며, 이 테이블은 프로세스가 가질 수 있는 페이지의 개수만큼 주소 변환 엔트리를 가지고 있게 됨
• 프로세스의 주소 공간과 물리적 메모리가 모두 같은 크기의 페이지 단위로 나누어지기 때문에 빈 공간은 어느 곳이든 활용 할 수 있음. → 외부조각 문제 발생X
• BUT, 프로그램의 크기가 항상 페이지 크기의 배수가 된다는 보장이 없기 때문에 프로세스의 주소 공간 중 마지막에 위치한 페이지에서는 내부조각이 발생할 가능성이 있음.

1) 주소 변환 기법

: CPU가 사용하는 논리적 주소를 페이지 번호(p)와 페이지 오프셋(d)으로 나누어 주소 변환(address translation)에 사용함.

• 페이지 번호 : 각 페이지별 주소 변환 정보를 담고 있는 페이지 테이블 접근 시 인덱스로 사용되고, 해당 인덱스의 항목(entry)에는 그 페이지의 물리적 메모리상의 기준 주소(base address), 즉 시작 위치가 저장됨
• 따라서, 특정 프로세스의 p번째 페이지가 위치한 물리적 메모리의 시작 위치를 알고 싶다면 해당 프로세스의 페이지 테이블에서 p번째 항목을 찾아보면 됨.
• 페이지 오프셋 : 하나의 페이지 내에서의 변위(displacement)를 알려준다 - 위치 변화함에 따라 차지하는 크기라고 생각하면,,
• 따라서, 기준 주소값에 변위를 더함으로써 요청된 논리적 주소에 대응하는 물리적 주소를 얻을 수 있음

2) 페이지 테이블의 구현

페이지 테이블은 페이징 기법에서 주소 변환을 하기 위한 자료구조로, 물리적 메모리에 위치하게 됨. 현재 CPU에서 실행중인 프로세스의 페이지 테이블에 접근하기 위해 운영체제는 2개의 레지스터를 사용하는데 아래와 같다.

1. 페이지 테이블 기준 레지스터(page-table base register)

   : 메모리 내에서의 페이지 테이블의 시작 위치를 가리킴.

2. 페이지 테이블 길이 레지스터(page-table length register)

   : 페이지 테이블의 크기를 보관함.

• 페이징 기법에서의 메모리 접근 연산은 주소 변환을 위해 페이지 테이블에 접근 하는 것과, 변환된 주소에서 실제 데이터에 접근하는 것, 이렇게 두 번의 메모리 접근을 필요로 함.

→ 메모리에 한 번 접근하기 위해서 매번 메모리에 두 번 접근해야하는 오버헤드가 뒤따름.

• 이러한 페이지 테이블 접근 오버헤드를 줄이고 메모리의 접근 속도를 향상시키기 위해 TLB(Translation Look-aside Buffer)라고 불리는 고속의 주소 변환용 하드웨어 캐시가 사용 되기도 함.
• 메모리에 비해 TLB로 사용 되는 하드웨어 가격 비쌈💸 → 빈번히 참조되는 페이지에 대한 주소 변환 정보만을 담음
• 요청된 페이지 번호가 TLB에 존재한다면 대응하는 물리적 메모리의 프레임 번호를 바로 얻을 수 있지만, 존재하지 않는 경우에는 메인 메모리에 있는 페이지 테이블로부터 프레임 번호를 알아내야 함.
• 주소 변환 정보는 프로세스별로 다 다르기 때문에 문맥교환 시 이전 프로세스의 주소 변환 정보를 가지고 있던 TLB 내용은 모두 지워버려야 함.

한편 페이지 테이블과 TLB에 저장되어 있는 정보는 그 구조가 조금 다름

• 페이지 테이블에는 하나의 프로세스를 구성하는 모든 페이지에 한 정보가 페이지 번호에 따라 순차적으로 들어 있음. 반면 TLB는 모든 페이지에 대한 주소 변환 정보를 가지고 있지 않아 페이지 번호와 이에 대응하는 프레임 번호가 쌍으로 저장되어야 함.

TLB를 통한 주소 변환을 위해서는 해당 페이지에 대한 주소 변환 정보가 TLB에 있는지 확인하기 위해 TLB의 모든 항목(entry)을 다 찾아봐야 하는 오버헤드가 발생함.

• 이 오버헤드를 줄이기 위해 병렬탐색이 가능한 연관 레지스터(associative register)를 사용함.

• 병렬탐색 기능이란?

  : TLB 내의 모든 항목을 동시에 탐색할 수 있는 기능

연관 레지스터를 사용할 때 평균적인 메모리 접근시간(Effective Access Time : EAT)

• 메모리에 접근하는 시간을 1
• 연관 레지스터에 접근하는 시간을 ε

→ ε은 1보다 충분히 작은 값이 될 것

• 요청된 페이지에 대한 주소 변환 정보가 연관 레지스터에 존재할 확률을 α라고 하면 평균적인 메모리 접근시간 EAT는 다음과 같다.

( 1+ε )α항 : 요청된 페이지의 주소 변환 정보가 TLB에 존재하는 경우를 뜻함.

• 이 경우 TLB로부터 직접 물리적 메모리 주소를 얻는 데 ε시간이 소요되고, 실제 원하는 데이터에 접근하기 위해 한 번의 메모리 접근이 필요하므로 1+ε 의 시간이 소요됨.
• 여기에 TLB에서 찾아지는 비율인 α를 곱하면 첫 번째 항을 얻을 수 있음.

( 2+ε )( 1-α )는 요청된 페이지의 주소 변환 정보가 TLB에 존재하지 않는 경우를 뜻함.

• 요청된 페이지에 대한 주소 변환 정보가 TLB에 있는지 확인하는 시간 ε이 먼저 소요되고, 그런 다음 페이지 테이블에 접근하는 시간과 실제 원하는 데이터에 접근하는 시간 등 두 번의 메모리 접근이 필요하게 됨.
• 따라서 2+ε의 시간이 소요되며, 여기에 TLB에서 찾지 못하는 비율인 1-α를 곱하여 두 번째 항인 ( 2+ε )( 1-α )가 얻어지게 됨.

⇒ TLB가 사용되는 시스템에서의 평균 메모리 접근시간은 위의 식을 정리하면 2 + ε - α가 됨

3) 계층적 페이징

현대의 컴퓨터는 주소 공간이 매우 큰 프로그램을 지원함.

ex) 32비트 주소 체계를 사용하는 컴퓨터에서는 $2^{32}$byte(=4GB)의 주소 공간을 갖는 프로그램을 지원할 수 있음. 이러한 환경에서 페이지 크기가 4KB라면 4GB/4KB, 즉 1M개의 페이지 테이블 항목이 필요하게 됨. 각 페이지 테이블 항목이 4byte씩을 필요로 한다면 한 프로세스당 페이지 테이블을 위해 1M X 4byte 크기의 메모리 공간이 필요하게 됨. 수행 중인 프로세스의 수가 증가함에 따라 전체 메모리의 상당 부분이 주소 변환을 위한 페이지 테이블에 할애되어 실제로 사용 가능한 메모리 공간이 크게 줄어들게 됨.

한편, 대부분의 프로그램은 4GB의 주소 공간 중 지극히 일부만 사용함

→ 페이지 테이블에 사용되는 메모리 공간의 낭비를 줄이기 위해 2단계 페이징 기법을 사용함.

• 크기

  $2^{10}$=K, $2^{20}$=M, $2^{30}$=G로 정의됨

2단계 페이징 기법 → 주소 변환을 위해 외부페이지 테이블과 내부 페이지 테이블의 두 단계에 걸친 페이지 테이블을 사용함

• 사용되지 않는 주소 공간에 대해서는 외부 페이지 테이블의 항목을 NULL로 설정하며
• 이에 대응하는 내부 페이지 테이블을 생성하지 않는 것

⇒ 1단계 페이징 기법에 비해서 메모리 낭비를 크게 줄여 공간적인 이득을 볼 수 있음

BUT! 주소 변환을 위해 접근해야 하는 페이지 테이블의 수가 증가하므로 시간적인 손해가 뒤따르게 됨

• 프로세스의 논리적 주소를 두 종류의 페이지 번호 ($P_1$, $P_2$) 와 페이지 오프셋(d)으로 구분
  • $P_1$은 외부 페이지 테이블의 인덱스
  • $P_2$는 내부 페이지 테이블의 인덱스
  • 논리적 주소를 이와 같은 세 부분으로 나누어<$P_1$, $P_2$, d>의 형태로 표시하면,
    1. 먼저 외부 페이지 테이블로부터 $P_1$만큼 떨어진 위치에서 내부 페이지 테이블의 주소를 얻게 됨
    2. 내부 페이지 테이블로부터 $P_2$만큼 떨어진 위치에서 요청된 페이지가 존재하는 프레임의 위치를 얻게 됨
    3. 해당 프레임으로부터 d만큼 떨어진 곳에서 원하는 정보에 접근할 수 있게 됨.

Q. 앞선 32비트 주소 체계를 갖는 시스템과 같은 가정에서 32비트의 논리적 주소 중 페이지 번호와 페이지 오프셋을 위해 각각 몇 비트씩을 할당해야 하는지 생각해보자.

A. 페이지의 크기가 4KB(=2$^{12}$byte)이므로 하나의 페이지 내에서의 바이트 오프셋을 결정하기 위해 12비트가 필요함. 따라서 총 32비트 중에서 최하위 12비트가 오프셋 d로 사용됨

Q. 두 번째 페이지 번호인 $P_2$를 위해 몇 비트가 사용되는지 생각해보자.

★ 주의 ) 2단계 페이징 기법에서는 내부 페이지 테이블 자체를 하나의 프레임에 보관하게 된다는 점

즉 4KB 페이지를 사용하는 이 예제의 경우 내부 페이지 테이블의 크기 역시 4KB가 됨.

페이지 테이블 항목의 크기가 4bytte이므로 내부 페이지 테이블은 4KB/4byte, 즉 1K(=$2^{10}$)개의 항목을 가지게 됨

A. 따라서 내부 페이지 테이블의 인덱스로 사용되는 $P_2$에 10비트가 할당되어야 함.

• 프로세스의 주소 공간이 커질수록 페이지 테이블의 크기도 커지므로 주소 변환을 위한 메모리 공간 낭비 역시 더 심각해지게 됨. 따라서 3, 4단계에 이르는 다단계 페이지 테이블이 필요하게 됨. 전에 언급했다시피 이는 접근시간이 크게 늘어나는 문제가 발생할 수 있음.
• 이러한 메모리 접근에 의한 시간적인 오버헤드를 줄이기 위해서는 TLB가 효과적

4) 역페이지 테이블

페이지 테이블로 인한 메모리 공간의 낭비가 심한 이유는 모든 프로세스의 모든 페이지에 대핸 페이지 테이블 항목을 다 구성해야 하기 때문

→ 해결방안: 역테이지 테이블(inverted page table) 기법

: 물리적 메모리의 페이지 프레임 하나당 페이지 테이블에 하나씩의 항목을 두는 방식

• 논리적 주소에 대해 페이지 테이블을 만드는 것이 아니라, 물리적 주소에 대해 페이지 테이블을 만드는 것

• 즉, 각 프로세스마다 페이지 테이블을 두지 않고, 시스템 전체(system-wide)에 페이지 테이블을 하나만 두는 방법을 말함

• 페이지 테이블의 각 항목은 어느 프로세스의 어느 페이지가 이 프레임에 저장되었는지의 정보를 보관하고 있음

• 즉 페이지 테이블의 각 항목은 프로세스 번호(pid)와 그 프로세스 내의 논리적 페이지 번호(p)를 담고 있게 됨

• 주소 변환 작업이 논리적 주소로부터 물리적 주소를 얻어내는 것임에 비해 역페이지 테이블은 물리적 주소로부터 논리적 주소를 얻기 수월한 구조로 되어 있음

• 따라서 역페이지 테이블에서의 주소 변환은 다소 비효율적

• 왜 ? 그 주소를 담은 페이지가 물리적 메모리에 존재하는지 여부를 판단하기 위해 페이지 테이블 전체를 다 탐색해야 하는 어려움이 있는 것

⇒ 상당한 시간 요구. 때문에 일반적으로 메모리에 유지하는 대신 연관 레지스터(associative register)에 보관해 테이블 전체 항목에 대한 병렬탐색(parallel search)을 가능하게 함으로써 시간적 효율성을 꾀함.

5) 공유 페이지

• 공유 코드(shared code)?

  : 메모리 공간의 효율적인 사용을 위해 여러 프로세스에 의해 공통으로 사용될 수 있도록 작성된 코드, 읽기 전용의 특성을 가짐.

  ( =재진입 가능 코드(re-entrant code) or 순수 코드(pure code) )

• 공유 페이지(shared page)?

  : 공유 코드를 담고 있는 페이지를 말함.

  물리적 메모리에 하나만 적재되어 메모리를 효율적으로 사용할 수 있음

• 모든 프로세스의 논리적 주소 공간에서 동일한 위치에 존재해야하는 제약점. 즉 공유 페이지는 그 페이지를 공유하는 모든 프로세스의 주소 공간에서 동일한 페이지 번호를 가져야 함.

• ↔ 사유 페이지(private page)?

  : 프로세스들이 공유하지 않고 프로세스별로 독자적으로 사용하는 페이지

  해당 프로세스의 논리적 주소 공간 중 어떠한 위치에 있어도 무방함

문서 편집기 프로그램의 코드가 코드1, 코드2, 코드3의 3페이지로 구성되고, 이 페이지들이 프로세스 $P_1$, $P_2$, $P_3$에 의해 공유된다면 코드1,코드2, 코드3 페이지는 세 프로세스의 주소 공간 내에서 동일한 위치에 존재해야 하며, 물리적 메모리에는 하나씩의 코드만이 올라가게 됨

반명 사유 페이지인 데이터1, 데이터2, 데이터3는 각 프로세스의 주소 공간 내의 어느 위치에 존재해도 상관없으며 프로세스마다 독립적으로 사용하게 됨

6) 메모리 보호

페이지 테이블의 각 항목에는 주소 변환 정보뿐만이 아니라 메모리 보호를 위한 **보호비트(protection bit)와 유효-무효 비트(valid-invalid bit)**를 두고 있음.

• 보호비트?

  : 각 페이지에 대한 접근 권한의 내용을 담고 있음

  • 한 프로세스의 주소 공간은 다른 프로세스에 의해 접근될 수 없으므로 '누구'에 해당하는 접근 권한을 설정할 필요가 없음
  • 각 페이지에 대해 '어떠한' 접근을 허용하는지의 정보가 보호비트에 저장됨
  • 즉, 각페이지에 대해 읽기-쓰기/읽기전용 등의 접근 권한을 설정하는 데에 사용됨

• 유효-무효 비트?

  : 해당 페이지의 내용이 유효한지에 대한 내용을 담고 있음

  • 유효 세팅 → 해당 메모리 프레임에 그 페이지간 존재함을 뜻함
  • 무효 세팅 → 프로세스가 그 주소 부분을 사용하지 않거나, 해당 페이지가 물리적 메모리에 올라와 있지 않고 백킹스토어에 존재해 해당 메모리 프레임에 유효한 접근 권한이 없다는 의미

5. 세그먼테이션

: 프로세스의 주소공간을 의미 단위의 세그먼트(segment)로 나누어 물리적 메모리에 올리는 기법

• 하나의 프로세스를 구성하는 주소 공간은 일반적으로 코드, 데이터, 스택 등의 의미 있는 단위들로 구성됨
• 세그먼트도 이와 같이 주소 공간을 기능 단위 or 의미 단위로 나눈 것을 뜻함
• 보통은 코드, 데이터, 스택 등의 기능 단위로 세그먼트를 정의함. 많게는 프로그램을 구성하는 함수 하나하나를 각각 세그먼트로 정의할 수도 있음 → 의미있는 논리적인 단위(logical unit)로 나눈 것이기 때문에 크기가 균일하지 않음
• 프로세스의 주소 공간이 통째로 메모리에 적재되는 것이 아니라 나누어져 각각 메모리에 적재된다는 면에서 페이징과 유사함. But, 프로그램을 의미 단위의 세그먼트로 나누어 관리하므로, 크기가 균일하지 않은 세그먼트들을 메모리에 적재하는 부가적인 관리 오버헤드가 뒤따르게 됨
• 논리적 주소가 <세그먼트 번호, 오프셋>으로 나뉘어 사용됨.
  • 세그먼트 번호 : 해당 논리적 주소가 프로세스 주소 공간 내에서 몇 번째 세그먼트에 속하는지 나타냄
  • 오프셋 : 그 세그먼트 내에서 얼마만큼 떨어져 있는지에 대한 정보를 나타냄
• 주소 변환을 위해 세그먼트 테이블을 사용함. 이때 세그먼트 테이블의 각 항목은 기준점(base)과 한게점(limit)을 가지고 있음
  • 기준점 : 물리적 메모리에서 그 세그먼트의 시작 위치를 나타냄
  • 한계점 : 그 세그먼트의 길이를 나타냄
  • 페이징 기법에서는 모든 페이지의 길이가 동일하므로 페이지 테이블의 항목에 기준점이라 할 수 있는 페이지 프레임 위치만 유지하고 있으면 됨. But, 세그먼테이션 기법에서는 세그먼트의 길이가 균일하지 않으므로 세그먼트의 위치 정보뿐 아니라 길이 정보를 함꼐 보관하고 있는 것
• 주소 변환시 세그먼트 테이블 기준 레지스터(Segment-Table Base Register:STBR)와 세그먼트 테이블 길이 레지스터(Segment-Table Length Register: STLR)를 사용함
  • 세그먼트 테이블 기준 레지스터 : 현재 CPU에서 실행 중인 프로세스의 세그먼트 테이블이 메모리의 어느 위치에 있는지 그 시작 주소를 담고 있음
  • 세그먼트 테이블 길이 레지스터 : 그 프로세스의 주소 공간이 총 몇 개의 세그먼트로 구성되는지, 즉 세그먼트 개수를 나타냄

• 논리적 주소 → 물리적 주소로 변환 하기 전에 확인해야하는 것

  • 요청된 세그먼트 번호가 STLR에 저장된 값보다 작은 값인지 → 예외상황을 발생시켜 메모리 접근을 봉쇄해야함

  • 논리적 주소의 오프셋값이 그 세그먼트의 길이보다 작은 값인가

    • 해당 항목에 있는 한계점과 요청된 논리적 주소의 오프셋값을 비교해 확인함

    → → 예외상황을 발생시켜 메모리 접근을 봉쇄해야함

• 페이징 기법과 마찬가지로 세그먼트 테이블의 각 항목에 보호비트와 유효비트를 둠

• 또한, 공유 세그먼트 개념도 지원함

  

• 세그먼트는 의미 단위로 나누어져 있기 때문에 공유와 보안의 측면에서 페이징 기법에 비해 훨씬 효과적

  • 주소 공간의 일부를 공유하거나 특정 주소 공간에 읽기전용 등의 접근 권한 제어를 하고자 할 경우, 이는 어떤 의미 단위로 이루어지지 단순히 크기 단위로 수행되지 않기 때문
  • 예) 페이징 기법에서 동일한 크기로 주소 공간을 나누다 보면 공유하려는 코드와 사유 데이터 영역이 동일 페이지에 공존하는 경우가 발생할 수 있음
  • but, 세그먼테이션 기법에서는 이러한 현상 발생X

• 세그먼테이션 기법에서는 프로그램을 의미 단위로 나누기 때문에 세그먼트의 길이가 균일하지 않음 → 물리적 메모리 관리에서 외부조각이 발생

  • 세그먼트를 가용공간에 할당하는 방식
    • 최초적합(first fir)방식 : 해당 세그먼트 크기보다 크거나 같은 첫 번째 가용 공간에 할당하는 방식
    • 최적적합(best fit)방식 : 세그먼트의 크기보다 크거나 같은 가용 공간 중 가장 작은 공간에 할당하는 방식

6. 페이지드 세그먼테이션(paged segmentation) 기법

: 페이징, 세그먼테이션 기법의 장점만을 취하는 주소 변환 기법

• 세그먼테이션 기법과 마찬가지로 프로그램을 의미 단위의 세그먼트로 나눔. 단, 세그먼트가 임의의 길이를 가질 수 있는 것이 아니라 반드시 동일한 크기 페이지들의 집합으로 구성되어야 함
• 단 세그먼트가 임의의 길이를 가질 수 있는 것이 아니라 반드시 동일한 크기 페이지들의 집합으로 구성되어야 함
• 물리적 메모리에 적재하는 단위는 페이지 단위로 함

⇒ 하나의 세그먼트 크기를 페이지 크기의 배수가 되도록 함으로써 세그먼테이션 기법에서 발생하는 외부조각의 문제를 해결하며, 동시에 세그먼트 단위로 프로세스 간의 공유나 프로세스 내의 접근 권한 보호가 이루어지도록 함으로써 페이징 기법의 약점을 해소함

• 주소 변환을 위해 외부의 세그먼트 테이블과 내부의 페이지 테이블을 이용함 → 2단계 페이지 테이블과 유사한 구조
• <세그먼트 번호, 오프셋>으로 구성된 논리적 주소를 물리적 주소로 변환하는 과정
  • 논리적 주소의 상위 비트인 세그먼트 번호를 통해 세그먼트 테이블의 해당 항목(세그먼트 길이와 그 세그먼트의 페이지 테이블 시작 주소 들어있음)에 접근함
  • 세그먼트 길이를 넘어서는 메모리 접근 시도인지 여부를 체크하기 위해 먼저 세그먼트 길이값과 논리적 주소 중 하위 비트인 오프셋값을 비교함
  • 오프셋이 더 크다면 유효하지 않은 위치에 대한 접근 시도이므로 트랩을 발생시킴
  • 그렇지 않다면 오프셋값을 다시 상위, 하위 비트로 나누어
    • 상위 비트는 그 세그먼트 내에서의 페이지 번호로 사용
    • 하위 비트는 페이지 내에서의 변위로 사용함
  • 세그먼트 테이블의 항목을 통해 해당 세그먼트를 위한 페이지 테이블의 시작 위치를 얻었으므로 그 위치에서 페이지 번호만큼 떨어진 페이지 테이블 항목으로부터 물리적 메모리의 페이지 프레임 위치를 얻게 됨.
  • 이 위치에서 오프셋의 하위 비트값인 페이지 내 변위만큼 떨어진 곳이 바로 원하는 물리적 메모리 주소가 되는 것