주소를 통해 접근하는 매체 : 메모리 -> 메모리에는 주소가 매겨진다.

주소는 두가지로 나눌 수 있다.
프로그램이 실행되면 독자적인 주소공간이 형성된다고 앞에서 공부했다. 프로그램마다 가지고 있는 주소가 논리 주소이며 가상주소라고 부른다.
논리적인 주소
프로그램이 시작되면 0번지 부터 시작되는 논리적인 주소를 가진다.

물리적인 주소
프로그램의 실제적인 주소다.
물리적인 메모리 안에 아래에는 커널이 올라가있고, 상위주소엔 여러 프로그램들이 섞여 올라가있다. 프로그램마다 0번지 부터 시작하는 독자적인 주소가 있지만 실행되려면 물리적인 주소에 올라가야 하고 이러기 위해선 주소가 변해야 한다.
따라서 이러한 주소를 결정하는 것을 주소 바인딩이라고 한다.
그렇다면 이 주소는 언제 결정되는가? (논리 -> 물리)

주소에 관련해 용어가 하나 더 있는데 Symbolic Address이다.
프로그래밍을 할 때 메모리 몇 번지에 변수를 저장하라고 하지 않고 변수에 어떤걸 저장하라고 표기한다.
함수를 호출할 땐 몇번지로 jump 해라 하지 않고 그 함수 이름으로 호출한다.
그래서 프로그래머 입장에선 주소를 사용하지 않고 symbol을 사용한다.

프로그램은 주소를 사용하나 프로그래머는 symbol을 사용

컴파일이 되면 숫자로 된 주소(논리 주소)로 만들어짐 -> 실행 -> 물리 주소로 변환

언제 이루어지나?

크게 세가지 시점으로 나눌 수 있다.

Compile time binding

컴파일되는 시점에 바인딩 되는 것
컴파일 시점에 이미 물리적인 주소가 정해져야 하기 때문에 논리적인 주소가 곧 물리적인 주소가 된다.
따라서 항상 논리적인 주소로 할당된 주소로 물리적 주소를 올려야한다. 물리적주소에 다른 주소는 많이 비어있어도 항상 0번지 부터 올려야한다.
따라서 굉장히 비효율적이고 현대의 컴퓨터 시스템에선 이 방법을 사용하지 않는다.
하지만 예전에 프로그램을 하나만 실행하던 때에는 이 방법을 사용하기도 했다.

논리주소가 fix 되기 때문에 컴파일러는 absolute code를 생성한다고 한다. 이 주소를 바꾸고 싶다면 compile을 다시 해야한다.

Load time binding

실행이 시작될 때 주소 변환이 이루어지는 것
프로그램이 시작돼서 메모리에 올라갈 때 물리적인 주소가 결정된다.
따라서 컴파일 타임에는 논리적인 주소만 결정되어있고 실행될 때 물리적인 주소에 비어있는 곳을 확인하고 그 위치에 올린다.
위의 그림에선 500번지 부터 비어있네 ? 여기 올리자 !

컴파일러가 재배치 가능한 코드(relocateable code)를 생성한 경우에 가능하다.

Execution time binding (= Run time binding

프로그램이 시작된 이후에도 물리적인 주소가 바뀔 수 있는 것
실행시에 주소가 결정되는 것은 load time binding과 똑같다. 하지만 이 주소가 실행중 바뀔 수 있다.
논리 주소 0번지가 물리적인 주소 300번지에 올라가 있는데 실행중에 300번지에 있는 내용이 700번지로 이동할 수 있다. 실행하다가 메모리에서 쫓겨날 수도 있고, 다시 돌아왔을 때 비어있는 곳으로 가다보니 바뀔 수 있는 것이다.

주소 변환을 그때그때 해야되므로 하드웨어적인 지원이 필요하다. MMU라는 하드웨어가 있어 그때그때 주소 변환을 해줘야한다.

소스코드
Add A,B A위치의 값과 B위치의 값을 더해 A위치에 저장
Jump C C위치로 jump 해라

컴파일 되어 실행파일로 바뀌면 A,B로 불렸던 변수들이 모두 주소로 변한 것을 볼 수 있다.

그래서 각각의 문장들이 메모리의 0,10,20 ... 번지로 표현된다.
논리적인 주소가 정해지는 시점이 세가지였다.

그러면 CPU가 바라보는 주소는 ? CPU는 하드웨어이기 때문에 물리주소를 바라볼 것 같지만 논리적 주소를 바라본다.
이렇게 될 수 밖에 없는 이유는 위의 그림을 보면 나온다. 프로그램을 컴파일해서 실행파일로 만들게 되면 각각의 instruction을 CPU가 실행하려면 메모리 20번지에 있는 내용과 30번지에 있는 내용을 읽어 더하는 연산을 해야한다. 그런데 여기에 있는 20,30은 논리 주소이다. 실행돼서 메모리에 올라가면 instruction에 있는 주소들은 물리 주소로 변하지 않는다. 그래서 메모리에 올라갈 때 시작위치는 바뀌지만 코드상의 주소는 논리적 주소로 남아있을 수 밖에 없다. 그래서 instruction을 실행하려면 20,30번지의 데이터를 읽어와야하는데 이게 논리적 주소니까 CPU는 논리적 주소를 바라볼 수 밖에 없다.

MMU

주소 변환을 지원해주는 하드웨어이다.
OS의 모듈이나 SW가 아니고 하드웨어이다.
위에서 본 것은 프로그램을 통째로 옮기는 경우이다. 하지만 현대에서는 필요한 부분만 메모리에 올려 코드가 조각조각난다.

Register 두개로 주소 변환을 하게 된다.

CPU가 346(논리 주소)에 있는 내용을 달라고 하면, 주소 변환이 필요하다. 가장 간단한 MMU는 relocation(=base) register, limit register 를 이용해 주소 변환을 한다.

프로그램이 physical에선 14000번째 부터 올라가있는 상태이다. 그래서 시작 위치와 논리 주소를 더해주면 된다. 그래서 변환된 물리주소에 있는 데이터를 읽어 CPU에게 갖다주면 된다.
논리 주소 + 시작 위치

한가지 더 체크하는 것이 limit이다. 프로그램의 크기(3000)를 limit register가 저장해놓고 있는다. 프로그램이 3000번지까지 있는데 악의적으로 4000번지에 있는 데이터를 달라고 할 수도 있다. 이러면 있지도 않은 데이터를 달라고 해서 주소 변환해버리면 다른 프로그램의 메모리 위치를 달라고 요청하는 것이다. 이러한 경우 반환해선 안되기 때문에 이를 막기 위해 논리주소를 받았을 때 이 논리 주소가 프로그램의 크기보다 크진 않은지 먼저 체크한다. 그래서 만약 limit register의 값을 넘어가는 요청이라면
trap이 걸려 CPU 제어권이 운영체제로 넘어가게 된다. 그래서 운영체제가 이를 살펴보고 악의적인 요청임을 파악하고 강제 abort 시키던지의 응징을 한다.

MMU scheme

사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소 값에 대해 base register의 값을 더한다.

user program

논리 주소만을 다뤄 실제 물리주소를 모르고 알 필요도 없다.

용어설명

Dynamic Loading

loading : 메모리로 올리는 것

따라서 동적으로 메모리를 올리는 것
프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load 하는 것
프로그램이 실행될 때 프로그램을 메모리에 통째로 옮긴다면, static loading이 될 것이다.
프로그램이라는 것은 방어적으로 만들어지기 때문에 프로그램 전체가 균일하게 사용되지 않는다. 그래서 사용되지 않는 코드도 많다. 자주사용되는 코드들은 한정적이다.
따라서 이걸 통째로 올리는 것은 비효율적이기 때문에 미리 올려두는 것이 아닐 상황이 생길 때 메모리에 올린다.

정교하게 알아둬야함
지금 컴퓨터 시스템은 실행하면 프로그램을 통째로 올리지 않고 필요할 때 올라갔다가 쫓겨나고 다시 올라가고 한다. 이것은 운영체제의 페이징 시스템에 의한 것이다. 그래서 지금의 일반적인 페이징 기법은 운영체제가 직접관리하는 것이다.

이 dynamic loading은 운영체제가 아닌 프로그래머가 프로그램 자체에서 구현하는 것이다. OS가 라이브러리 형태로 지원을 하므로 프로그래머가 이를 사용한다.

요즘은 섞어쓰기도 한다.

Overlays

메모리에 프로세스의 부분중 실제 필요한 정보만을 올린다.
dynamic loading과 똑같은 말인가?
역사적으로 좀 다르다. Overlays는 초창기 컴퓨터 시스템에서 메모리 크기가 작기 때문에 프로그램을 메모리에 올려놓는게 불가능했다. 그래서 프로그래머가 이를 메모리에 올릴 때 프로그래머가 프로그램을 직접 쪼개서 올리던 것.

운영체제의 지원이 없고 프로그래머가 직접 구현하는 것이다. (라이브러리 사용 X)

Swapping

프로세스를 메모리에서 통째로 backing stroe(하드디스크 = swap area)로 쫓아내는 것이다.

중기 스케줄러가 swap out시킬 프로세스를 선택했었다.
메모리에 너무 많은 프로그램이 올라와있으면 시스템이 굉장히 비효울적이기 때문에 프로그램 중 몇개를 통째로 디스크로 쫓아내는 것
중기 스케줄러는 어떤 프로그램을 메모리에서 쫓아내는가? CPU 우선순위가 낮은 것 (수행 가능성이 낮은 것)!
이 swapping이 지원되기 위해선 바인딩과 연관지어 생각해야 한다. compile time binding, load time binding이 사용된다면 프로그램을 쫓아냈다가 다시 돌아올 때 원래 주소로 올라와야 한다. 따라서 이러한 바인딩에서 swapping은 의미가 별로 없다. 따라서 Run time binding을 사용해 쫓겨났다가 다시 돌아와도 같은 자리가 아니라 빈 곳에 들어갈 수 있는게 좋다.

메모리에서 프로그램을 쫓아냈다가 다시 부르는 것은 파일 입출력과 다르게 양이 많다. 따라서 swap time은 대부분 transfer time(=전송하는 시간, swap되는 양에 비례하는 시간)이다.

"통째로 쫓겨나는 것"

최근엔 통째가 쫓겨나는 게 아니라 프로그램의 주소 공간이 잘게 잘려 일부 페이지만 쫓겨나는 것 조차도 해당 페이지가 swap out되었다고 말하기도 한다.
하지만 원칙적인 swapping의 개념은 주소 공간이 전부 쫓겨나는 것이다.

Dynamic Linking

linking을 실행 시간까지 미루는 기법
linking: 프로그램을 작성하고, 컴파일 -> 링크 -> 실행파일 생성
여러군데 존재하던 컴파일 파일들을 묶어 실행파일로 만드는 것
내가 소스 파일을 여러개 따로 코딩을 해서 링킹을 하기도 하고, 라이브러리들도 링킹이 돼서 실행이 되면 내 코드안에서 실행될 수 있다.

static linking

라이브러리가 프로그램의 실행 파일 코드에 포함됨

Dynamic linking

코드가 내 실행파일 안에 포함되지 않은 상태로 남아있다가 실행 -> 라이브러리 호출하는 곳에 도달 -> 라이브러리 없음, 찾아야함 -> 찾음(보통 별도의 파일 형태로 존재) -> 필요하면 메모리에 올림/이미 올라와있으면-> 그 주소에 가서 실행
내 코드안에 실행파일 만들때 넣는게 아니고 실행파일과 라이브러리가 별도로 존재하게 되고 라이브러리를 찾을 수 잇는 포인터만 내 코드에 넣어둠

예
내가 프로그램을 만들면서 printf 를 사용해 프로그래밍 했다.
printf가 static linking이 이루어지면 내 실행파일 안에 printf는 내가 만든 코드가 아니라도 코드가 이미 포함되어 있다. 내 코드 라이브러리 코드 구분 없이 내 프로그램 주소 공간안에서 그냥 실행되는 것이다.
만약 100명이 각각 printf를 사용하고 실행파일로 만들어 실행하면 같은 기능을 하는 코드라도 100개의 copy가 메모리에 올라갈 것이다.

dynamic linking은 내가 printf를 사용해 프로그래밍을 했지만 printf의 코드가 실행파일에 올라가지 않고 이 라이브러리의 위치를 찾을 수 있는 포인터만 실행파일에 포함된다. 그래서 프로그램이 실행되면 라이으버리르 코드를 사용하는 지점에 다다랐을 때 라이브러리의 위치를 찾아 메모리에 올리고 사용한다. 만약 100명이 프로그래밍 해 실행했다면 -> 이미 메모리에 올라와있다면 공유해서 사용가능
shared 라이브러리라고 한다. 운영체제의 도움이 필요

Allocation of Physical Memory

물리적인 메모리의 관리를 어떻게 할 것인가?

메모리는 일반적으로 두 영역으로 나뉘어 사용한다.

• OS 상주 영역 : interrupt vecotr와 함께 낮은 주소 영역 사용
• 사용자 프로세스 영역 : 높은 주소 영역 사용

사용자 프로세스 영역의 할당 방법 :

• contiguous allocation
  • 연속할당 - 프로그램을 통째로 올리는 것
• noncontiguous allocation
  • 불연속 할당 : 프로그램을 구성하는 부분을 잘게 쪼개서 여러 영역에 분산해 올리는 것
  • Paging

Contiguous allocation

고정 분할 방식

프로그램이 들어갈 사용자 메모리 영역을 미리 partition으로 나누어놓는 것이다.
아래 그림을 보면 4개로 나누어놓았다. 해당 영역들은 균일한 크기로 나눌 수도 있고 균일하지 않은 크기로 나눌 수도 있다.
프로그램 A가 실행될 때 A는 분할1과 크기가 같으므로 해당 영역에 올리면 된다. 프로그램 B는 조금 더 커서 분할2에 들어가지 못하고 분할3에 들어간다. 이렇게 될 경우 낭비되는 영역이 생긴다. 이를 외부 조각, 내부 조각으로 나눌 수 있다.

융통성이 없이 미리 나누어놓기 때문에 외/내부 조각이 생길 수 있다.

외부 조각 External Fragmentation

프로그램B를 메모리에 올리고 싶은데 분할2가 올리려는 메모리보다 크기가 작아 사용되지 못했다. 프로그램이 들어갈 수 있는 공간임에도 불구하고 작아서 사용되지 못한 공간을 말한다.

내부 조각 Internal Fragmentation

프로그램 B의 크기가 분할3의 크기보다 작다. 그래서 분할3은 프로그램 B에 할당되었음에도 남는 공간이 생기게 된다. 따라서 프로그램이 할당된 공간보다 작아 남는 공간을 말한다.

가변 분할 방식

프로그램이 들어갈 사용자 메모리 영역을 미리 나누어놓지 않는것이다.

프로그램이 실행될 때 마다 차곡차곡 메모리에 올려놓는 방법이다. 프로그램 A,B,C가 수행중이라면 이들은 그림의 왼쪽과 같이 차례대로 메모리에 올라갈 것이다. 프로그램 B가 끝나면 해당 프로그램이 있던 자리는 빈 공간이 된다. 그리고 프로그램 D가 실행되는데 D가 프로그램 B 보다 크다면 B가 있던 공간에는 들어가지 못하고 아래 있는 공간에 들어가게 된다.
따라서 중간중간에 외부조각이 생기게 된다.

차곡차곡 쌓더라도 메모리에 hole들이 생겨 외부조각이 생긴다.

가변분할 방식을 쓰면 비어있는 메모리 공간인 hole들이 여기저기 산발적으로 생기게 된다 .
물리적인 메모리에서 어느부분은 프로그램에 의해 사용되고 있고, 어느 부분은 비어있으므로 이를 관리해야한다. 프로그램이 종료되면 할당되었던 공간은 hole에 편입시키고, 프로그램이 새로 들어오면 hole에 할당해야한다.

hole이 여러군데 있을 텐데 어디에다 프로그램을 할당해야하는가? 하는 문제가 있다.

Dynamic Storage-Allocation Problem

가변 분할 방식에서 size n인. 요청을 만족하는 가장 적절한 hole을 찾는 문제
적어도 hole의 크기가 n보단 작아야 하는데, 이 hole이 많을 때 어디에 넣어야 하는가가 문제다.

• First fit
  • 제일 처음 발견된 hole에 넣는 것이다.
• Best fit
  • hole을 다 살펴본 다음 프로그램에 가장 잘 맞는 hole에 넣는 것
  • 프로그램의 크기와 가장 근접한 크기의 hole
  • 전체 hole을 다 살펴봐야하기 때문에 탐색 부담이 있다.
• Worst fit
  • 가장 큰 hole에 프로그램을 할당하는 방법이다.
  • 가장 큰 hole을 찾으려면 hole을 모두 돌면서 찾아야한다.
  • 왜 어리석을까? 나중에 더 큰 프로그램이 들어올 수 있을 것이고, 지금의 프로그램이 들어가기에 더 적합한 것이 있을 텐데 탐색 부담까지 있고, 작은 hole들을 만들어 내기 때문이다.

first-fit과 best-fit이 worst-fit보다 속도와 공간 이용률 측면에서 효과적이다.

hole만 찾아 넣게 되면 중간중간에 작은 hole들이 많이 생기게 된다.
사용중인 프로그램들을 한군데 모아서 hole을 크게 만들 수 있다.

compaction

external fragmentation문제를 해결하는 한 가지 방법
사용중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것이다.
매우 비용이 많이 드는 방법 -> 전체 프로그램의 바인딩과 관련된 문제이므로
아무때나 할 수 있는 것이 아니고 run time binding이 지원되어야만 할 수 있다. compaction을 하는 것이 좋은가? => 하는 것 보다 최소한의 프로그램만을 이동시켜서 큰 hole을 만드는 것이 좋을 것이다. => 어떤 프로그램을 이동시켜야하는 등의 매우 복잡한 문제이다.

불연속 할당 방법은 크게 paging 기법과 segmentation으로 나눌 수 잇다.
paging 기법은 프로그램을 구성하는 주소공간을 같은 크기의 페이지로 잘라 페이지 단위로 물리적인 메모리에 올려놓거나 bacing store에 내려놓거나 하는 것이다. 물리 주소도 페이지 크기로 미리 잘라놓고 이를 page frame이라고 한다. page frame하나하나에는 페이지 하나가 올라갈 수 있다.
hole들의 크기가 균일하지 않아 어떻게 넣어야 하는지, compaction등의 고민을 하지 않아도 된다. 왜냐하면 비어있는 공간이 동일한 공간의 frame이므로 아무곳이나 들어가도 되는 것이 장점이다.

하지만 불연속 할당의 단점은 주소 변환이 복잡해진다는 것이다. 단지 시작주소만 더해서 되는 것이 아니고 page 별로 주소 변환을 해야한다.

segmentation은 프로그램의 주소공간을 의미있는 단위로 자르는 것이다. 프로그램의 주소공간이라는 것이 코드, 데이터, 스택의 의미있는 공간으로 구성된다. 따라서 code segment, data segment, stack segment로 잘라 각각의 segment를 필요시에 물리적으로 다른 위치에 넣을 수 있는 것이다. 의미 단위라고 했으므로 code, data, stack으로 나눌 수도 있고 더 잘게 자를 수도 있다. 각각의 함수들을 다른 segment로 만들 수도 있다. segment는 의미 단위로 자른 것이므로 크기가 균일하지 않다. 따라서 프로그램의 크기가 달라 발생했던 문제들이 segmentation에서도 생길 수 있다.

Paging

• 프로세스의 주소 공간을 동일한 사이즈의 page 단위로 나누는 것이다.
• virtual memory의 내용이 page 단위로 noncontiguous하게 저장된다.
• 일부는 backing storage에, 일부는 physical memory에 저장된다.

Basic method

• physical memory를 동일한 크기의 frame으로 나눔
• logical memory를 동일 크기의 page로 나눔 (frame과 같은 크기)
• 모든 가용 frame들을 관리
• 단지 레지스터 두개를 이용한 주소 변환은 안되고 page table을 이용해 주소 변환을 한다.
• page table : 프로그램을 구성하는 각각의 페이지들이 물리 주소 어디에 들어가있는지 저장되어있다.
• 외부조각은 안생기나, 내부 조각은 생길 수 있다.
• 왜 내부 조각이 생기냐 ? 프로그램의 크기가 page의 배수가 아닌 경우 마지막 페이지는 내부에 남는 공간이 생기므로

페이징 기법은 프로그램을 구성하는 논리적인 메모리를 페이지로 잘라서 각각의 페이지를 물리적 메모리의 비어있는 곳 어디든 넣을 수 있다. 여기서 주소 변환은 page table이 사용된다. 논리적인 페이지들이 물리적인 주소 어디에 들어가있는가에 대해 저장되어있다.

논리적인 page0번이 물리 주소 frame 1번에 들어가 있는 것을 확인할 수 있다.
주소 변환을 위해 table은 순차적으로 검색할 필요가 없다. n번째 페이지를 주소 변환하고 싶다면 page table에서 n번째 데이터를 찾아보면 주소를 알 수 있다. index를 이용해 바로 접근할 수 있다.

논리적인 페이지 번호를 물리적인 페이지 프레임 번호로 바꾸는 것

page 내의 offset(페이지 내부의 순서)은 주소 변환시 영향이 없고, 페이지 번호만 변환된다.

그렇다면 이 page table이 어디에 들어갈 것이냐 ? MMU 기법에서는 register 단위로 했다. 주소공간을 페이지 단위로 자르는데 이는 4kb 단위이다. 따라서 크기가 크다. 프로그램 하나의 주소공간에 보통 100만개의 페이지가 필요하다. 레지스터에 들어갈 수 있느냐 ? 못들어간다. 프로그램마다 page table이 별도로 존재해야한다. page table의 크기가 크기 때문에 memory에 집어넣게 된다. 그래서 메모리에 접근하기 위해선 주소 변환을 한다음 해야하는데 이를 위해선 page table에 접근해야하는데 page table은 또 메모리에 있다. 따라서 page table 을 위한 접근 1번, 실제 데이터로의 접근 1번 해서 총 2번의 main memory 접근이 필요하다.

메모리상의 페이지테이블의 시작위치를 Page table base register가 가지고 있다. 또한 페이지 테이블의 길이를 Page table length register가 가지고 있다. 매번 2번씩 메모리에 접근하는 것은 비효율적이므로 translation look aside buffer라 불리는 고속의 lookup hardware cache를 사용한다.

그림을 보면 좌측에 CPU 아래에 page table이 있는데 이 page table은 memory 내에 있었다. main memroy위에 캐시 메모리가 있다. 메인 메모리에서 빈번히 사용되는 데이터를 캐시데이터에 저장해서 CPU에서 빨리 접근하는..

주소 변환을 위한 별도의 캐시를 두는 것이 TLB이다. 데이터를 보관하는 캐시가 아닌 주소 변환을 위한 캐시이다.
페이지 테이블에서 빈번히 참조되는 일부 엔트리를 캐싱한다. 메인 메모리 보다 접근 속도가 빠른 하드웨어로 구성되어있다. CPU가 논리적인 주소를 주면 메인 메로리에 있는 페이지 테이블에 접근하기 전에 TLB에 접근해 저장되어있는 정보를 통해 주소변환을 할 수 있는지 체크한다. 그래서 저장되어있으면 TLB를 통해 바로 주소 변환이 가능하다. TLB에 없는 경우 메인 메모리의 page table에 접근해 두번의 메인 메모리 접근이 필요하다.

TLB는 페이지 테이블의 전체 데이터를 가지고 있는 것이 아닌 빈번히 참조되는 엔트리 몇개만 가지고 있다. 이때 page table에선 p번째의 frame 번호만 가져가면 되는데 TLB는 그게 아니라 page number, frame number를 모두 가지고 있어야 한다. 주소 변환을 위해 TLB의 특정항목이 아닌 전체 항복에 대해 찾아봐야하는 것이다.

TLB는 특정항목이 아닌 전체를 탐색해야 하니 시간이 오래걸린다. 그래서 parallel search가 가능하다.
page table은 index로 탐색하지 전체를 탐색하는 것이 아니니 parallel search가 필요없다.

프로그램마다 각각의 page table을 가지고 있다고 했으므로 TLB도 프로그램 별로 존재한다. 그래서 TLB는 context switch 때 flush(remove old entries) 된다.

전체 바이트 주소는 서로 다른 바이트 몇군데를 구분할 수 있느냐? 32비트까지 ! 32비트 어드레스 주소를 쓴다면 메모리주소가 0부터 2의 32승 - 1까지이다.
2의 10승 : K , 2^20 = M, 2^30 = G => 2^32B (4GB)
프로그램이 32bit 주소체계 -> 페이지로 나눔, 이때 페이지는 4KB 단위 -> 페이지 1M개의 page가 생성 -> page table의 entry가 1M개이다. 그렇다면 page table도 메모리에 들어가야하고 각 프로그램마다 페이지 테이블이 따로 있는데, 이를 다 따로 메모리에 집어넣으면 공간낭비가 심함 각 page entry가 4B정도 된다. 프로그램 마다 page table을 위해 4MB의 공간이 필요하다. => 공간낭비 심함 -> 2단계 페이지 테이블

4GB의 메모리 주소 공간에서 프로그램이 사용하는 부분은 지극히 일부분이다. 사용안되는 부분이 상당 부분을 차지한다. 페이지 테이블이라는 것은 엔트리에 구멍이 있다고 해서 빼고 만들 수 없다. 왜냐하면 index 기반이기 때문이다. 결국 주소 체계중에 일부분만 사용함에도 page table은 다 만들어져야한다.
그래서 1단계 page table을 사용하면 공간낭비가 심하다는 것이다.

그래서 사용하는 것이 2단계 page table이다.

보통은 행정구역도 계층적으로 두고 있다. 이와 같이 page table도 계층적 구조를 띄는 것이다.

2단계 page table에서의 주소변환은 아래와 같다.

먼저P1번째 엔트리를 찾는다. 이때 찾아지는 것은 안쪽 페이지 테이블 중에 어떤 페이지 테이블인지 지정해주는 것이다. 왜냐하면 안쪽 페이지 테이블이 여러개 이기 때문이다. 그래서 바깥쪽 테이블의 포인터가 가리키는 것은 안쪽 테이블이 어떤것인지다.

이것이 정해지면 안쪽 페이지 테이블의 번호인 P2 번째의 물리적인 페이지 frame 번호를 얻게 된다. 그러면 해당 frame에 가서 d번째 데이터를 얻게 된다. 2단계 페이ㅣ 테이블에서 기억해야할 점은 안쪽 테이블 페이지의 크기가 페이지 크기와 같다. 즉 안쪽 페이지 테이블은 테이블 자체가 페이지화돼서 어딘가에 들어가 있게 되는 것이다. 안쪽 페이지 테이블의 크기는 하나당 4KB가 된다. 하나의 엔트리가 4B이므로 엔트리 개수는 1K개 이다.

32비트의 주소체계 중에서 offset이 얼마나 되어야 하고, 안쪽 페이지, 바깥쪽 페이지가 몇 bit로 표현되어야하는지 알아보자. 페이지 하나의 크기가 4KB이기 때문에 4KB안에서 Byte단위로 주소 구분을 하려면 몇 bit가 필요할까? 4KB는 2의 12승 바이트이다. 즉, 하나의 페이지 안에서 몇번째 떨어져있는 바이트인지를 구분하기 위해서는 서로 다른 4K 위치를 구분하기 위해 몇비트가 필요한지 보면 된다. 서울시 내에 집이 100채가 있다면 이를 구분하기 위해 번지수를 00번 부터 매기면 99번까지 생긴다. 즉, 10진수로 2자리면 된다. 만약 집이 10000채가 있다면 이들을 구분하기 위해 10진수 4자리가 필요하다. 즉, 10의 4승채의 집을 구분하기 위해선 10진수 4자리가 필요하고 2의 12승 바이트를 구분 하기 위해선 12bit가 필요하다는 것이다. 그래서 페이지 안에서 바이트 단위로 얼마나 떨어져있는지를 구분하는 오프셋을 위해서 12비트가 필요 그리고 위에 있는 페이지 번호는 어떻게 안쪽 페이지 번호와 바깥쪽 페이지 번호로 나눌 것인가 ? 그냥 편하게 10비트씩 공평하게 나누면 계산도 편하고 쉬울 것이다. 하지만 이렇게 결정되는 것은 아니다. 안쪽 페이지 테이블이 페이지화 되어서 들어간다고 했다. 즉, 4KB인데 각 엔트리가 4B이기 때문에 엔트리가 1K개 있다. 안쪽 페이지 테이블의 시작위치로 부터 P2라는 번호의 값은 두번째 페이지 테이블 에서 몇번째 떨어져있는지를 나타낸다. 근데 P2에는 1K개의 엔트리가 존재하므로 1K개의 엔트리 위치를 구분하기 위해 1K는 2의 10승이고 2의 10승을 구별하기 위해선 10개의 비트가 필요하므로 안쪽 페이지를 위한 비트가 10bit인것이다. 따라서 P1은 나머지인 10bit가 할당된다.

32bit 주소 체계를 사용하지 않고 64비트 주소 체계를 사용한다면 ? 각각을 구분하기 위해 몇 비트가 필요한지 각각이 어느정도의 크기인지 생각하면 된다.

페이지 테이블이 프로그램마다 엔트리가 100만개 이상이 필요하고, 2단계 페이지 테이블을 사용하면 안쪽 테이블은 마찬가지로 100만개 만들어야 하고 바깥쪽 페이지 테이블이 하나 더 만들어져야 하므로 1단계 페이지 테이블을 사용하는 것보다 공간적으로 더 손해이다. 또한 주소 변환을 한번 더 거쳐야 하므로 시간적으로도 손해이다.
시간도 공간도 손해인데 왜 사용하는 것일까 ? 프로그램을 구성하는 page 중 사용되는 것은 별로 안된다. 근데 page table을 만들 땐 사용되지 않는다고 해서 entry를 없애버리고 만들 수 없다. 하지만 2단계 페이지 테이블을 사용하면 이를 할 수 있다. 바깥쪽 페이지 테이블은 물리적인 크기 만큼 생성이 되지만, 안쪽 페이지 테이블은 실제 사용이 되는 메모리에 대해서만 만들어지는 것이다. 따라서 공간을 줄일 수 있다.

Multi level page table

페이지 테이블을 2단계로만 쓰는 것이 아니라 다단계로 사용할 수 있다. 테이블을 위한 공간을 더 줄일 수 있지만 한번 주소 변환을 하려면 페이지 테이블을 여러번 거쳐야 하고 페이지 테이블이 물리적인 메모리상에 있기 때문에 4단계 페이지 테이블이라고 하면 메모리에 접근하기 위해 4번(주소변환) + 1번(실제 접근)이 ㅣㄹ요하다.

그래서 시간 오버 헤드가 굉장히 크다. 대부분의 주소 변환은 TLB를 통해 직접 이루어지기 때문에 이러한 다단계 페이지 테이블을 사용하더라도 시간이 지나치게 걸리지 않는다.

메모리 접근 시간이 100ns, TLB 접근시간이 20ns이고 TLB hit ratio 가 98%인 경우 effective memory access time이 128 nanoseconds로 계산된다. 따라서 결과적으로 주소 변환을 위해 28ns만 소요된다.

effective memory access time = 0.98(TLB hit ratio) 120(메모리 접근 1, TLB 접근 1) + 0.02(TLB miss ratio) 520(메모리 접근 5, TLB 접근 1)

Valid/Invalid Bit in a Page Table

지금까지 본 페이지 테이블엔 logical 메모리에 있는 페이지 개수만큼 페이지 테이블에 엔트리가 존재하고, 그 엔트리에는 해당 페이지가 메모리의 어디 frame에 올라가있는지를 나타냈다.
하지만 사실은 페이지 테이블엔 주소 변환 정보 뿐만아니라 부가적인 정보를 나타내는 비트가 더 있다. 그 중 하나가 valid/invalid bit이다.
메모리에 의미있는 값을 집어넣든 안집어넣든 0과 1의 조합은 숫자로 해석될 것이다. 위의 그림을 보면 페이지는 5번까지 존재하지만, 페이지 테이블엔 7번 엔트리까지 존재하는 것을 볼 수 있다. 즉, 6번과 7번은 사용하지 않는 다는 것인데,이는 프로그램의 주소공간이 가질 수 있는 maximum size 만큼 엔트리가 생겨야 하기 때문이다.
이 프로그램은 5page까지 있다. 따라서 페이지 테이블의 6,7 엔트리는 사용하지 않는다.
그렇다면 왜 6,7 엔트리가 존재하냐?
프로그램의 주소공간이 가질 수 있는 maximum size만큼 페이지 테이블 엔트리는 생겨야 하기 때문이다.
그래서 페이지 테이블에서 해당 엔트리가 유효한 것인지를 valid/invalid bit로 나타내는 것이다.
페이지가 항상 메모리에 올라가지 않을 수도 있다. 당장 필요하지 않은 것은 backing store에 내려가있을 것이다. 이러한 경우에도 invalid라고 표시해놓는 것이다.
위의 그림을 보면 page table에 6,7번이 invalid로 표시되어 있는 것을 볼 수 있다.

valid/invalid bit

• valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함(접근 허용)
• invalid는 해당 주소의 frame에 유효한 내용이 없음을 뜻함(접근 불허)
  • 프로세스가 그 주소 부분을 사용하지 않는 경우
  • 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우

valid/invalid bit 말고도 부가정보를 나타내는 bit가 존재하는데 이게 바로 protection bit이다. 이는 page에 대한 접근 권한(read/write/read-only)를 나타낸다. 자기 자신이 자기 페이지만 접근하기 때문에 다른 프로세스가 이 페이지를 못보게 하는 등의 용도는 아니다. 그렇다면 무슨 의미일까? 접근 권한을 제어하는 것은 어떤 연산에 대한 접근 권한을 제어하는 것이다.

Inverted Page Table

page table의 문제점 ? 너무 많은 메모리 공간을 차지한다.

기존 페이지 기법을 반대로 생각한 것이다.
원래는 프로세스마다 페이지 테이블이 존재했는데, Inverted Page Table은 시스템 안에 page table이 하나 존재한다. page table의 엔트리가 프로세스의 페이지 만큼 존재하는 것이 아니고 물리적인 메모리의 프레임 개수만큼 존재한다.
기존에는 index를 이용한 주소변환을 사용했는데 Inverted Page Table에선 이게 불가능 하다.
페이지 프레임의 f번째 엔트리를 가면 논리적인 페이지 번호가 나온다. 원래라면 논리적인 페이지 번호를 통해 frame 번호가 나오는데 역발상인것이다 !

하지만 주소 변환이란 논리적인 주소 -> 물리적인 주소의 변환인 것이다. 그래서 page table에서 frame 번호를 찾기 위해선 page table을 모두 찾아봐야한다. 0번부터 찾다가 5번에 찾던 논리 주소가 있다면 5번 프레임에 있는 것이다.

이거 왜 쓰냐 ?
페이지 테이블을 위한 공간을 줄이고자 하는 것이다. 대신 시간적인 오버헤드가 있다. 한번에 주소 변환이 되는 것이 아니고 전부 search해야지만 프레임 번호를 알 수 있다. 한가지 더 page table에 저장해야하는 것이 있는데, page number 뿐만 아니라 어떤 프로세스의 page number인지를 기록해야하므로 pid 또한 저장해야한다.

CPU가 논리 주소(pid, p, d)를 주면, 논리 주소 중 pid, p가 page table의 어디에 있는지 검색 -> 찾아진 위치가 위에서 부터 몇번째 엔트리인지 확인해 해당 순번의 frame에 접근하면 된다.

하지만 시간적인 오버헤드가 너무 크다. 따라서 page table에서 pid,p를 찾을 때 순차적으로 찾는 것이 아닌 병렬적인 search를 사용한다. associative register를 사용한다.

Shared Page

다른 프로세스들과 공유할 수 있는 페이지가 있다.
각각의 프로세스가 같은 프로그램을 동시에 돌린다면 code부분은 같고 각각의 데이터만 다르면 되는 것이다.
그래서 이렇게 공유할 수 있는 코드를 물리적인 메모리에 각각 올리는 것이 아니라 하나의 copy만 올리는 것이다.
그래서 P1, P2, P3의 page table의 mapping을 보면 코드 부분 매핑이 같은 것을 알 수 있다.

이를 Re-entrant Code(=Pure code)라 한다. 그래서 read-only로 세팅해 프로세스 간 하나의 code만 메모리에 올린다. 프로세스마다 별도로 관리되어야하는 것은 각각 올려 매핑하는 것이다.

두가지 조건을 만족해야 한다.

• read only여야한다.
• shared code는 동일한 logical address에 위치해야한다.
  • 만약 libc 1, libc 2, libc 3 순서가 프로세스마다 뒤바뀌어 있다면 공유해서 사용할 수 없는것이다.
  • 이는 앞에서 배운 주소 바인딩을 생각해보면 된다.

Segmentation

페이징 기법 - 같은 페이지 단위로 자른것
segmentation - 의미 단위로 자른 것

segmentation은 여러 가지로 정의할 수도 있다. logical address는 <segment-number, offset>으로 구성된다.
segment 별로 주소 변환을 해야하므로 segment table이란 것을 활용한다. 주소 변환을 위해 두가지 레지스터가 지원된다.

• base : segment의 물리 주소의 시작점
• limit : segment의 길이

• s : segment 번호
• offset : 얼마나 떨어져있는지

segment table에는 limit이 존재한다. 페이징에서는 페이지의 크기가 모두 동일했기 때문에 table에 limit가 필요없었는데, sement는 각각 길이가 다를 수 있으므로 limit를 통해 sement의 길이를 알 수 있어야한다.

segment가 3개로 구성되어있는데 s가 5로 되어있는지 확인하는 register가 필요하다. 그래서 s가 sement의 길이 보다 큰 값이 요청되었다면 trap이 걸리게 된다.
d가 너무 커 s+d가 segment의 길이를 넘어가게 된다면 trap이 걸린다.
segment의 개수만큼 table의 엔트리가 생긴다. 페이징에선 프로그램의 주소공간에 따라 달랐다.

segment 길이가 다 다르기 때문에 메모리 내에서 자가게 빈 공간이 생기게 된다. 즉, 가변 분할 방식에서와 동일한 문제점들이 발생한다. 따라서 외부 조각이 발생해 first fit, best fit등을 사용해야 한다.

장점은 ? 의미 단위이므로 의미 단위로 어떠한 일이 수행되어야 할때 편리하다. 예를 들어 권한 부여시에도 의미에 따라 권한을 부여하는것이 굉장이 자연스럽다. 페이징에선 같은 크기로 나눠 권한을 주기 때문에 페이지 내에서 부여할 권한이 다른 경우 애매하다.
공유할 때도 마찬가지이다. 공유할 때도 의미단위로 공유를 하지 크기 단위로 공유하지는 않는다.
따라서 공유와 보안에 있어 페이징에 비해 훨씬 효과적이다.

페이징에선 프로그램에 대한 페이지가 굉장히 많아서 공간낭비가 심했다. 그에비해 segmentation에서는 segment 개수가 많지 않다.

아래는 segment의 공유를 보여준다. 같은 논리상의 주소(=segment number)여야 한다. private segment는 각각 다른 곳에 존재한다.

Paged segmentation

segmentation과 paging을 합친것으로 segment 내에 페이지가 있는 것이다.

먼저 segment에 대한 주소 변환을 한다.

segment 하나가 여러개의 page로 구성되기 때문에 메모리에 올라갈 땐 page로 나눠져서 올라가게 된다. 따라서 hole이 생기지 않는다는 장점이 있다. 하지만 의미단위로 해야하는 작업들은 segmentation 단계에서 하는 것이다. original segmentation는 잘 쓰지 않는다. 쓰려면 paged segmentation을 사용

original segmentation과의 차이점
기존의 segment table에는 limt(segment length), base(start segment)였는데, base address를 가지는 것이 아닌 segment를 구성하는 page table의 base address를 가지고 있다.

위의 그림에서 유의해야할 점은 d는 segment내에서의 offset이고, d'은 page offset이다.

물리적인 메모리관리에 대해서 이제까지 배웠다.
주소변환 (CPU가 논리적인 주소 제공 -> 물리적 주소로 변환)
운영체제의 주소변환을 위한 역할은 없다. 모두 하드웨어적으로 해결하는 문제들이다.
프로세스 하나가 CPU를 잡고 있으면서 메모리 접근 -> 운영체제 도움을 받지 않는다. 왜 ? 어떤 프로세스가 CPU를 가지고 메모리 접근을 하는데 주소변환을 할 때 마다 개입해야 한다면 CPU가 운영체제가 넘어가야된다. 주소 변환을 하고 CPU가 다시 프로세스로 돌아온다 ? 하는 건 말이 안되는 것이다. CPU가 매 클럭마다 instruction을 수행하고 메모리에 접근하고 하는 것은 모두 주소 변환을 통해서 이루어지는데, 이러한 매순간마다 운영체제의 도움이 필요하면 CPU가 계속 왔다갔다 해야되므로 말이 안된다. 따라서 주소 변환은 무조건 하드웨어적으로 이루어지는 것이다. 운영체제가 끼어들어야하는 경우는 ? I/O 장치로 접근할 때 -> 사용자 프로세스가 직접 I/O 접근을 못하기 때문에 운영체제에 부탁을 하는 것이다. 하지만 매번 메모리 접근할때마다 운영체제가 해줘야한다는 것은 상식적으로 말이 안된다는 것이다.

출처

Operating System Concepts 10th
KOCW 강의 - [운영체제] 이화여자대학교 반효경 교수