[운영체제] 메모리 관리

Memory Management

🔊 이화여자대학교 반효경 교수님의 KOCW 2014년 1학기 운영체제 강의를 들으며 정리한 노트입니다.
      캡쳐한 이미지 중 따로 출처 명시를 하지 않은 이미지 또한 반효경 교수님 강의 자료에 있음을 밝힙니다.

Logical vs. Physical Address

메모리라는 것은 주소를 통해서 접근하는 매체이다.

• Logical address(=virtual address)

  논리적인 주소 (가상 주소라고도 부름)

  • 프로세스마다 독립적으로 가지는 주소 공간
  • 각 프로세스마다 0번지부터 시작
  • CPU가 보는 주소는 logical address임

• Physical address

  물리적인 주소

  • 메모리에 실제 올라가는 위치

＊주소 바인딩: 주소를 결정하는 것

프로그래머 입장에서는 숫자로 된 주소를 사용하지 않고, 변수명이나 함수명 같은 Symbol로 된 주소를 사용함. 그것을 여기서 Symbolic Address라고 한다. 이것이 컴파일이 되면 0번지부터 시작하는 그 프로그램만의 독자적인 숫자로 된 주소로 만들어져 바뀌게 된다. 이게 실행이 되려면 물리적인 메모리에 올라가야되니까 주소 변환이 이루어져야 되는 것이다.

그러면 이 주소 변환이 언제 이루어지는가? (아래)

주소 바인딩 (Address Binding)

크게 3가지 시점으로 나눠볼 수 있다.

• Compile time binding

  주소 변환이 컴파일 시에 이뤄지는 방법

  • 물리적 메모리 주소(physical address)가 컴파일 시 알려짐
  • 시작 위치 변경시 재컴파일
  • 컴파일러는 절대 코드(absolute code) 생성

• Load time binding

  실행이 시작될 때 주소 변환이 이루어지는 것

  • Loader의 책임하에 물리적 메모리 주소 부여
  • 컴파일러가 재배치가능코드(relocatable code)를 생성한 경우 가능

• Execution time binding (=Run time binding)

  프로그램이 시작된 이후에도 실행하다가 중간에 물리적인 메모리 주소가 바뀔 수 있는 방법

  • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
  • CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table)
  • 하드웨어적인 지원이 필요
    (e.g., base and limit registers, MMU)

이 3가지를 비교하는건 아래 그림을 통해서 보면 쉽다.

맨 왼쪽에 소스코드가 있다. 무슨 언어로 된 프로그램인지는 모르지만 프로그램이 하나 만들어져있다. 이 프로그램에는 Symbolic address로 주소가 표현이 되있다. Add A, B는 A 위치에 있는 값 100하고 B 위치에 있는 값 330을 더해서 A 위치에다가 저장하라는 뜻이라고 정의한 것이다. 이 연산결과 A 위치에 100이었던 것이 두개가 더해지니까 430이 될 것이다. Jump C는 C 위치로 점프를 하라는 얘기다.
Symbolic address로 프로그래머는 메모리 주소를 사용한다는 것을 보여준 코드이다. 이게 컴파일이 되서 실행파일이 만들어지게 되면 Symbolic address였던게 숫자로 된 주소로 바뀌게 된다. 그게 프로그램마다 가지는 주소이기 때문에 여기서는 Logical address가 되는 것이다. 그래서 소스코드의 각각의 문장들이 메모리에 0번지, 10번지, 20번지, 30번지, 40번지 이런식으로 표시가 되고, Add A, B하라고 했던게 20번지에 있던 내용과 30번지에 있던 내용을 더하라는 이런식의 주소로 바뀌게 된다. 그 다음에 Jump C라고 했던 부분이 40번지로 점프해라 이런식으로 바뀌어서 이 프로그램의 Logical address로 표시가 된 것이다.

이게 실행이 되려면 물리적인 메모리에 올라가야되고, 물리적인 메모리에 주소가 결정되는 것을 우리가 주소 바인딩이라고 부른다는 것이다. 그 물리적인 메모리 주소가 결정되는 시점이 앞에서 봤듯이 3가지로 나눠볼 수 있었다.

그 중에서 제일 위에 나와있는 Compile time binding은 컴파일 시점에 이미 물리적인 메모리 주소가 결정이 되는 것이다. 즉, 컴파일 이후의 Logical address, 논리적인 주소라고 얘기했지만 Compile time binding은 컴파일 시점에 이미 물리적인 주소가 결정이 되야되기 때문에 이 Logical address가 사실은 물리적인 주소라는 것이다.
그래서, 이 Compile time binding을 쓰게 되면 이 프로그램을 물리적인 메모리에 올릴 때는 항상 Logical address에 주어져있는(이미 결정되있는) 이 주소로 올려야 된다는 것이다. 즉, 물리적인 메모리에 다른 주소는 많이 비어있는데도 불구하고 항상 이 프로그램은 0번지부터 정해져있는 위치에만 올려야 된다는 것이고, 이게 컴파일 타임에 미리 결정되기 때문에 대단히 비효율적이다.
지금의 컴퓨터 시스템에서는 이런 Compile time binding을 사용하지는 않는다. 그렇지만, 예전에 컴퓨터 안에서 프로그램이 하나만 실행되는 그런 환경에서는 어차피 다른 프로그램이 같이 올라갈 일이 없기 때문에 컴파일 할 때 미리 물리적인 메모리 주소를 결정해서 올리는 이런 방법이 사용되기도 했었다.

두번째 나와있는 Load time binding은 프로그램이 시작되서 메모리에 올라갈 때 물리적인 메모리 주소가 결정이 되는 것이다. 그래서 이 프로그램에 논리적인 주소가 0번부터 주어져있고, 컴파일 타임에는 논리적인 주소까지만 결정이 된 상태에서 이것을 실행시키게 되면 메모리를 봤더니 물리적인 메모리에 500번지부터 비어있더라… 그러면, “논리적인 주소 0번지를 물리적인 메모리 500번지부터 올린다.” 이런 얘기다. 이게 Load time binding이라는 것이다.

그 다음에 세번째에 나와있는 Run time binding은 Load time binding처럼 실행시에 주소가 결정되는 것은 똑같다. 그런데, 이 주소가 실행 도중에 바뀔 수가 있다는 것이다. 이미지를 보면 논리 주소 0번지가 물리적인 메모리 주소 300번지에 올라와있는데 일단 이렇게 바인딩이 됐다가 실행되는 도중에 300번지부터 있던 이 내용이 700번지부터로 이동해갈 수가 있다는 것이다. 즉, 프로그램이 실행되다가 경우에 따라서는 이런 내용이 300번지부터 올라와있었는데 메모리에서 쫓겨날 수가 있고, 그리고나서 나중에 또 다시 올릴 때는 300번지에 다른 내용이 올라가 있다면 비어있는 700번지에다가 바인딩을 해서 올리고… 이런 것이 지원이 되는게 바로 Run time binding이라는 것이다.
그래서, 지금의 우리들이 사용하는 컴퓨터 시스템은 당연히 Run time binding을 지원 하고 있다.

Compile time binding을 사용할 때는 이 주소가 논리적인 주소이지만 또 물리적인 메모리 주소로 fix가 되는 것이기 때문에 Compile time binding에 의해서 만들어진 이런 코드를 우리가 absolute code(절대 코드)라고 부른다. 그래서, Compile time binding에 의한 코드는 만약에, 메모리에 올라갈 위치를 바꾸고 싶으면 컴파일을 다시 해야된다. 예를 들어, 물리적인 메모리 0번지부터 올리는게 아니라 500번지부터 올리게 하고 싶다. 그런데 지금 Compile time binding을 쓰겠다그러면 컴파일을 새로해야지 올라갈 수 있는 위치를 바꿀 수가 있는 것이다. 절대 코드 이기 때문에 그런 것이다.

반면에, Load time binding을 쓰는 데서는 Run time binding도 마찬가지겠지만 컴파일을 해서 만들어지는 논리적인 코드가 재배치가능코드(relocatable code)라고 해서 이것은 항상 특정 위치에 올라가야되는게 아니라 비어있는 위치는 실행 시에 어느 위치든지 올라갈 수 있는 그런 코드라는 것이다.

그래서, Compile time binding이나 Load time binding은 프로그램이 시작될 때 이미 주소가 다 결정이 되고 그 주소가 변화가 없는데, Run time binding은 프로그램 실행 중에도 계속 주소가 바뀐다는 것이다.
그렇기 때문에, CPU가 어떤 메모리 주소를 요청할 때마다 그때마다 바인딩을 체크를 해봐야 된다. 이 내용이 물리적인 메모리 어디에 올라가 있는지를 주소 변환을 그때그때 해야된다는 것인데 그러기 위해서는 Run time binding은 하드웨어적인 지원이 필요하다. MMU라는 하드웨어가 있어서 그때그때 주소 변환을 해줘야되는게 바로 Run time binding 기법이 되겠다.

그러면 CPU가 바라보는 주소는 Logical address일까, Physical address일까?
CPU는 하드웨어이기 때문에 Physical address를 바라볼 것 같지만 사실은, CPU가 바라보는 주소는 바로 위에 보이는 것 같이 Logical address이다.
이게 이렇게 될 수 밖에 없는 이유가…

이 그림을 잘보면 이해를 할 수 있는데, 우리가 왼쪽과 같은 소스코드로 짜여진 프로그램을 컴파일해서 실행파일을 만들게 되면 그 안 각각이 인스트럭션들인데, CPU가 이러한(실행파일 0번지와 같은) 인스트럭션을 실행하려면 메모리 20번지에 있는 내용과 메모리 30번지에 있는 내용을 CPU로 읽어들여서 더하는 연산을 해야될 것이다. 그런데, 현재 실행파일 0번지에 표시되있는 20번지하고 30번지는 Logical address이다. 그리고 이게 실행이 되서 메모리에 올라가더라도 이 인스트럭션 코드 안에 있는 address는 바뀌지가 않는다. 그대로 20, 30이라고 되어있다. 이것들이 올라가는 위치는 0번지부터 시작하던 실행파일 코드가 500번지부터 또는 300번지부터 올라가는 식으로 되있지만 실제로 이 컴파일된 코드 자체 들어가있는 주소까지 바꿀 수는 없다. 그렇게 되면 컴파일을 새로 해야되는 문제이기 때문에…
그래서, 이게 메모리에 올라갈 때 시작위치는 바뀌지만 그 안에 있는 코드 상의 주소는 고스란히 Logical address로 남아있을 수 밖에 없다. 그래서 CPU가 예를 들어서 메모리 500번지에 올라가 있는 Add 20, 30 이런 인스트럭션을 실행하겠다 그러면 20번지에 있는 내용과 30번지에 있는 내용을 더하려고 하면 20번지 30번지에 있는 (메모리에 있는) 내용을 CPU안으로 읽어 들여야하는데 그 주소가 Logical address라는 것이다.
즉, CPU가 바라 보는 주소도 Logical address일 수밖에 없다. 그래서 CPU가 매번 메모리 몇번지에 있는 내용을 달라 이렇게 요청을 하면 그때 주소변환을 해서 물리적인 메모리 위치를 찾은 다음에 그 내용을 읽어서 CPU한테 전달을 해야되는 것이다.
그래서, CPU는 Logical address를 본다고 얘기하는 것이다.

아까 전에 Run time binding이 지원되려면 하드웨어적인게 필요하다고 말했는데… Compile time binding이나 Load time binding은 사실 주소 변환이라고 해도 별게 없다. Compile time binding는 이미 결정이 되있는거고, Load time binding은 숫자 얼마를 더해주는 그런 바인딩인데,
Run time binding부터는 그때그때마다 이 내용들이 어디에 올라가 있는지를 주소 변환을 새로 해주는 방법이 필요하기 때문에 주소 변환용 하드웨어 지원이 필요하다는 것이다.
그래서, 주소 변환을 지원해주는 하드웨어를 우리가 MMU(Memory-Management Unit)라고 부른다.

🔊 지금 앞부분에서 설명하고 있는 이 내용은 프로그램이 메모리에 올라갈 때 통째로 메모리에 올라가는 그런 경우를 설명하고 있는 것임.

지금까지 일반적으로 설명한 현재 프로그램 실행이 되는 상황에서는 프로그램에서 필요한 부분만 메모리에 올라가고, 그렇지 않은 부분은 디스크에 쫓겨나고 각각의 코드도 잘려서 여기저기 산발적으로 올라가고...
이런 환경을 이번 메모리 관리에 들어오기 전에 미리부터 설명했었는데, 그것은 현대의 OS가 그렇게 하기 때문에 그렇게 설명을 한 거지만, 지금 메모리 관리로 들어와서는 처음부터 설명을 하는 것이기 때문에 일단은 프로그램의 논리 주소가 통째로 물리적인 메모리에 올라가는 그런 환경을 가정하고 주소 변환을 설명하는 것이다.

Memory-Management Unit (MMU)

주소 변환을 위한 하드웨어

• MMU (Memory-Management Unit)
  • logical address를 physical address로 매핑해주는 Hardware device
• MMU scheme
  • 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register (=relocation register)의 값을 더한다
• user program
  • logical address만을 다룬다
  • 실제 physical address를 볼 수 없으며 알 필요가 없다

주소 변환을 할 때는 기본적인 MMU에서는 레지스터 2개를 통해서 주소 변환을 하게 된다.

Dynamic Relocation

CPU가 “메모리 346번지에 있는 내용을 달라” 이렇게 하게 되면 이것은 logical address라고 했다.
그러면, 주소 변환이 필요한데 이 주소 변환을 해주는 하드웨어 MMU라고 했다.
그리고, MMU의 가장 간단한 MMU 주소 변환은 레지스터 2개로 주소 변환이 이루어진다. 그 레지스터는 relocation register(base register라고도 부름), limit register 이 2개를 이용해서 주소 변환을 하게 된다.
좌측 하단에 있는 그림은 특정 프로그램 즉, process p1이 CPU에서 실행 중인 상황을 나타내고 있어서 p1의 logical memory를 나타내주고 있다. 0번지부터 3000번지까지 있고, 그래서 CPU가 346번지를 달라고 했다면, 이 process p1의 주소 공간에서 0번지부터 346번째 떨어져있는 내용을 지금 CPU가 요청한 상황이다.

그리고, 지금 이 프로그램이 physical memory상에는 14000번지부터 올라가 있는 상황이다. 그럼 주소 변환을 어떻게 해주면 되느냐?
이 프로그램이 물리적인 메모리에 올라가있는 시작 위치(14000번지)하고, 이 논리주소(346번지)를 더해주면 된다.

그러면, 14000번지가 논리적인 주소 0번지이기 때문에 14000번부터 346만큼 떨어진 그 위치에 있는 내용을 읽어서 CPU한테 갖다주면 될 것이다.

이 MMU scheme에서는 base register에다가 이 프로그램의 시작 위치를 갖다가 저장해놓는다. 그래서 주소 변환을 할 때는 논리 주소에다가 시작 위치를 더해서 14346번지 이렇게 물리적인 주소를 얻게 된다는 것이다.

근데, 여기서 한 가지 더 체크하는게 있는데 그것은 바로 limit register를 사용하는 체크이다.
이것은 뭐냐하면 이 프로그램의 최대크기가 있을 것이다. p1이라는 프로그램은 크기가 3000번지까지 가지고 있는 프로그램이다. 그래서, limit register는 이 프로그램의 크기인 3000을 담고 있다.
이렇게 저장해놓는 이유는 이 프로그램이 만약, 악의적인 프로그램이라서 본인의 크기가 3000인데도 불구하고, CPU 중간에 인스트럭션을 통해서 “메모리 4000번지에 있는 내용을 달라” 이런식으로 요청을 할 수도 있다. 그렇게 되면, 이 프로그램은 지금 3000번지까지 밖에 없는데, 만약에 logical address 4000번지를 달라고 하면 4000에다가 시작 위치를 더해주면 그 위치가 physical memory에 정해져 있는 위치 가 아니라 더 바깥이 될 것이다. 3000번지에다가 14000을 더한 17000이 이 프로그램의 제일 끝 부분인데, 있지도 않은 4000번지를 달라고 해서 주소 변환을 해버리면 18000번지… 이 프로그램 바깥에 즉, 다른 프로그램이 존재하는 그런 메모리 위치를 요청하게 되는 것이다.

그런 경우에는 어떻게 해야될까?
요청한다고 주면 안될 것이다! 남의 프로그램 메모리를 보려고 하는 악의적인 시도를 하는 프로그램이기 때문에, 막아야 한다!

Hardware Support for Address Translation

운영체제 및 사용자 프로세스 간의 메모리 보호를 위해 사용하는 레지스터

• Relocation register (=base register): 접근할 수 있는 물리적 메모리 주소의 최소값
• Limit register: 논리적 주소의 범위

그래서, CPU가 메모리 몇 번지를 달라고 논리 주소를 주게 되면, 먼저, 혹시 이 논리 주소가 프로그램 크기보다 더 큰 논리 주소를 요청한 것은 아닌가? 그것부터 체크해본다.
limit register에 있는 값하고 logical address 요청된 것을 비교해보는 것이다. 그래서, limit register의 값을 벗어나는 요청이면 trap이 걸리게 된다. trap이 걸리면 이 프로그램이 CPU를 잡고 있었지만 하던 일을 잠시 멈추고, CPU 제어권이 운영체제한테 넘어가게 된다. 그러면, 운영체제는 trap이 왜 걸렸는지… (trap은 일종의 software interrupt 이다) 왜 걸렸는지 따져보니까 이 프로그램이 악의적이게도 본인의 메모리 주소 아닌 곳을 보려는 시도를 했다고해서 거기에 대한 (프로그램을 강제 abort(중단)시키는 등의) 응징을 한다.

그렇지 않고, 이 logical address가 프로그램 크기 이내에 있는 그러한 요청이었다면, base register(relocation register)의 값을 더해서 주소 변환을 한 다음에 물리적인 메모리 어딘가에 있는 내용을 읽어다가 CPU한테 전달을 해주면 되는 것이다.

그게 register 2개를 이용한 간단한 MMU scheme이라는 것이다.

그래서, 사용자 프로그램은 logical address만 다루고 있다.
그리고, 실제 physical address는 볼 수도 없고 알 필요도 없다.
사용자 프로그램은 logical address를 다루고 있고, CPU도 logical address를 바라보고 있고…

그래서 physical address라는 것은 logical address로 메모리 주소 요청이 됐을 때, MMU가 그때그때 주소 변환을 해서, 얻게 된다는 그런 개념이다.

몇 가지 용어 설명 (Some Terminologies)

• Dynamic Loading
• Dynamic Linking
• Overlays
• Swapping

Dynamic Loading

• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것
• memory utilization의 향상
• 가끔식 사용되는 많은 양의 코드의 경우 유용
  • 예: 오류 처리 루틴
• 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능 (OS는 라이브러리를 통해 지원 가능)

＊ Loading: 메모리로 올리는 것

메모리에 동적으로 올린다…
프로그램을 메모리에 올려야지 실행이 될텐데 메모리에다가 동적으로 올린다. 이건 무슨 뜻일까?
동적으로 올린다는건 그때그때 필요할 때마다 즉, 해당 루틴이 불려질 때마다 그 루틴을 메모리에 올리는 방법을 Dynamic Loading이라고 부른다.

즉, 프로그램이 시작될 때 메모리에 통째로 올려놓는다면 (동적 로딩하고 비교해서 설명한다면 이런 용어를 많이 쓰진 않지만) Static Loading(정적 로딩)정도가 되겠다.

대개 프로그램이라는 것은 방어적으로 만들어지기 때문에, 프로그램 전체 메모리가 균일하게 사용되는게 아니다. 대개 프로그램 중에서 상당 부분은 거의 사용되지 않는 오류 처리 루틴과 같은 것들이 많고… 그래서, 자주 사용되는 부분은 굉장히 한정적인데, 좋은 프로그램 일수록, 좋은 소프트웨어 일수록 그렇다.
아주 이상한 input에 대해서도 처리가 가능하게 방어적으로 프로그래밍을 하기 때문에, 일반적으론 사용안되는 그런 루틴들이 대단히 많이 포함이 되있다는 것이다.

그것을 통째로 메모리에 올리는 것은 비효율적이기 때문에 미리 올려놓는게 아니라 혹시 그런 상황이 생기면 그때 메모리에 올려놓는 이런 방법을 Dynamic Loading이라고 부른다.

근데 여기서 Dynamic Loading의 개념은 조금 정교하게 알아둬야할 부분이 있는데 지금 컴퓨터 시스템도 프로그램을 실행시키면 통째로 메모리에 올라가지 않고, 당장 필요한 부분만 메모리에 올라가고 필요없으면 쫓겨나고 이렇게 된다. 근데, 그게 원래 Original Dynamic Loading의 개념은 아니다.
지금 우리가 프로그래밍을 해놓으면 필요할 때 그때 메모리에 올라가고 필요 없어지면 쫓겨나고 그거는 운영체제가 관리해주는 소위, 페이징 시스템에 의해서 이루어지는 것이다. (페이징 시스템은 뒷 부분에 나온다고 함)

여튼, 지금의 일반적인 OS에서 하는 페이징 기법에서의 올라가고 내려가고 하는 것은 운영체제가 직접 관리해주는 것이고, 보통 Dynamic Loading이라고 하면 운영체제가 지원을 해주는게 아니고 프로그래머가 Dynamic Loading을 직접 하도록 만드는… Dynamic Loading은 그런 개념이다.

그러면, 프로그래머가 수작업으로 언제 어디다가 올리고 이런걸 다 작성하느냐? 하면 그렇지는 않다. 대개 다이나믹 로딩을 프로그래머가 쉽게 하도록 운영체제가 라이브러리 형태로 다이나믹 로딩을 할 수 있는 것을 제공해주고 그것을 통해서 프로그래머는 라이브러리를 써서 만들기 때문에… 일일히 다이나믹 로딩을 어떻게 할지를 만드는건 아니고, 라이브러리를 써서 다이나믹 로딩을 하기 때문에 그렇게 코딩이 어려운 것은 아니다.

그렇지만, 현재 시스템에서 이루어지는 페이징 기법하고 다이나믹 로딩은 원래는 다른 것이다.
(지금은 다이나믹 로딩이라는 말을 섞어서 쓰기도 한다. 프로그래머가 명시적으로 다이나믹 로딩을 해서 이루어지는게 원래 다이나믹 로딩이지만, 프로그래머가 명시적으로 명시하지 않고, 운영체제가 알아서 올려놓고 쫓아내고 이러는 것도 다이나믹 로딩이라는 말로 섞어쓰기도 한다. 라는 그런 정도로 알아두면 된다.)

Dynamic Loading하고 구분해서 살펴봐야 될 용어로 Overlays 라는게 있다.

Overlays

• 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림
• 프로세스의 크기가 메모리보다 클 때 유용
• 운영체제의 지원없이 사용자에 의해 구현
• 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현
  • “Manual Overlay”
  • 프로그래밍이 매우 복잡

내용을 보면 다이나믹 로딩과 거의 똑같다. Overlays의 첫번째 문장내용만 봐서는 다이나믹 로딩과 오버레이는 차이가 없는데… 역사적으로 조금 다르다.

오버레이는 초창기 컴퓨터 시스템에서 워낙 메모리 크기가 작기 때문에 프로그램 하나를 메모리에 올려놓는 것 마저도 불가능했다. 그래서, 프로그래머가 프로그램을 메모리에 올려서 실행시킬 때는 큰 프로그램을 쪼개가지고… (이번에는 이쪽 부분을 메모리에 올려놓고 실행을 하고, 그러다가 그 부분이 아니라 다른 부분이 실행이 되어야되면 다른 부분을 또 메모리에 올려놓고) 이런거를 프로그래머가 수작업으로 코딩을 한 것이다.
그래서, 이 오버레이를 다른 말로 Manual Overlay라고 함. 대단히 불편하고 어려운 프로그래밍이 될 것이다.

이것은 운영체제의 지원이 없고, 프로그래머가 직접 어떻게 올리고 내릴지를 코딩을 통해서 다 해야되기 때문에 첫번째 나와있는 실제로 필요한 정보만 올리는 것을 프로그래머가 코딩을 통해서 하는 것이고, Dynamic Loading도 결과적으로는 그렇게 되지만 그거를 라이브러리를 통해서 하기 때문에 프로그래머가 어떻게 올리고 내리는지를 자세하게 코딩 할 필요는 없다는 것이다.

그게 Dynamic Loading과 Overlays의 차이점이 되겠다.

Swapping

• Swapping

  • 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것

    하드디스크 같이 메모리에서 쫓겨나는 것을 저장하는 곳을 Backing store라고 부르고 다른 말로는 swap area라고도 부른다.

• Backing store (=swap area)

  • 디스크
    • 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간

• Swap in / Swap out

  • 일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스 선정
  • priority-based CPU scheduling algorithm
    • priority가 낮은 프로세스를 swapped out 시킴
    • priority가 높은 프로세스를 메모리에 올려놓음
  • Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야 함
  • Execution time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음
  • swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)임

스와핑은 프로세스를 메모리에서 통째로 (하드디스크로) 쫓아내는 것

Schematic View of Swapping

메모리에서 통째로 쫓겨나서 하드디스크 backing store로 내려가는 거를 우리가 swap out라고 부르고 backing store로 쫓겨났던게 메모리로 다시 올라오는 것을 swap in이라고 부른다.

스와핑하고 관련해서는 중기 스케줄러가 바로 swap out 시킬 프로그램을 결정하는 역할을 하고 있다. 그래서, 중기 스케줄러를 다른 말로 swapper라고도 불렀었다.
즉, 메모리에 너무 많은 프로그램이 올라와있으면 시스템이 굉장히 비효율적이 되기 때문에 중기 스케줄러가 일부 프로그램을 골라가지고 통째로 메모리에서 디스크로 쫓아내는 그런 일을 하게 되는데, 그게 스와핑의 개념과 연결되있는 그런 얘기라는 것이다.

그러면 중기 스케줄러는 보통 어떤 프로그램을 메모리에서 쫓아내느냐? CPU 우선 순위가 낮은(CPU 수행 가능성이 낮은) 프로그램을 쫓아내는게 좋을 것이다. 당장 CPU를 얻어야 될 프로그램은 메모리에 올라와있는게 좋으니까…

이 스와핑 시스템이 지원이 되기 위해서는 앞에 바인딩하고 연결해서 생각을 좀 해봐야 된다.

만약에, 컴파일 타임 바인딩이나 로드 타임 바인딩이 사용이 되고 있다면, 스와핑에서 쫓겨났다가 메모리로 올라올 때는 원래 위치로 올라와야될 것이다.(500번지에서 쫓겨났으면 500번지로 올라와야되고…다른 메모리 영역이 비어있더라도 반드시 500번지로 올라와야되고) 이렇기 때문에 사실 스와핑의 효과를 십분 발휘하기는 어려울 것이다.
그래서, 스와핑이 좀 더 효율적으로 동작을 하려면 런타임 바인딩이 지원이 되어야 될 것이다. 즉, 300번지부터 올라와있던 프로그램이 스왑 아웃을 당해서 쫓겨났으면 나중에 메모리에 올라갈 때 다른 위치로도 비어있다면 올라갈 수 있게 해주는 그런 방법이 지원이 되는게 좋겠다는 것이다.

스와핑이 좀 더 효율적으로 사용이 되려면 런타임 바인딩이 지원이 되는 것이 좋겠다는 얘기이다.

메모리에서 프로그램을 통째로 쫓아내고, 다시 올려놓고 이런 일은 상당히 방대한 양이 한꺼번에 쫓겨났다가 다시 올라오는 일이기 때문에(그냥 파일 입출력하고 다르게 양이 굉장히 많다), 이런 디스크 접근하는 시간의 대부분이 Transfer time 즉, 스왑되는 데이터 양에 비례하는 그런 시간이다.
우리가 디스크를 접근하는 시간은 (뒤에 하드디스크 스토리지 관리 부분에서 배우겠지만) seek time(탐색시간)이라고 해서 디스크 헤드가 이동하는 시간이 거의 대부분을 차지한다. 그리고 실제로, 데이터를 전송하는 transfer time은 굉장히 미미한 시간 규모를 차지하고 있다.
그렇지만, 용량이 이렇게 방대한 스와핑 시스템에서는 seek time도 중요하지만 양이 워낙 많기 때문에 transfer time도 상당 부분을 차지하고 있다라는 설명을 하기 위해서 이런 얘기를 하는 것이다.

지금 설명한 스와핑은 프로그램이 메모리에서 통째로 쫓겨나는 것을 우리가 스와핑이라고 부르고, 원래 본연의 스와핑의 의미가 이게 맞다.
그렇지만, 이것도 최근에는 우리가 페이징 시스템에서 프로그램 전체가 쫓겨나는게 아니라 프로그램 주소 공간이 잘게 잘려져가지고 일부 페이지가 메모리에서 쫓겨나고, 일부 페이지는 또 올라오고 이런식으로 다 쫓겨나는게 아니라 일부 페이지만 쫓겨나는 것 마저도 그 페이지가 스왑 아웃 됐다. 이런식의 표현을 쓰기도 한다. 그러니까, 메모리에서 프로그램 다 쫓겨나는게 아니라 일부 구성하는 페이지만 쫓겨나는 그런 것도 우리가 스왑 아웃됐다라는 말을 쓰기도 하지만…
원칙적인 원래의 스와핑의 개념은 스왑 아웃된다고 하면 프로그램을 구성하는 그 주소 공간이 전부 다 쫓겨나는 것을 스왑 아웃이라고 부르고 그래서 중기 스케줄러하고 연동되서 설명을 하는 것이다.

Dynamic Linking

• Linking을 실행 시간(execution time)까지 미루는 기법
• Static linking
  • 라이브러리가 프로그램의 실행 파일 코드에 포함됨
  • 실행 파일의 크기가 커짐
  • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비 (eg. printf 함수의 라이브러리 코드)
• Dynamic linking
  • 라이브러리가 실행시 연결(link)됨
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
  • 운영체제의 도움이 필요

Linking이 뭐냐하면 우리가 프로그램을 작성한 다음에 보통 컴파일하고, 그 다음에 링크해서 실행파일을 만들게 되는데… 여러 군데에 존재하던 컴파일된 파일들을 묶어가지고 하나의 실행파일을 만드는 과정을 말한다.

내가 소스 파일을 여러개 따로 코딩을 해가지고 linking을 하기도 하고, 또는 내가 작성하지 않은 함수지만 워낙 유용한거라서 누군가가 만들어놓고 필요할 때 내가 불러다쓰는 라이브러리들도 결국에는 linking이 되서 실행파일이 만들어지면 내 코드 안에 그 라이브러리 코드가 보통 포함이 되는 개념. 그런식으로 linking이 되는걸 우리가 Static linking이라고 부른다.
예를 들어, 내가 프로그램을 만들면서 printf라는 라이브러리 함수를 사용해서 프로그래밍을 했다고 가정하자. 근데, printf라는 함수가 Static linking이 이루어지게 되면 내가 만든 실행파일 안에(비록 printf라는 함수는 내가 만든 코드는 아니지만 내 프로그램 실행파일 안에) printf의 코드가 이미 포함이 되있는 것이다. 그래서, 실행시키면 내가 만든 코드든 라이브러리 코드든 구분 없이 내 프로그램 주소 공간 안에서 그냥 실행이 되는 것이다. 만약에, 개발자 100명이 각각 printf를 이용해서 프로그래밍을 하고, 그것을 실행파일로 만든 다음에 그 프로그램 100개를 실행시키게 되면 비록 printf라는 같은 기능을 하는 코드라 하더라도 그 코드가 100 카피가 메모리에 올라갈 것이다. 왜냐하면, 별도의 프로그램에 속하는 것이기 때문에… 이게 Static linking의 개념이다.

반면에, 여기서 얘기하는 Dynamic linking은 라이브러리 코드가 내 실행파일 안에즉, 컴파일해서 실행파일이 만들어질 때 포함이 되지 않고, 포함이 되지 않은 상태로 남아 있다가 실행을 시키게 되면 프로그램이 실행되다가 라이브러리 호출하는곳에 도달하면 (내 코드 안에 라이브러리 코드가 안들어있기 때문에) 라이브러리를 찾아야 될 것이다. 라이브러리를 어디서 찾을 것이냐…?
그래서, Dynamic linking은 내 코드 안에다가 실행파일 만들 때 라이브러리를 집어넣는 것이 아니고 실행파일에는 이 라이브러리가 별도의 파일로 존재하고, 그 라이브러리가 어디있는지 (위치)를 찾을 수 있는 stub이라는 작은 코드(소위, 포인터)만 내 실행파일 안에 두고 라이브러리 자체는 포함을 안시켜놓는다.
Dynamic linking을 쓰게 되면, 프로그램이 실행되다가 라이브러리 호출하는 곳에 이르면 그 라이브러리가 어디에 있는지를 찾는다.(별도의 파일 형태로 보통 Dynamic linking이 되는 라이브러리가 존재하는데 그런 라이브러리를 찾아가지고) 필요하면 메모리에 올리고, 또는 이미 메모리에 올라와있다면 그 주소로 가서 해당 라이브러리를 실행을 하게 된다는 것이다.
예를 들어, 내가 printf를 사용해서 프로그래밍을 했는데 이 printf함수의 코드가 내 실행파일에 들어가지 않고, 그냥 printf라는 기능을 실행할 수 있는 라이브러리가 어디에 있는지 위치를 찾는 코드만 내 프로그램 안에 집어넣어 놓는 것이다. 그래서 실행이 되면…, 개발자 100명의 코드가 printf를 써서 프로그래밍을 했는데, 그게 Dynamic linking을 사용한다 그러면 프로그램이 실행이 될 때 printf를 호출하는 지점에 이르면 자기 프로그램 안에는 해당 코드가 없다. 그래서, printf코드에 해당하는 라이브러리 파일을 찾아서 그거를 메모리에 올려서 실행을 하는 것이다. 만약 이때 개발자 100명이 printf를 사용해서 다른 사용자에 의해서 printf에 Dynamic linking되는 라이브러리가 이미 메모리에 올라와있다면 추가로 올릴 필요가 없이 올라와있는 라이브러리를 같이 공유해서 사용을 할 수가 있는 것이다.
그래서, 이 Dynamic linking을 해주는 라이브러리를 shared library라고 부른다. 리눅스 같은 환경에서는 shared object라고 부르고, 윈도우 같은 환경에서는 dll이라는 확장자를 가진 파일이 있다.(* dll은 dynamic linking library의 약자. Dynamic linking을 하는 shared library 파일)

지금부터는, 물리적인 메모리를 어떻게 관리할 것인가? 에 대해 설명한다.

Allocation of Physical Memory

• 메모리는 일반적으로 두 영역으로 나뉘어 사용
  • OS 상주 영역
    • interrupt vector와 함께 낮은 주소 영역 사용
  • 사용자 프로세스 영역
    • 높은 주소 영역 사용
• 사용자 프로세스 영역의 할당 방법
  • Contiguous allocation(연속 할당)
    : 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
    • Fixed partition allocation
    • Variable partition allocation
  • Noncontiguous allocation(불연속 할당)
    : 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
    • Paging
    • Segmentation
    • Paged Segmentation

＊그림: 물리적인 메모리를 보여주는 그림
물리적인 메모리는 낮은 주소 부분에 운영체제 커널이 항상 상주하고 있고, 높은 주소 영역에는 사용자 프로그램들이 올라가 있게 된다.
이 사용자 프로그램이 올라갈 이 영역을 관리할 방법을 크게 두 가지로 나눠볼 수 있다. 첫번째는 Contiguous allocation(연속 할당)이고, 두번째는 Noncontiguous allocation(불연속 할당)이다.

프로그램이 메모리에 올라갈 때 통째로 메모리에 올라가는 방법이 연속 할당이다.

(맨 앞에서부터 설명했던 것들이 사실은 지금까지 연속 할당에 대해서 설명을 한 것이었음) p1이라는 프로그램이 메모리에 올라가면 그림과 같이 한 군데에 통째로 올라가기 때문에 주소 변환도 비교적 간단했다. 시작 주소만 더해주면 되는 방식… 이런게 연속 할당에 의한 메모리 관리 기법인 경우에 그런 것이다.

반면에, 두번째에 나와있는 불연속 할당은 프로그램을 구성하는 주소 공간을 잘게 쪼개가지고 일부는 저쪽에 올라가있고, 일부는 이쪽에 올라가있고 그게 가능해지는 방법이 불연속 할당이라는 것이다.
그래서, 현대의 시스템에서는 당연히 불연속 할당을 쓰고 있고, 그 중에서도 프로그램의 주소 공간을 같은 크기의 페이지로 잘라가지고 페이지 단위로 메모리 여기저기 올라가기도 하고 내려가기도 하고 그런 방법을 쓰고 있는데, 그게 페이징 기법이라는 것임.

Contiguous Allocation(연속 할당)

• Contiguous allocation
  • 고정 분할(Fixed partition) 방식
    • 물리적 메모리를 몇 개의 영구적 분할(partition)로 나눔
    • 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
    • 분할당 하나의 프로그램 적재
    • 융통성이 없음
      • 동시에 메모리에 load되는 프로그램의 수가 고정됨
      • 최대 수행 가능 프로그램 크기 제한
    • Internal fragmentation 발생 (external fragmentation도 발생)
  • 가변 분할(Variable partition) 방식
    • 프로그램의 크기를 고려해서 할당
    • 분할의 크기, 개수가 동적으로 변함
    • 기술적 관리 기법 필요
    • External fragmentation 발생

연속 할당도 크게 2가지로 또 나눠 볼 수 있다. 바로 고정분할 방식하고, 가변분할 방식이라는 것이다.

위 그림 좌측을 보면, 고정 분할 방식이라는 것은 프로그램이 들어갈 사용자 메모리 영역을 미리 파티션으로 나누어놓는 것이다.
그리고, 가변 분할 방식은 그림 우측과 같이 사용자 프로그램이 들어갈 메모리 영역을 미리 나눠놓지 않는 것이다.

고정 분할 방식 먼저 설명…
이 메모리 관리 기법에서는 지금 사용자 프로그램이 들어갈 물리적인 메모리를 분할 4개로 미리 나누어 놓았다. 분할의 크기를 균일하게 만들어 놓을 수도 있고, 그림과 같이 가변적으로 만들어 놓을 수도 있다. 이런 상황에서 프로그램 A가 실행이 되면 프로그램 A의 크기가 마침 그림과 같은 크기다. (지금은 연속 할당이기 때문에 통째로 메모리에 올려놓는 상황이다) 프로그램 A의 크기가 그림과 같다면 크기가 똑같은 분할 1에다가 이 프로그램 A를 올려놓으면 될 것이다.
그 다음에, 프로그램 B가 실행이 되려고 하는데, 프로그램 B는 크기가 그림과 같다. 그런데 프로그램 B의 크기는 지금 분할 2의 크기가 더 작기 때문에 분할 2에 들어갈 수가 없다. 그래서 프로그램 B는 분할 3에 들어가게 된 것이다. 그러면, 여기서 이제 낭비되는 메모리 조각이 발생하는데, 그 낭비되는 메모리 조각을 외부 조각하고, 내부 조각이라는 용어로 나누어서 이야기를 한다.

• External fragmentation (외부 조각)
  • 프로그램 크기보다 분할의 크기가 작은 경우
  • 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할
• Internal fragmentation (내부 조각)
  • 프로그램 크기보다 분할의 크기가 큰 경우
  • 하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각
  • 특정 프로그램에 배정되었지만 사용되지 않는 공간

외부 조각이라는건 뭐냐하면, 내가 지금 이 프로그램 B를 메모리에 올리고 싶은데, 올리려는 프로그램보다 분할 2라는 메모리 조각의 크기가 더 작다. 그래서, 사용이 안됐다. 프로그램이 들어갈 수 있는 공간임에도 불구하고 조각이 너무 작아서 사용이 안된 이러한 공간을 외부 조각이라고 부른다.
그 다음에 프로그램 B의 크기가 분할 3의 크기보다 작다. 그래서, 분할 3에다가 프로그램 B를 넣어놨지만, 그 안에서 지금 남는 메모리 조각이 있다. 이것은 지금 프로그램 B한테 할당이 된 공간이지만 사용은 안되는 공간이다. 그래서 이거를 내부 조각이라고 부른다.
지금은 외부 조각으로 분류를 해놓았지만, 나중에 또 아주 작은 프로그램이 등장해서 거기에 그 프로그램이 외부 조각이 있는 위치에 들어가면 그것은 외부 조각은 아닌것이다. 그리고, 거기에서 남는 공간이 있다면 남는 공간은 내부 조각이 되는 것이다. 이런식으로 그때그때마다 그 조각에 대한 해석이 달라질 수 있다.

그래서, 고정 분할 방식은 이런식으로 분할이 작아서 생기는 문제가 있고, 프로그램 크기하고 분할의 크기가 맞지 않아서 생기는 이런 내부 조각의 문제가 발생할 수 있다는 것이다.

그러면 굳이 이렇게 분할의 크기를 미리 나눠놓을 필요가 있겠는가?
그래서, 가변 분할 방식은 프로그램이 실행될 때마다 차곡차곡 메모리에 올려놓는 방법이다. 그래서 운영체제가 그림과 같이 올라가있고, 프로그램 A, B, C가 순서대로 실행이 된다고하면, 그 프로그램들을 메모리에 차곡차곡 그림과 같이 순서대로 그냥 올리는 것이다.
이렇게 올려놓고 실행이 되다가 만약에 프로그램 B가 끝나면 프로그램 B가 있던 공간이 빈 공간이 되고, 그 다음에 프로그램 D가 실행이 되는데 프로그램 D는 크기가 그림과 같다면 프로그램 D는 프로그램 B가 들어갔던 공간이 더 작기 때문에(지금 연속 할당 상황이기 때문에) 못들어간다. 그래서 프로그램 D는 아래쪽 빈 공간에 들어가게 되는 것이다.
그러면, 프로그램 B가 실행이 끝난 공간은 아무도 사용 안하는 공간인데도 프로그램 크기보다 비어있는 공간의 크기가 작아서 사용이 되지 못했다. 이런 것은 외부 조각이라고 말할 수 있다. 즉, 가변 분할 방식을 쓰더라도 프로그램 크기들이 균일하지 않기 때문에 프로그램이 실행되고 종료되고, 또 새로 실행되고 이러다보면 중간중간에 이러한 외부 조각이 생길 수 있다는 것이다! (가변 분할 방식에서 내부 조각은 생기지 않는다)

연속 할당은 고정 분할 방식과 가변 분할 방식으로 나누어볼 수 있고, 각각의 방법은… 특히, 고정 분할 방식은 굉장히 융통성이 없이 미리 분할 즉, 파티션을 나누어 놓는 방법이기 때문에, 내부 조각이나 외부 조각이 발생할 수가 있다는 것이고,
가변 분할 방식은 그때그때 프로그램을 차곡차곡 쌓아서 메모리에 올리지만 그렇게 하더라도 중간중간에 프로그램이 실행되고 종료되고 하면, 메모리에 구멍(hole)이 뚫리게 되는데… 그런 외부 조각들이 생길 수가 있다는 것이다.

• Hole
  • 가용 메모리 공간
  • 다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있음
  • 프로세스가 도착하면 수용가능한 hold을 할당
  • 운영체제는 다음의 정보를 유지
    a) 할당 공간 b) 가용 공간 (hole)

그래서, 위 그림과 같은 가변 분할 방식을 쓰게되면, 프로그램(process 8)이 실행되다가 종료가 되면 구멍이 생기고, 또 새로운 프로그램(process 9)이 실행되면 구멍이 작아지고, 또 새로운 프로그램(process 10)이 실행되면 구멍이 작아지고… 중간에 또 종료가 되면 이렇게 작은 hole들…(여기서 가용 메모리 공간(비어있는 메모리 공간)을 Hole(구멍)이라는 용어로 사용했는데) 이런 hole들이 여기저기 산발적으로 생기게 된다는 것이다.

그러면, 운영체제는 이 물리적인 메모리에서 어느 부분은 프로그램에 의해서 지금 사용이 되고 있고, 어느 부분은 비어있는 hole이고… 이런거를 따로따로 관리를 하고 있어야 될 것이다. 그랬다가 프로그램이 종료가 되면 할당됐던 공간을 hole에다가 편입을 시키고, 또, 새로운 프로그램이 실행되면 hole 중에서 적당한 위치에다가 그 프로그램을 집어 넣어야 될 것이다.

그러면, 프로그램이 실행될 때 hole이 여러 군데 있을텐데, 이 hole(가용 메모리 공간) 중에서 어디다가 새로운 프로그램을 집어 넣을 것인가? 그걸 결정해야되는 문제가 있다.
그 문제를, 우리가 특별히 가변 분할 방식에서 생기는 Dynamic Storage-Allocation Problem(또는, Dynamic Memory-Allocation Problem)이라고 부른다.

Dynamic Storage-Allocation Problem
: 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제

• First-fit

  (홀 중에서 제일 처음 발견되는 홀에다가 집어 넣음)
  (홀들을 다 살펴볼 필요가 없다. 그냥 찾다가 들어갈 수 있으면 아무데나 제일 처음 발견되는데 집어넣는 방법이니까…)

  • Size가 n 이상인 것 중 최초로 찾아지는 hole에 할당

• Best-fit

  (홀을 다 살펴 본 다음에 프로그램 크기하고 가장 잘 맞는 홀에다가 프로그램을 올려놓는 것)
  (따라서, 홀들을 탐색하는 시간 부담이 좀 있다.)

  • Size가 n 이상인 가장 작은 hole을 찾아서 할당
  • Hole들의 리스트가 크기 순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야함
  • 많은 수의 아주 작은 hole들이 생성됨

• Worst-fit

  (가장 큰 홀에다가 프로그램을 할당하는 방법)
  (왜 제일 어리석은 방법이라고 하냐? 면, 큰 홀에는 나중에 더 큰 프로그램이 들어갈 수도 있다 그런데, 지금 실행되려는 프로그램이 들어갈 수 있는 적합한 홀이 있을텐데도 제일 큰 홀을 이번에 써서 작은 홀로 만들어 버리는 것이기 때문에…)

  • 가장 큰 hole에 할당
  • 역시 모든 리스트를 탐색해야함
  • 상대적으로 아주 큰 hole들이 생성됨

＊ First-fit과 best-fit이 worst-fit보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려짐 (실험적인 결과)

지금 실행하려는 프로그램의 크기가 n인데, 지금 hole이 여러개 있다. 그러면, 어느 홀에다가 사이즈 n인 프로그램을 넣어야되느냐? 하는건데… 적어도 홀의 크기가 프로그램 크기 n보다는 커야 할 것이다(프로그램 크기 n이상은 되어야 할 것이다).
어디다가 이 프로그램을 집어넣어주는게 좋겠는가?
이 방법은 크게 First-fit, Best-fit, Worst-fit 3가지 방법의 알고리즘으로 여기서 얘기를 하고 있다.

Dynamic Storage-Allocation Problem에서 사용하는 프로그램이 들어갈 홀 위치를 결정하는 방법 이 3가지를 많이 얘기하는데, 실험적으로 살펴보니까, First-fit이나 Best-fit방법이 Worst-fit보다는 더 속도나 공간 이용률 측면에서 더 효과적인 것으로 알려져있다.(당연한거겠지만…)

First-fit은 홀을 찾는 오버헤드가 적어서 좋은 것이고, Best-fit은 가장 적당한 홀을 찾아서 넣기 때문에 미래를 위해서 조금 더 좋은 방법 되시겠다.

그 다음에… 이런식으로 홀만 찾아넣게 되면 그래도 중간중간에 작은 홀들이 많이 생길텐데,

이런 홀들을 묶어서 즉, 사용 중인 메모리 공간을 한 군데로 밀어서 홀을 한 군데 몰아놓을 수 있다. 그런 방법을 compaction이라고 부른다.

• compaction
  • external fragmentation 문제를 해결하는 한 가지 방법
  • 사용 중인 메모리 영역을 한 군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것
  • 매우 비용이 많이 드는 방법임
  • 최소한의 메모리 이동으로 compaction하는 방법 (매우 복잡한 문제)
  • Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다

즉, 외부 조각으로 생기는 홀들을 갖다가 한 군데로 밀어가지고, 아주 큰 홀을 만들면 홀의 크기가 작아서 사용이 안되는 외부 조각 문제를 해결할 수가 있다. 그렇게 하는 것을 compaction이라고 하는데…
디스크 조각 모음은 디스크에 있는 파일의 데이터를 이동시키는 방법임에 비해서 compaction은 메모리에 올라가서 실행 중인 프로그램의 메모리 영역을 한 군데로 미는 작업이기 때문에, 그렇게 호락호락한 방법은 아니다. 매우 비용이 많이 드는 작업이다. 바인딩을 다 점검해야되는 문제가 있기 때문에…(프로그램 하나에만 영향을 미치는게 아니라 전체 프로그램의 바인딩과 관련된 문제이기 때문에 생각보다는 비용이 많이드는 복잡한 방법이다.)
그리고, 아무때나 할 수 있는건 아니고, 적어도 런타임 바인딩이 지원이 되어야지만(즉, 메모리 위치가 실행 중에도 변경될 수 있는 그런 기능이 지원 되어야지만) compaction을 할 수가 있다 애초부터.

그래서, compaction을 꼭 한 군데만 다 밀어놓는게 좋으냐?
그렇게 하면 좋겠지만 그렇게 하는 것보다, 최소한의 프로그램만을 이동시켜가지고, 큰 홀을 하나 만들 수 있으면 좋을 것이다. 전체를 다 미는 거보다는 아주 작은 이동을 통해서 홀 큰거를 만들 수 있으면 중간에 일부 홀은 존재하더라도 그런 식의 compaction이 보다 효율적일 수가 있다.(그렇게 하는 것 자체도 사실은 어떤 프로그램을 이동시킬 것인가? 결정하는 문제도 간단한 문제가 아니다, 여러가지를 고려해야되는 그런 상황이다)

Noncontiguous Allocation (불연속 할당)

실제로, 현대의 컴퓨터 시스템에서 사용하는 방법은 연속 할당이 아니고, 지금부터 설명할 불연속 할당 방법이기 때문에 연속 할당에서 나오는 문제들로부터 비교적 자유롭다.

불연속 할당 방법은 크게 Paging기법, Segmentation기법으로 나누어볼 수가 있다. (Paged Segmentation은 이 기법을 혼합하는 방법)

위 그림을 보면, 좌측 하단 그림이 하나의 프로그램인데, 페이징 기법은 하나의 프로그램을 구성하는 주소 공간을 같은 크기의 페이지로 자르는 것이다. 같은 크기로 잘라가지고, 페이지 단위로 물리적인 메모리에 올려놓거나 또는 backing store에 내려놓거나, 그렇게 하는게 페이징 기법이다.
하나의 프로그램을 구성하는 주소 공간을 같은 크기의 페이지로 자르는 것처럼, 물리적인 메모리에 사용자 프로그램이 들어갈 수 있는 공간들도 똑같은 크기의 페이지 하나가 들어갈 수 있는 크기로 미리 잘라놓는다. 그거를 페이지 프레임(page frame)이라고 부른다.(frame == 틀) 페이지가 들어갈 수 있는 공간을 의미하기 때문에, 물리적인 메모리의 공간을 우리가 페이지 프레임이라고 부르고, 그리고, 페이지 프레임 하나하나에는 페이지들이 올라갈 수 있는 그런 상황이 되는 것이다.

이런 페이징 기법을 쓰면 우리가 방금 전에 연속 할당 - 가변 분할 방식에서 봤던 문제 즉, 홀들의 크기가 균일하지 않아서 어디다 집어넣을 것인가?, 또는 홀들을 밀어가지고 한 군데로 몰아놓는 이런게 필요가 없다.
왜냐하면, 어차피 물리적인 메모리에서 비어있는 위치가 있으면, 그 비어있는건 페이지 크기인 페이지 프레임이 비어있기 때문에, 이 프로그램의 어떤 페이지든지 비어있는 위치는 아무데나 들어갈 수가 있는 것이다.

그래서, Hole… Dynamic Storage-Allocation Problem 이런 문제가 없어지는게 페이징 기법의 장점이 되겠다.
대신에, 이런 불연속 할당을 쓰게 되면 주소 변환이 복잡해질 것이다. MMU에 의해서 주소 변환을 할 때 단지, 시작 주소만 더해서 주소 변환을 하는 것이 아니고 잘려진 각각의 페이지가 물리적인 메모리의 어디에 올라가 있는지를 확인해봐야된다. 즉, 주소 변환을 페이지 별로 해야되기 때문에 주소 바인딩이 더 복잡해지는게 특징이다.

그 다음에 Segmentation기법은, 프로그램의 주소 공간을 같은 크기로 자르는게 아니라 의미 있는 단위로 자르는 것이다.

대개 이제 프로그램의 주소 공간(프로그램을 구성하는 주소 공간)이라는게(좌측 그림) 전~에 설명했었지만 코드, 데이터, 스택 이러한 크게 3가지 의미있는 공간으로 구성이 된다. 그래서, Segmentation기법은 크게 코드 세그먼트, 데이터 세그먼트, 스택 세그먼트 이렇게 잘라가지고 각각의 세그먼트를 필요시에 물리적인 메모리의 다른 위치에 올려놓을 수 있게 하는 방법이라는 것이다.
우리가 세그먼트라는건 프로그램의 주소 공간을 구성하는 의미 단위라고 했기 때문에 코드, 데이터, 스택이 될 수도 있고, 더 잘게 자를 수도 있다. 우리가 코드 중에도 코드가 함수 여러개로 구성이 되기 때문에 각각의 함수들을 다른 세그먼트로 만들면 세그먼트 수가 많아질 것이다.(그것도 함수라는 어떤 의미 단위이기 때문에…)
그래서, 각각의 함수를 세그먼트로 잘라서 물리적인 메모리에 다른 위치에 올려놓을 수가 있는 것이고, 거기서도 세그먼트 단위로 주소 변환을 해줘야된다.

그런데, 세그먼트라는건 의미 단위로 자르는거기 때문에 크기가 균일하지는 않다. 그래서 우리가 프로그램을 통째로 메모리에 올릴 때, 프로그램 크기가 달라서 발생했던 문제들(연속 할당 - 가변 분할 방식에서 Dynamic Storage-Allocation Problem 문제) 과 같은 문제가 Segmentation기법을 쓰더라도 (크기가 균일하지 않기 때문에) 발생할 수 있다.

뭐 어쨌든… Paging기법과, Segmentation기법은 통째로 메모리에 올리지는 않는다. 그리고, 잘라가지고 산발적으로 올릴 수가 있다. 라는 개념이다.

Paging

• Paging
  • Process의 virtual memory를 동일한 사이즈의 page 단위로 나눔
  • Virtual memory의 내용이 page 단위로 noncontiguous하게 저장됨
  • 일부는 backing storage에, 일부는 physical memory에 저장
• Basic Method
  • physical memory를 동일한 크기의 frame으로 나눔
  • logical memory를 동일 크기의 page로 나눔 (frame과 같은 크기)
  • 모든 가용 frame들을 관리
  • page table을 사용하여 logical address를 physical address로 변환
  • External fragmentation 발생 안함
  • Internal fragmentation 발생 가능

페이징의 기본 개념은 프로세스를 구성하는 주소 공간을 동일한 크기의 페이지로 나누고, 그래서 이 페이지는 일부는 backing store에 있고, 일부는 물리적인 메모리에 올라갈 수가 있게 되고, 그리고 페이지 단위로는 불연속적으로 메모리에 올라갈 수가 있게 되는 것이다.

물리적인 메모리도 페이지 크기로 나누어놓게 되는데, 그거는 우리가 페이지가 들어갈 수 있는 위치, 틀이라고해서 페이지 프레임이라고 부르고, 프로그램의 주소 공간을 동일한 크기로 자른거는 각각을 페이지라고 부른다.
그래서, 운영체제는 비어있는 페이지 프레임이 어디인지를 관리하게 되고, 주소 변환이 페이지 단위로 이루어져야되기 때문에, 단지 레지스터 2개를 이용한 주소 변환이 안되고, 페이징 기법은 페이지 테이블이라는 것을 써서 주소 변환을 하게 된다.
(페이지 테이블이라는 것은 프로그램을 구성하는 주소 공간에 페이지들이 여러개로 구성이 될텐데, 그 각각의 페이지마다 물리적인 메모리 어디에 올라가 있는지를 테이블 안에다가 표시를 해놓는 일종의 배열이라고 보면 된다)
그래서, 같은 크기로 잘라놨기 때문에 External fragmentation은 발생하지 않고, 대신에 Internal fragmentation은 생길 수가 있다. 왜냐하면, 프로그램의 크기가 반드시 그 페이지 크기의 배수가 되리라는 보장은 없기 때문이다. 그런 경우에 페이지 단위로 나누다보면 맨 마지막에 가서는 페이지 하나보다 남는 자투리가 더 작아서 (페이지 안에 포함되지만) 빈 공간이 될 수 밖에 없기 때문에 내부 조각이 약간은 생길 수가 있다는 얘기다.(그렇지만, 페이지 크기를 잘게 썰게 되면 그 내부 조각이라는게 그렇게 영향력이 있지는 않다)

---

Paging Example

페이징 기법은 위 그림과 같이 프로그램을 구성하는 논리적인 메모리를 동일한 크기의 페이지로 잘라서 각각의 페이지 별로 물리적인 메모리의 적당한 위치에 어디든지 비어있는 위치가 있으면 올라갈 수 있게 해주는 방법이다.

페이징 기법에서 주소 변환을 위해서는 페이지 테이블이라는 것이 사용된다. 페이지 테이블이라는 것은 각각의 논리적인 페이지들이 물리적인 메모리에 어디에 올라가 있는가 있는가? 논리적인 페이지도 페이지 번호를 0번부터 3번까지 매겨놨고, 물리적인 메모리에서 페이지가 들어갈 수 있는 공간을 우리가 페이지 프레임이라고 부른다고 했는데, 그래서 이 페이지 프레임도 0번부터 동일한 크기의 페이지로 잘라서 번호를 매겨놨다.
그러면, 이 논리적인 페이지 0번이 물리적인 페이지 프레임 어디에 올라가 있는가? 또, 1번은 어디에 올라가 있는가? 각각의 논리적인 페이지 별로 주소 변환을 하기 위한 테이블이 바로 페이지 테이블이라는 것이다. 그래서, 페이지 테이블은 논리적인 메모리의 테이블의 페이지 갯수만큼 엔트리가 존재하게 된다. 각각의 테이블의 엔트리에는 그 페이지가 몇번 물리적인 프레임에 올라가 있는지를 나타내주고 있다는 것이다.
그래서 여기서는, 0번 페이지는 지금 1번 페이지 프레임에 올라가 있다는 것을 테이블이 알려주고 있고, 3번 페이지 같은 경우는 7번 페이지 프레임에 올라가 있다 이런 얘기다.

주소 변환을 위해서 테이블이라는 것은 순차적으로 검색을 다 할 필요가 없을 것이다. 엔트리의 크기가 미리 정해져있고… 그래서 예를 들어서, n번째 페이지를 주소 변환하고 싶다 그러면, 페이지 테이블에서 위에서부터 n번째 엔트리를 찾아보면 “아~ 그 페이지가 몇번 프레임에 올라가 있구나” 라는 것을 주소 변환을 바로 할 수가 있다.
이런식으로 테이블이나 배열이라는 것은 인덱스를 이용해서 곧바로 접근을 할 수 있는 자료구조이다.

이 구조를 다른 식의 그림으로 그려보면 아래와 같은 식의 그림이 된다. (아래)

Address Translation Architecture

CPU가 논리적인 주소를 주게 되면 이것을 물리적인 메모리 상의 주소로 바꿔야되는데, 페이징 기법에서는 주소 변환할 때 페이지 테이블을 사용한다고 했다. 그래서, 이 주소(logical address)에서 앞 부분(p)이 페이지 번호가 되고, 뒷 부분(d)이 그 페이지 내에서 얼만큼 떨어져있는지를 나타내는 오프셋이 된다.
그래서, 논리적인 페이지 번호(p)에 해당하는 엔트리를 페이지 테이블에서 위에서 p번째 찾아가면 f라는 페이지 프레임 번호가 나온다.
그러면, 논리적인 주소를 물리적인 주소로 바꾸게 되는데, 이거는 단지 논리적인 페이지 번호(p)를 물리적인 (위에서 몇번째 프레임인지를 나타내는)프레임 번호(f)로 바꿔주면 주소 변환이 끝나는 것이다.

페이지 내에서의 오프셋 부분(d)은 주소 변환에서 영향이 없고, 실제로 그 앞 부분에 있는 페이지 번호(p)만 바뀌는.. 이런식으로 주소 변환이 이루어진다는 것이다. (아래 이미지도 참고)

Implementation of Page Table

• page table은 main memory에 상주
• Page-table base register (PTBR)가 page table을 가리킴
• Page-table length register (PTLR)가 테이블 크기를 보관
• 모든 메모리 접근 연산에는 2번의 memory access 필요
• page table 접근 1번, 실제 data/instruction 접근 1번
• 속도 향상을 위해 associative register 혹은 translation look-aside buffer (TLB)라 불리는 고속의 lookup hardware cache 사용

그렇다면, 페이지 테이블이 어디 들어가야 될 것이냐?
우리가 전에 나왔던 기본적인 MMU 기법에서는 레지스터 2개로 주소 변환을 했다.(레지스터는 CPU안에 들어가있는 아주 빠른 장치이다)
근데, 사실 이 프로그램을 구성하는 주소 공간이라는 걸 페이지 단위로 자르는데, 보통 이 페이지 크기가 4KB이다. 그러면 이 프로그램의 주소 공간은 굉장히 크다. 4KB로 자르게 되면 (위 이미지에서는 페이지 테이블의 엔트리가 4개이지만) 실제로는 한 100만개 정도가 필요하다. 그러니까 프로그램 하나의 주소 공간이 100만개의 페이지로 잘린다는 것이다. 그러면, 이 100만개의 엔트리가 CPU안에 레지스터 같은데 들어갈 수 있을까? 못들어간다. 워낙 페이지 테이블을 위해서 많은 용량이 필요하기 때문에…
그리고, 이 페이지 테이블이라는건 각 프로그램마다 페이지 테이블이 별도로 존재 해야 된다는 것이다.(A라는 프로그램의 페이지 테이블이 있어서 주소 변환을 해야되고 또, B라는 프로그램의 페이지 테이블이 있어서 주소 변환을 해야되고…이런식으로)(그래서, 페이지 테이블의 용량이 굉장히 크기 때문에 레지스터에 집어넣을 수도 없고, 그렇다고 메모리 접근을 위한 주소 변환인데 하드디스크 같은데 저장할 순 없을 것이다. 캐시메모리에 들어가기에도 용량이 너무 크다)
그래서 이 페이지 테이블을 어디에 집어넣느냐 하면, 메모리에다가 집어넣게 된다.

그래서 실제로, 메모리를 접근하기 위해서는 주소 변환을 한 다음에 접근을 해야되는데… 주소 변환을 하려면 페이지 테이블을 접근해야되고, 페이지 테이블이 또 메모리에 존재하기 때문에… 결국에는 메모리를 한번 접근하려면 (메모리 접근을 위해서는) 2번의 메모리 접근이 필요한 것이다.
한 번은 페이지 테이블을 통한 주소 변환을 위해서 메모리 접근이 필요하고, 주소 변환이 됐으면 실제로 데이터를 메모리에서 접근하기 위해서 또 메모리 접근이 필요한 것이다.

앞에 레지스터 2개가 기본적으로 있었는데(위 그림 참고), 이 2개의 레지스터가 페이징 기법에서는 어떻게 사용이 되느냐하면, Page-table base register(PTBR)와 Page-table length register(PTLR) 라는 용도로 사용이 된다. 즉, 메모리 상에 페이지 테이블이 어디에 있는지 그 시작 위치를 Page-table base register(PTBR)이라는 레지스터가 가지고 있고, 페이지 테이블의 길이를 Page-table length register(PTLR)이라는 레지스터가 가지고 있어서, 앞에 단지 레지스터 2개를 가지고 주소 변환을 하던 base register(relocation register)하고, limit register가 이제는 주소 변환을 위한 페이지 테이블의 베이스 값하고, 리미트 값을 가지는 용도로 사용이 된다는 것이다.

그래서, 매번 메모리 접근 한 번하려고, 메모리를 2번 접근하는 것은 시간이 2배로 걸리니까 상당히 비용이 큰 것이다. 그러다보니까 이러한 속도 향상을 위해서 별도의 하드웨어를 사용한다. 그것이 바로 assciative register로 구성되는 TLB라는 일종의 캐시인데 이것은 메인 메모리보다 빠른(메인 메모리하고 CPU 사이에 존재하는) 주소 변환을 해주는 계층이라는 것이다.

Paging Hardware with TLB

위 그림을 보면 조금 더 이해가 편할텐데…
그림을 보면 좌측에 CPU가 있고, 가운데 하단에 주소 변환을 위한 page table이 있다. 사실은 이 page table이 물리적인 메모리 안에 있을 것이다.
원래 오리지널 페이징 기법에서는 CPU가 주는 논리 주소에 대해서 메모리 상에 존재하는 페이지 테이블을 통해서 주소 변환을 하고, 그런 다음에 변환된 주소로 물리적인 메모리를 접근하게 되는 것이다. 근데, 이렇게 되면 2번의 메모리 접근이 필요하기 때문에 이 속도를 개선하기 위해서 TLB라는 별도의 하드웨어를 두는 것이다.(컴퓨터 구조 시간에 메인 메모리 윗단에 캐시 메모리가 있다는 것을 봤을텐데, 메인 메모리에서 빈번히 사용되는 데이터를 캐시 메모리에 저장해서 CPU로 부터 더 빨리 접근할 수 있도록 해주는 계층이 있었다. 그러한 캐시 메모리가 있듯이 여기서 메모리 주소 변환을 위한 별도의 캐시를 두고 있는데 그게 바로 TLB라는 계층이다.(데이터를 보관하는 캐시 메모리하고는 조금 용도가 다름. 주소 변환을 위한 캐시 메모리라고 설명을 할 수가 있다.))
이 TLB는 페이지 테이블에서 빈번히 참조되는 일부 엔트리를 캐싱을 하고 있다. 그래서, 페이지 테이블 즉, 메인 메모리보다 접근 속도가 빠른 하드웨어로 구성이 되있고 그래서, CPU가 논리적인 주소를 주게되면 메모리 상에 있는 페이지 테이블을 접근하기 전에 TLB를 먼저 검색해본다. 혹시 주소 변환 정보 중에서 TLB에 저장되있는 정보를 이용해서 주소 변환이 가능한지를 체크해보는 것이다. 그래서 만약 p에 해당하는 엔트리 내용이 페이지 테이블로 가기 전에 TLB에 이미 저장이 되있다고 하면 TLB를 통해서 바로 주소 변환이 이루어질 것이다. 그러면, 바로 주소 변환을 해서 물리적인 메모리로 접근을 하니까 이 경우에는 메모리를 1번만 접근하면 된다. 그리고, TLB에 없는 경우에는 페이지 테이블을 통해서 일반적인 주소 변환을 하고 메모리를 접근하게 되니까 2번의 메모리 접근이 필요한 것이다.

근데, 여기서 주의할게 TLB라는건 페이지 테이블의 정보 전체를 담고 있는게 아니라 일부를 담고 있는거라고 했다.(엔트리가 100만개 되니까 이것을 다 담지 못하고 빈번히 참조되는 엔트리 몇개만을 TLB에 가지고 있다) 그러면, 페이지 테이블에서는 주소 변환을 할 때 페이지 번호가 p면 그냥 위에서부터 p번째 엔트리를 가면 바로 주소 변환이 됐다 f라는 페이지 프레임 번호가 나온다. 그런데, TLB는 이 내용을 전부 가지고 있는게 아니기 때문에 그래서, 여기다가 주소 변환된 프레임 번호f만 보관하고 있다고 주소 변환이 되는게 아닐 것이다. 즉, 논리적인 페이지 번호p하고, 그 다음에 그 p에 대한 주소 변환된 프레임 번호f 이 2개를 쌍으로 가지고 있어야 한다. 그게 일반적인 페이지 테이블하고 차이점이다. 전체를 가지고 있는게 아니기 때문에 논리적인 페이지, 물리적인 페이지 번호의 쌍을 가지고 있어야 되는 것이다.

그리고, 주소 변환을 위해서 TLB의 특정 항목을 검색하는게 아니라 전체를 다 검색해봐야 될 것이다. p라는 페이지에 대한 주소 변환 정보가 TLB에 있는지를 확인해보려면 위에서부터 전체 항목에 대해서 page number p가 있는지를 다 찾아봐야 된다. 그래서 있으면 p가 있고 그거에 대한 주소 변환 정보 f가 있구나 해서 주소 변환이 이루어지고, page number어디에도 없으면 TLB에 없기 때문에 페이지 테이블을 통해서 주소 변환을 해야된다.

그래서, TLB는 특정 항목만 검색하는게 아니라 전체를 검색해야한다. 그러다보니까 전체를 검색하는 시간이 오래걸릴 것이다.

Associative Register

• Associative registers (TLB) : parallel search가 가능
  • TLB에는 page table 중 일부만 존재
• Address translation
  • page table 중 일부가 associative register에 보관되어 있음
  • 만약 해당 page #가 associative register에 있는 경우 곧바로 frame #를 얻음
  • 그렇지 않은 경우 main memory에 있는 page table로부터 frame #를 얻음
  • TLB는 context switch 때 flush (remove old entries)

그런 문제를 막기 위해서 TLB는 보통 parallel search가 가능한(병렬적으로 탐색을 할 수 있는) Associative Register를 이용해서 구현을 하고 있다.

즉, CPU가 페이지 번호 p를 주면 이 p에 해당하는 주소 변환 정보가 있는지를 parallel하게(병렬적으로) 쫙 검색을 해서 어느 한군데 p가 있으면 주소 변환이 바로 이루어지고, 어디에도 없으면(TLB 미스가 나면) 페이지 테이블을 통해서 주소 변환을 해야되는 것이다.

근데, 페이지 테이블을 통한 주소 변환은 앞에서도 말했지만 페이지 테이블의 항목(엔트리)을 전부 탐색할 필요가 없다. 페이지 번호P가 주어지면 배열의 인덱스p를 가지고 위에서부터 p번째 엔트리를 가면 주소 변환이 바로 이루어지기 때문에 이것은 parallel search(병렬적 탐색)나 sequential search(순차 탐색)나 이런게 필요한게 아니고 직접 p번째 엔트리만 가면 주소 변환이 되는 것이다.

그래서, 요약하면 이 2군데에서 실제로 주소 변환을 하기 위한 검색에 차이가 있다는 것이다.

그리고, 페이지 테이블이라는게 각각의 프로세스마다 존재하는 것이다. 프로세스 별로 논리적인 주소 체계가 다르고, 그러면 이것에 대한 주소 변환을 위한 페이지 테이블은 프로세스마다 존재를 해야되는 것이다. 그러면 페이지 테이블의 일부를 담는 TLB도 프로세스마다 다른 정보가 될 것이다.
(논리적인 페이지p에 해당하는 프레임 번호가 f다 라고하면 그것은 이 프로세스에 해당하는 것이라면, 다른 프로세스로 CPU가 넘어가면 페이지 테이블의 주소 변환 정보도 달라진다는 것이다)
그래서, 이 TLB에 있는 정보는 컨텍스트 스위치가 발생할 때 flush를 시켜서 모든 엔트리를 비워야되는 것이다. 프로세스마다 주소 변환 정보가 다르기 때문에 그렇게 해줘야 한다.

그러면, 실제로 메모리 접근 하는 시간이 어떻게 되겠는가?

Effective Access Time

• Associative register lookup time = ε

• memory cycle time = 1

• Hit ratio = α

  • associative register에서 찾아지는 비율

• Effective Access Time (EAT)

  

우리가 TLB를 접근하는 시간을 ε(입실론)이라고 해보면, 보통은 이 TLB 접근하는 시간이 메인 메모리 접근하는 시간인 1보다 훨씬 작을 것이다. 그리고, TLB로부터 주소 변환이 되는 비율을 α(알파)라고 하면 실제로 메모리 접근하는 시간이 어느 정도 될 것인가??
계산을 해보면 위 이미지와 같이 될 것이다.

α의 비율 만큼은(TLB에서 주소 변환 정보가 찾아지는 만큼은) TLB 접근 하는 시간ε하고, (주소 변환이 끝났기 때문에)실제 데이터를 접근하는 메모리 접근 시간1이 걸릴 것이다.
그리고, 주소 변환 정보가 TLB에 없는 경우(1-α의 비율 만큼)그 비율 만큼은 TLB 접근을 해봤는데 TLB에 없었다<miss>. 그러면, 일단 ε이라는 시간이 걸리고, 그 다음에 TLB에 없었으니까 페이지 테이블에 접근해야된다. 메모리 접근 시간 1 들고, 주소 변환 한 다음에 실제 데이터 접근하려고 메모리 접근해야될 것이다. 그러니까 메모리 접근 시간이 2가 걸린다.

그러면, 이것을 계산해보면 2 + ε - α 이런 식이 나오는데, 결과적으로 TLB로부터 주소 변환이 되는 비율 α가 굉장히 높다는 것이다.(거의 1에 가까운 비율이 되기 때문에) ε은 1에 비해서 굉장히 작은 그런 값이 되겠고… 그러면 이2 + ε - α 값이 페이지 테이블만 있을 때 접근하는 시간 2 보다는 훨씬 작은 값이 된다는 것이다.

Two-Level Page Table

2단계 페이지 테이블

아까 봤을 땐 페이지 테이블이 한 단계로 구성되어있었는데, 2단계 페이지 테이블은 위 그림과 같이 페이지 테이블이 두 단계로 존재한다. 안쪽 페이지 테이블과 바깥쪽 페이지 테이블이 있어서 CPU가 논리적인 주소를 주게 되면, 페이지 테이블을 두 단계 거쳐서 주소 변환을 하고, 그 다음에 실제로 메모리 접근을 하게 된다는 것이다.

그러면 도대체 왜 이런 2단계 페이지 테이블을 사용하느냐?
컴퓨터에서는 보통 목적이 2가지이다. 속도를 빠르게 하던지, 공간을 줄이든지… 이 2가지 목적일텐데 그 중에서 어떤 것일까? 일단 속도는 줄어들지가 않는다. outer-page table접근해야되고, 그 다음에 page table접근해서 주소 변환을 하면 한번 페이지 접근하던거를 2번 접근하니까 시간은 더 걸린다.
결국에는 속도는 줄어들지 않는데, 페이지 테이블을 위한 공간이 줄어드는게 바로 2단계 페이지 테이블을 사용하는 목적이다.

• 현대의 컴퓨터는 address space가 매우 큰 프로그램 지원

  • 32 bit address 사용시: 2³² B (4GB)의 주소 공간

    2¹⁰ = K(킬로), 2²⁰ = M(메가), 2³⁰ = G(기가)

    • page size가 4K시 1M개의 page table entry 필요
    • 각 page entry가 4B시 프로세스 당 4M의 page table 필요
    • 그러나, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비됨

→ page table 자체를 page로 구성

→ 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL (대응하는 inner page table이 없음)

현대의 컴퓨터에서는 메모리 주소 체계가 굉장히 크다. 32비트의 address를 사용하고 있고, 최근에는 64비트 address체계까지 사용하고 있다.

위 그림에 보면 (빨간색 표시 해놓은)이 주소라는게 32비트로 구성이 되고, 최근에는 64비트로 구성되는 경우도 있다는 것이다. 일단, 여기서는 32비트 주소 체계를 쓰는 그런 아키텍쳐를 기준으로 설명한다.

이 주소가 32비트면 우리가 32비트로 표현할 수 있는 전체 메모리 논리적인 주소 1개가 얼마일까?
메모리에는 주소가 byte(바이트) 단위로 매겨진다. 맨 위에 0번지는 0번째 바이트고, 제일 아래쪽에 예를 들어서 3000번지라고 하면 거기는 3000바이트째 주소가 된다. 그런데, 주소를 갖다가 32비트를 쓴다고 하면 32비트로 표현 가능한 서로 다른 정보가 몇 가지일까?
(1비트로 표현 가능한 정보가(각각의 비트가 0과 1을 표현할 수 있기 때문에) 2가지이다. 2비트로 표현 가능한 정보는 2² 이므로 4가지, 3비트는 2³이므로 8가지이다) 그러면 주소가 32비트라면 이걸로 표현 가능한 전체 바이트 주소는 서로 다른 바이트 몇 군데를 구분할 수 있느냐?
2³²가지 위치 구분이 가능하다. 즉, 32비트 주소 체계를 쓴다면 메모리 주소가 0번지부터 2³² - 1번지까지 주소를 매길 수가 있다.
그래서, 32비트 주소 체계를 이용해서 표시할 수 있는 메모리 주소는 2³² B(바이트)를 표시할 수 있고, 그러면 각 프로그램이 가질 수 있는 최대 메모리 크기는 4GB가 된다. 4GB까지 표현할 수 있는 이유는 32비트 주소 체계를 쓰기 때문에 그런 것이다.

그런데,

아까 이게(위 그림 빨간 표시 부분) 32비트 주소 체계를 쓰기 때문에 4GB로 표시할 수 있는데, 이 4GB로 표시할 수 있는 총 공간을 페이지 단위로 쪼개는 것이다. 그런데, 각각의 페이지 크기가 4KB라고 말했었다. 그러면 총 4GB의 공간을 4KB짜리로 쪼개면 페이지 몇 개가 나올까? (4GB를 4KB로 나누면) 1M(메가)개(100만개보다 조금 큰 갯수)의 페이지 갯수가 얻어진다.(위 그림에 빨간 표시해놓은 안에서 페이지 개수가 1메가개가 되는 것이다 즉, page 100만개 조금 넘는 수의 페이지 갯수가 되는 것)
그러면, 이 페이지 테이블의 엔트리(위 그림 파란 표시)가 아까 처음에 설명한대로 1메가개.. 100만개 이상의 페이지 테이블 엔트리가 필요할 것이다. 그러면, 결국 이 페이지 테이블도 메모리에 들어가야 되는 것이고, 각 프로그램마다 페이지 테이블이 따로 있는데, 이러한 페이지 테이블을 다 메모리에다가 집어넣으면 공간 낭비가 심하다는 것이다.

그리고, 이 각각의 페이지 엔트리가 보통 한 4바이트 정도로 보면 된다.(엔트리 개수가 1메가개(100만개 이상)인데, 엔트리 하나의 크기가 4바이트 정도 된다는 얘기다)
4MB의 페이지 테이블이 각 프로세스마다 필요하고, 그렇게 되면 굉장히 공간 낭비가 심하기 때문에, 2단계 페이지 테이블을 쓰겠다는 것이다.

근데, 여기서 한 가지 말해야되는게 뭐냐면 이(위 그림 빨간 표시한) 4GB의 전체 메모리 주소 공간 중에서 실제 프로그램이 사용하는 공간은 지극히 일부분이다. 이 4GB의 공간이 다 사용되는게 아니라 프로그램의 주소 공간은 보통 코드, 데이터, 스택 이런식으로 구성이 되는데 제일 윗 부분에 코드하고 데이터가 약간 있고, 제일 아랫 부분에 스택이 있고, 중간에는 사용 안되는 논리적인 주소가 상당 부분을 차지하고 있다는 것이다. 뭐 프로그램에 따라서 조금 다르겠지만 대개 전체 공간에서 상당히 일부분만 사용이 되는데, 그런데 페이지 테이블이라는 것은 이 엔트리를(위 그림에 파란색 표시 해놓은 부분) 중간에 구멍이 있다고해서 빼고 만들 수는 없다. 왜냐하면, 배열이라는 것은 인덱스를 통해서 접근을 하는데 앞에서부터 p번째 페이지를 접근하려면 위에서부터 p번째 엔트리를 접근해야되는데 중간에 사용 안되는 페이지가 있다고해서 거기를 비우고 페이지 테이블을 만들 수는 없기 때문에…
그러다보니까 결국에는, 주소 체계 중에서 상당히 일부분만 실제로 사용됨에도(프로그램이 사용하는 주소 공간은 상당히 일부분임에도), 페이지 테이블 엔트리는 다 만들어져야된다는 것이다.
그래서 이러한 1단계 페이지 테이블을 쓰면 공간 낭비가 심하다는 것이다.

그래서, 만들게 되는게 바로 여기서 소개하고 있는 2단계 페이지 테이블이다.

이 2단계 페이지 테이블은 페이지 테이블이 위와 같이 2단계로 구성이 되있고, 페이지 테이블의 페이지 번호를

위 이미지와 같이 페이지 내에서의 offset부분은 원래부터 존재하던 것이고(이게 더 세분화가 된 것일 수가 있다 사실은), 그리고.. 위에 서울이 있고, 그 밑에 서대문구이런식으로 주소 체계를 하나 더 두는 것처럼 여기서도 그런식으로 한 것이다.
바깥쪽 페이지 테이블에 페이지 번호가 있고, 안쪽 페이지 테이블에 페이지 번호가 있고, 그 다음에 페이지에서 얼만큼 떨어져 있는가 하는 오프셋이 존재를 하는 것이다.

Address-Translation Scheme

그래서, 2단계 페이지 테이블에서의 주소 변화는 이런식으로 논리적인 주소에서 바깥쪽 페이지 테이블outer-page table의 인덱스를 찾을 페이지의 번호(P₁)를 가지고, 위에서 P₁번째 엔트리를 가서 주소 변환 정보를 얻는다. 그럼, 여기서 얻어지는게 뭐냐하면, 안쪽 페이지 테이블page of page table 중에 어떤 페이지 테이블인지를 이 친구(위 그림outer-page table회색칠 부분)가 지정을 해준다.

사실 이 안쪽 페이지 테이블은 굉장히 여러개가 있다. 각각의 바깥쪽 페이지 테이블outer-page table엔트리 하나 당 안쪽 페이지 테이블page of page table이 하나씩 만들어지는 것이다.
그래서, 이 바깥쪽 페이지 테이블의 포인터가 가리키는 것은

안쪽 페이지 테이블이 어떤건지 가리키고 있고, 그게 정해지면 이제 안쪽 페이지 테이블의 페이지 번호(P₂)가 있는데 이걸 이용해서 위에서부터 P₂번째 엔트리를 가면, 물리적인 페이지 프레임 번호를 얻게된다. 그러면, 이 페이지 프레임 번호를 여기에다가(위 그림 빨간 표시한 부분에다가) 덮어씌우면, 그 페이지 프레임이 나오고, (거기서) 페이지 내에서 d번째 떨어진 위치에서 원하는 정보를 찾을 수가 있는 것이다.

이런식으로, 2단계로 주소 변환을 하게 되는 것이다.

Two-Level Paging Example

• logical address (on 32-bit machine with 4K page size)의 구성

  • 20 bit의 page number
  • 12 bit의 page offset

• page table 자체가 page로 구성되기 때문에 page number는 다음과 같이 나뉜다
  (각 page table entry가 4B)

  • 10-bit의 page number
  • 10-bit의 page offset

• 따라서, logical address는 다음과 같다

  

• p₁은 outer page table의 index이고

• p₂는 outer page table의 page에서의 변위(displacement)

근데, 2단계 페이지 테이블에서 1가지 기억해야할게 뭐냐면, 이 안쪽 페이지 테이블(그림 빨간 표시)의 크기가 페이지 크기하고 똑같다. 즉, 안쪽 페이지 테이블은 테이블 자체가 페이지화 되서 페이지 어딘가에 들어가 있게 되는 것이다.
그래서, 페이지 하나 크기가 4KB 라고 했기 때문에, 안쪽 페이지 테이블의 크기는 하나에 4KB가 되는 것이다. 그리고 보통 페이지 테이블의 엔트리 하나의 크기가 4B(바이트)라고 설명했었다. 그러면, 4KB의 안쪽 페이지 테이블에서 엔트리 하나 당 4B씩이라고 하면 엔트리 갯수는 몇개가 될까? 4KB에서 4B 엔트리를 몇 개 집어넣을 수 있느냐? 1K(킬로)개를 집어넣을 수 있다.

그래서, 지금부터 설명할 내용은 (조금 어려운 내용일 수 있다) 32비트의 주소 체계 중에서 페이지 안에서 떨어져있는 오프셋이 몇 비트가 되어야되고, 안쪽 페이지 번호가 몇 비트로 표현돼야되고, 바깥 쪽 페이지 번호가 몇 비트로 표현돼야되는지 그걸 말할 것이다.

위 그림과 같은 것에서 비트 수를 알기 위해서는 제일 안쪽(page offset)부터 차례대로(왼쪽으로) 따라 올라오면 된다. 일단, 페이지 하나의 크기가 4KB이기 때문에 우리가 4KB안에서 바이트 단위로 주소 구분을 하려면 몇 비트가 필요할까? 4KB라는건 2¹²B(바이트)이다.

즉, 이 하나의 페이지 안에서 (어차피 메모리라는건 바이트 단위로 주소가 매겨지기 때문에) 몇번째 떨어져 있는 바이트인지를 구분하기 위해서는 서로 다른 4K (2¹²)위치를 구분하기 위해서 몇 비트가 필요한지를 보면 된다.
우리가 서울시(라는 페이지 하나) 안에 집이 100채가 있다고 하면, 100채를 구분하기 위해서 번지 수를 00번지부터 매기면 99번지까지가 필요할 것이다. 즉, 100채의 집을 구분하기 위해서는 10진수 두 자리면 된다. 만약에, 서울시 안에 집이 10000채가 있다면, 이 집들의 번지를 구분하기 위해서 10진수 4자리가 필요할 것이다. 0000번지부터 9999번지까지 구분하면 되니까… 즉, 10⁴채의 집을 구분하려면 10진수 4자리가 필요하고…
지금은 우리가 4KB.. 2¹²B(바이트)를 구분하기 위해서는 (2진수로 되있는거니까) 12비트가 필요하다는 것이다.

그래서, 페이지 안에서 바이트 단위가 얼마나 떨어져있는지를 구분하는 오프셋을 위해서 12비트가 필요한 것은 그렇게 해서 떨어져 나가는 것이고,
그 다음에 위에 있는 페이지 번호page number부분 32비트 중에서 20비트인데, 이걸 어떻게 안쪽 페이지 번호(p₁)하고 바깥쪽 페이지 번호(p₂) 비트로 나눌 것이냐? 그냥 편하게 10비트씩 공평하게 나누면 계산도 편하고 더 쉬울 것이다. 근데, 그렇게 결정되는 것은 아니고… 아까

이 안쪽 페이지 테이블(빨간 표시)이 페이지화돼서 들어간다고 했다. 즉 이게(빨간 표시) 4KB라는 얘기인데, 그런데 각 엔트리가 4바이트이기 때문에 엔트리 수가 1K가 있다고 했다.

지금 이 안쪽 페이지 테이블의 시작 위치로부터 p₂라는 페이지 번호 값은 이 페이지 테이블(page of page table)에서 위에서부터 몇번째 엔트리인지를 구분하는 숫자이다. 그런데, 안쪽 페이지 테이블 안에 엔트리가 몇개 있느냐하면 1K개가 있다. 그러니까 1K개의 엔트리 위치를 구분하기 위해서 이 p₂는 몇 비트가 되어야 되느냐? 1K는 2¹⁰이다. 그래서 서로 다른 2¹⁰가지 엔트리 위치를 구분하기 위해서 몇 비트가 필요하느냐 10비트가 필요하겠다.

그래서, 이제 이 안쪽 페이지 테이블(p₂)의 엔트리를 가리키는 페이지 번호가 10비트가 되는 것이다. 그러면 전체 32비트에서 12비트, 10비트 빼면 바깥쪽 페이지 테이블을 위한 페이지 번호는 10비트짜리가 만들어질 것이다.

우리가 이걸 바꿔서 32비트 주소 체계를 64비트 주소 체계를 쓴다고 생각해보자. 그런데 페이지 크기는 똑같이 4KB이다. 그리고 2단계 페이지 테이블을 쓴다. 그러면, p₁, p₂, d는 각각 몇 비트가 필요할까? 이것은 각자 생각해보자.
(서로 다른 n개의 정보를 구분하기 위해서는 몇 비트가 필요하냐, n비트로 구분 가능한 서로 다른 위치가 몇 군데냐, 그걸 알면 주소에서 몇 비트가 필요하고

그 다음에 이러한 각각의 위치에서 몇 군데를 가리켜야 되는지를 생각할 수가 있다는 것이다. 여기서는(빨간 표시에서는) 1K군데를 구분해야되는거고, 여기서는(파란 표시에서는) 서로 다른 4K군데를 구분해야되는 것이다. 그래서 빨간색에서는 10비트, 파란색에서는 12비트가 필요한 것이고 그 비트를 전체 주소에서 빼면 맨 앞의 비트는 자동으로 계산이 되는 것이다.)

2단계 페이지를 사용하는 이유가 시간은 더 걸리지만 페이지 테이블을 위한 공간을 줄인다고 처음에 말했었다. 페이지 테이블이 프로그램마다 엔트리가 100만개 이상이 필요하고, 그런데 2단계 페이지 테이블을 쓰면 여전히 안쪽 페이지 테이블의 엔트리는 100만개 이상이 필요하다. 오히려 바깥쪽 페이지 테이블이 하나 더 만들어지기 때문에, 1단계 페이지 테이블을 쓰는 것보다 공간적으로도 사실 손해다.
시간도.. 한번, 두번 거쳐서 주소 변환을 해야되고, 공간도 1단계 페이지 테이블에서 쓰던 엔트리 수가 다 필요하고, 그 다음에 바깥 쪽 페이지 테이블을 위한 엔트리가 또 필요하고… 그러니 시간도 손해, 공간도 손해…
그런데 왜 2단계 페이지 테이블을 쓰게 될까?

그 답이 위와 같이 이렇게 적혀있는데… 이게 뭔 얘기냐면

아까 이 프로그램을 구성하는 이 공간 중에서 상당 부분은 사용이 안된다고 했다. 실제로 사용되는 페이지 수는 몇개 안되는데, 페이지 테이블로 만들 때는 우리가 사용되지 않는 중간에 있는 공간들을 엔트리를 안 만들 수가 없다고 했다. 페이지 테이블이라는 것은 K번째 페이지를 주소 변환하려면 위에서 K번째가서 주소 변환 해야되는데, 중간에 엔트리를 없애버리고 만들면 그런 식의 접근이 안되기 때문에…

그래서, 페이지 테이블의 엔트리는 비록 사용이 안되는 페이지들이 있다해도 Maximum Logical Memory(최대 논리적 메모리)의 크기 만큼 페이지 테이블의 엔트리 수가 만들어져야 한다. 그런데, 2단계 페이지 테이블을 쓰게 되면 그걸 해소할 수 있다. 어떻게 해소를 하느냐 하면…

바깥쪽 페이지 테이블은 전체 논리적인 메모리 크기 만큼 만들어지지만, 실제로 사용이 안되는 주소에 대해서 안쪽 페이지 테이블은 안만들어지고 포인터가 그냥 NULL 상태로 되있는 것이다.
실제로 사용되는 메모리 영역에 대해서만 안쪽 페이지 테이블이 만들어져서 주소를 가리키고 있고, 중간에 사용이 상당히 안되는 많은 주소 공간들에 대해선 바깥쪽 페이지 테이블에서 NULL이 되있고, 안쪽 페이지 테이블이 안만들어지기 때문에… 얼마나 많이 사용이 안되면 2단계 페이지 테이블을 쓰는게 더 메모리 공간이 훨씬 효과적이겠나…??

그래서, 2단계 페이지 테이블을 쓰는 이유는 페이지 테이블의 공간을 줄일 수 있기 때문인데 어떻게 줄일 수 있느냐? 전체 주소 공간 중에서 상당 부분은 실제로 사용이 안되는 공간이기 때문에… 안쪽 페이지 테이블이 만들어지지 않기 때문에 그런 것이다.

Multilevel Paging and Performance

페이지 테이블을 2단계만 쓰는게 아니라, 다단계로 사용을 할 수가 있다.
아무래도, 프로그램의 주소 공간이 굉장히 넓기 때문에 페이지 테이블을 2단계만 쓰는게 아니라 3단계, 4단계 이런식으로 점점 더 여러 단계의 페이지 테이블을 사용하는게 가능하다.

• Address space가 더 커지면 다단계 페이지 테이블 필요

• 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요

• TLB를 통해 메모리 접근 시간을 줄일 수 있음

• 4단계 페이지 테이블을 사용하는 경우

  • 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns이고

    (TLB가 접근 시간이 더 빠르니까…)

  • TLB hit ratio가 98%인 경우(TLB를 통해서 직접 주소 변환이 되는 비율이 98%인 경우)
    effective memory access time = 0.98 x 120 + 0.02 x 520 = 128 nanoseconds.

  • 결과적으로 주소 변환을 위해 28ns만 소요

    우리가 메모리 접근하는 시간이 100ns 이기 때문에, 주소 변환을 위해서는 28ns만 추가적으로 더 든 것이다.

이렇게 하면, 테이블을 위한 공간을 더 많이 줄일 수가 있는데, 그렇지만 한번 주소 변환을 하려면 페이지 테이블을 여러번 거쳐야되고, 페이지 테이블이라는게 물리적인 메모리 상에 있기 때문에 메모리를 한번 접근하기 위해서…
예를 들어서, 4단계 페이지 테이블이라고 하면 주소 변환을 위해서 메모리를 4번 접근해야된다. 페이지 테이블이 메모리에 있기 때문에… 그리고 주소 변환을 한 다음에 실제 원하는 데이터를 접근하기 위해서 또 메모리 접근을 해야되고.. 즉, 4단계 페이지 테이블이면 메모리 1번 접근하려면 메모리 5번의 접근이 필요하다.(4번 = 주소 변환, 1번 = 실제 데이터 접근)

그래서 예를 들어서, 메모리 접근 시간이 100ns다. 그러면 4단계 페이지 테이블을 사용하면 500ns가 걸릴 것이다. 이것은 굉장히 시간 오버헤드가 큰 것이다. 그런데, 우리는 앞에서 TLB라는 것을 배웠다. TLB라는 것은 주소 변환을 전담해주는 일종의 캐시 메모리라고 설명했다. 그래서, 4단계 페이지 테이블을 사용하면 시간이 오래 걸릴 수가 있지만, 대부분의 주소 변환은 이 TLB를 통해서 직접 이루어지기 때문에 사실은 이런 다단계 페이지 테이블을 사용하더라도 시간이 지나치게 오래 걸리지는 않는다는 것을 위 계산을 통해서 보여주고 있는 것이다.

Valid (v) / Invalid (i) Bit in a Page Table

Valid (v) / Invalid (i) Bit in a Page Table
왼쪽 : 프로그램마다 주어지는 논리적 메모리(Logical Memory) 오른쪽 : 물리적 메모리(Physical Memory) 우리가 페이지 테이블을 통해서 주소 변환을 하는 모습임

지금까지 보여줬던 페이지 테이블에는 논리적 메모리에 있는 페이지 갯수만큼 페이지 테이블에 엔트리가 존재하고, 그 엔트리에는 이 페이지가 물리적 메모리에 어떤 페이지 프레임에 올라가있는지 페이지 프레임 번호(주소 변환 정보)가 들어 있다까지 말했는데, 사실은 페이지 테이블에 주소 변환 정보만 들어있는 것이 아니고 부가적인 비트가 더 엔트리마다 같이 저장이 되고 있다. 그 중에 하나가 위 그림에 표시되있는 valid-invalid bit이라는 것이다. 그래서 그림을 보면 비트가 v(valid)로 표시된 엔트리가 있고, 그 다음에 i(invalid)로 표시된 엔트리가 있다.

우리가 어차피 메모리에 의미있는 값을 집어넣든 집어넣지 않든 간에 페이지 테이블에 있는 0과 1의 조합은 숫자로 해석이 될 것이다. 위 그림에서는 페이지가 5번까지 있다.. 6번, 7번은 이 프로그램이 지금 사용하지 않는 페이지라는 것인데, 그런데도 불구하고 페이지 테이블에 6번, 7번 엔트리가 존재한다.

왜 그렇다고 설명했었냐하면, 프로그램의 주소 공간이 가질 수 있는 최대 사이즈 만큼 이 페이지 테이블 엔트리는 생겨야된다고 했다. 프로그램이 사용하는 페이지 갯수가 있지만 앞에서 설명했었듯이 예를 들어, 32비트 주소 체계를 쓰게 되면, 페이지가 최대 1메가개가 존재할 수가 있고, 그러면 상위 부분에 코드, 데이터를 구성하는 페이지가 있고 아주 아랫쪽에 스택을 구성하는 페이지가 있고, 중간에 사용되지 않는 주소 영역이 굉장히 많이 존재한다고 했다. 그렇지만, 페이지 테이블 엔트리에는 그런 사용되지 않는 영역을 위해서도 엔트리가 만들어져야 된다고 했다. 그 이유는 테이블이라는 자료구조 특성상 위에서부터 인덱스를 통해서 접근을 해야되기 때문에… 그래서 모든 엔트리가 다 만들어져야되고… 여기서도 6번, 7번 페이지는 없지만 이 주소 체계에서는 6번, 7번 테이블이 만들어지고 대신에 사용이 되지 않기 때문에 valid-invalid bit이 i(invalid)로 표시가 되있는 것이다.

페이지 테이블 그림(6번, 7번)에 0이라고 표시를 해놓긴 했지만, 사실은 이게 정말 0번 페이지 프레임을 말하는지, 아니면 이 페이지에 대한 정보가 의미가 없는건지 그걸 valid-invalid bit을 통해서 표시를 해놓는다는 것이다.

그래서, 사실은 valid-invalid bit에서 v(valid)라는 것은.. 예를 들어, 0번 페이지 테이블 엔트리에 가면, 거기가 v(valid)라고 표시되있다고 하면 0번 페이지가 2번 프레임에 실제로 올라와있다는 얘기다.
5번 페이지 테이블 엔트리에서도 5번 페이지가 9번 페이지 프레임에 v(valid)니까 실제로 올라와 있다는 뜻이다.
반면에, i(invalid)라는 것은 이 페이지가 이 프로그램에 의해서 아예 사용이 되지 않거나, 또는 여기서 표시는 안되있지만 이 페이지가 항상 메모리에 올라가있지는 않을 수도 있다. 이 중에서 당장 필요한 것은 물리적인 메모리에 올라가있게 될 것이고… 당장 필요하지 않은건 하드디스크의 Backing Store에 내려가 있을 것이다. 그런 경우에, 이 페이지에 대한 주소 변환을 시도하게 되면, 물리적인 메모리 프레임에는 아무데다 올라가 있지 않을 것이다. 그런 경우에 i(invalid)라고 표시를 해놓는 것이다.

Memory Protection

• Page table의 각 entry 마다 아래의 bit를 둔다
  • Protection bit
    • page에 대한 접근 권한 (read/write/read-only)
  • Valid-invalid bit
    • “valid”는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함 (접근 허용)
    • “invalid”는 해당 주소의 frame에 유효한 내용이 없음^을 뜻함 (접근 불허)

invalid는 2가지의 의미가 있다. 프로세스가 아예 그 주소 부분을 사용하지 않거나 또는 이 페이지가 물리적인 메모리에 올라와있지 않고, backing store 즉 swap area에 있는 경우

그 다음에 Valid-invalid bit 말고, 페이지 테이블 엔트리 당 또다른 bit이 하나 더 저장되는게 있는데 그게 바로 Protection bit이라는 것이다.

보통 Protection이라고 하면 보안을 목적으로 하는 bit이다 이렇게 생각할 수 있을 것이다. 내가 접근해서는 안될 페이지를 접근하지 못하게 하는 권한을 가진.. 이런걸 보통 Protection이라고 하는데, 여기서는 그런 얘기는 아니다.
페이지 테이블이라는게 어차피 프로세스마다 독립적으로 존재하기 때문에 이 프로세스의 페이지 테이블을 접근했으면 결국, 본인의 페이지에 대해서만 주소 변환을 할 수 있는거니까 다른 프로세스가 내 페이지를 접근한다거나 이런건 애초에 불가능하기 때문에 그래서, Protection 이라는게 다른 프로세스가 이 페이지를 못보게 하거나 그런 용도는 아니라는 것이다. 자기자신이 자기 페이지만 접근하는 것이기 때문에 그런 일은 애초부터 없는 것.

그럼 이 Protection의 의미가 뭐냐?
즉, 접근 권한을 제어하는 거는 어떤 연산에 대한 접근 권한이 있느냐를 나타내는 것이다.

여기 페이지들이 굉장히 여러 개가 있는데 이 페이지 중에는 프로그램의 코드 부분을 담고 있는 페이지도 있고, 또 데이터나 스택 부분을 담고 있는 페이지도 있을 것이다.

그런데, 코드 같은 경우에는 그 내용이 바뀌지 않아야 된다. 원래 있는 그 내용을 CPU에서 읽어서 인스트럭션을 실행하는 용도지, 중간에 내용이 바뀌거나 이러지 않아야되기 때문에 그래서, 코드 같은 경우에는 read-only로 셋팅을 해놓고, 데이터 영역이나 스택 영역 같은데는 데이터를 중간에 쓰고, 업데이트하고 이런게 가능하다. 그래서 그런 페이지는 read, write권한을 다 줘야된다는 것이다.

그래서, 이 Protection bit의 의미는 이 페이지에 대해서 읽기 권한이 있느냐, 쓰기 권한이 있느냐, 연산에 대한 권한을 표시하기 위한 그런 비트라는 것이다.

이렇게 해서 페이지 테이블에 들어가는 비트 2가지를 설명함.

Inverted Page Table

• page table이 매우 큰 이유
  • 모든 process 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재
  • 대응하는 page가 메모리에 있든 아니든 간에 page table에는 entry로 존재
• Inverted page table
  • Page frame 하나당 page table에 하나의 entry를 둔 것 (system-wide)
  • 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시 (process-id, process의 logical address)
  • 단점
    • 테이블 전체를 탐색해야 함
  • 조치
    • associative register 사용 (expensive)

지금까지 페이지 테이블에서 문제가 되는게 뭐였느냐면, 굉장히 많은 용량을 차지하고 있다는게 문제다. 페이지 테이블이 엔트리가 100만개 이상이 되고 그러면 주소 변환을 위한건데, 페이지 테이블 자체가 메모리 공간을 많이 차지하게 된다는 것이다. 주소 공간이 허용하는 한도 만큼의 페이지 테이블 엔트리가 만들어져야되고, 또, 프로세스마다 각각 주소 변환을 해야되기 때문에 각 프로세스 별로 페이지 테이블이 만들어져야되고… 그렇기 때문에, 굉장히 공간 오버헤드가 컸던 것이다.

그래서, 그런거를 막아보자는 차원에서 나온 페이지 테이블이 Inverted Page Table이라는 것이다.

Inverted Page Table Architecture
Inverted Page Table을 보여주는 그림

원래의 페이지 테이블을 통한 주소 변환을 완전히 역발상으로 뒤집어 놓은 것이다. 원래는 페이지 테이블이라는게 프로세스마다 존재했다. 예를 들어서, p1이 있으면 p1을 위한 페이지 테이블이 있고, p2라는 프로세스가 있으면 p2를 위한 페이지 테이블이 있고… 이랬었는데,

Inverted Page Table은 시스템 안에 페이지 테이블이 딱 하나 존재한다. 그래서, 각 프로세스마다 존재하는게 아니라 system wide하게 페이지 테이블이 하나가 존재하는데, 그게 어떤식으로 만들어져 있느냐하면.. 이 페이지 테이블의 엔트리가 프로세스의 페이지 갯수만큼 존재하는게 아니고, 물리적인 메모리의 페이지 프레임 갯수만큼 존재하는 것이다. 그래서, 지금 페이지 테이블의 첫번째 엔트리는 물리적인 메모리의 첫번째 프레임을 나타내는 엔트리고, 두번째 엔트리는 두번째 프레임을 나타내는 엔트리라는 것이다. 그래서, 물리적 메모리의 페이지 프레임 갯수만큼 페이지 테이블 엔트리가 존재하게 되는 것이다.

그런데, 우리가 주소 변환을 하려면 어떤 페이지 번호를 보고 위에서부터 그 페이지 번호만큼 떨어진 엔트리에 가서 주소 변환을 하는 방법을 썼었는데, 지금 Inverted Page Table로는 그게 아예 불가능하다. 왜 그러냐? 그림을 보면 원래는 논리적인 페이지 번호가 있으면 그 해당하는… 예를 들어, 우리가 p번 페이지를 주소 변환 하고 싶다. 그러면 위에서부터 p번째 엔트리에 가면 페이지 프레임 번호가 몇번인지가 나온다. 그게 이제 정방향의 페이지 테이블에 의한 주소 변환인데… 이 역방향 페이지 테이블이라는 것은 페이지 프레임 갯수만큼 엔트리가 존재하고 그래서 들어가는 내용이 반대로 되있다. 첫번째 엔트리에는 첫번째 페이지 프레임에 들어가는 논리적인 페이지 번호가 들어있고, 두번째 엔트리에는 두번째 페이지 프레임에 들어가는 페이지의 논리적인 주소 번호가 들어있다는 것이다. 즉, 논리적 메모리에서부터 정방향으로 주소 변환을 하는게 아니고, (물리적 메모리 안에) 페이지 프레임의 f번째 엔트리를 가면 논리적인 페이지 번호가 나오게 되있는게 Inverted Page Table이다.

근데, 우리가 주소 변환이라는건 논리적 주소를 물리적 주소로 바꾸는거지 이것은 물리적 주소를 보고, 논리적 주소로 바꿀 수 있는 테이블이다 사실은. 그래서 어떻게 보면 우리 목적에 맞지 않는 테이블인데, 이 테이블을 통해서 주소 변환을 하려면 어떻게 해야 되느냐? 어쨌든 논리 주소를 가지고 이 물리적인 주소를 알아내야되기 때문에 그래서, 논리 주소에 해당하는 페이지 번호 p가 도대체 물리적인 메모리 어디에 올라가있는지를 찾으려면 페이지 테이블의 엔트리를 다 찾아봐야된다. 다 찾아봐서 해당하는 p가 나오면 “(그게 만약에 위에서부터 f번째 엔트리였다면) 아~ 이 페이지 p는 지금 f번째 프레임에 올라가 있구나.” 이걸 알 수 있다는 것이다.

그래서, 테이블이라는 것은 그 묘미가 뭐냐하면 배열처럼 인덱스를 통해서 위에서 p번째 떨어진데를 바로 검색하는게 페이지 테이블의 장점인데, 이 Inverted Page Table은 그런 장점이 없다. 페이지 번호가 주어지면 페이지 테이블 엔트리를 전부 검색해야지만 주소 변환을 할 수가 있는 것이다.

도대체 이런걸 왜 쓸까? 앞에서도 설명했지만 페이지 테이블을 위한 공간을 줄이고자 하는 것이다. 이거는 시스템 안에 하나만 존재하는거니까 공간을 많이 줄일 수 있는데 대신에, 문제는 시간적인 오버헤드가 있다. 한번에 주소 변환이 되는 것이 아니고, 페이지 테이블 엔트리를 전부 다 탐색해봐야지만 이 페이지 p가 어떤 프레임에 있는지를 알 수가 있게 되는 것이다.

그리고, 한 가지 더 페이지 테이블에 저장해야될게 있는데, 논리적인 페이지 번호만 저장하면 될게 아니라, 도대체 이 페이지 번호 p가 어떤 프로세스의 p번째 페이지 인지 그 프로세스 id를 같이 저장해야될 것이다. 왜냐하면, 논리적인 메모리라는 것은 프로그램마다 별도로 있는거니까 f번째 프레임에 올라가있는 이 페이지가 도대체 누구의 p번째 페이지냐를 나타내는 process id (pid)가 같이 들어가야 되는 것이다.

그래서, 이 Inverted Page Table로 주소 변환 하는 걸 한번 설명하면, CPU가 지금 그림과 같은 logical address를 줬다고 해보자. 이런 logical address를 주면, 도대체 이 logical address에 있는 페이지 번호 p가 이 페이지 테이블에서 어디에 있는지를 검색을 해봐야되고, 그리고 이 p가 여러개 있을 수도 있다 사실은. 다른 프로그램의 p번째 페이지가 또 페이지 테이블에 있을 수가 있는거니까.. 이것은 페이지 프레임 마다… 물리적인 메모리에 대해서 존재하는 테이블이니까. 그래서 탐색할 때는, 지금 CPU를 가지고 있는 이 p1이라는 프로세스의 pid를 같이 줘서 이 프로세스의 p번째 페이지가 어디에 있는지를 찾아서 그게 찾아지게 되면 주소 변환은 어떻게 하면 되냐면… 찾아진 위치가 위에서부터 몇 번째 엔트리인지를 봐서 그 엔트리 위치에 해당하는 번호를 페이지 프레임 번호로 넣어주면은 주소 변환이 끝나게 되는 것이다.

근데, 공간 줄이겠다고 이렇게 일일히 다 검색을 해봐야된다면 너무 오버헤드가 클 것이다. 그래서 보통은 Inverted Page Table은 그냥 위에서부터 순차적으로 검색하는 식으로 만드는 것은 적절하지가 않고, 앞에 TLB에서 설명했던 것처럼 associative register를 사용해서 이 엔트리들을 병렬적으로 동시에 검색할 수 있게.. 그래서, 이 페이지 테이블을 그냥 메모리에 넣는게 아니라 associative register라는 별도의 하드웨어에 집어넣어서 동작을 하게 하면, 순차적인 탐색의 ‘시간 오버헤드’를 줄일 수가 있는 것이다.

Shared Page

• Shared code

  • Re-entrant Code (=Pure code)

    재진입 가능 코드

  • read-only로 하여 프로세스 간에 하나의 code만 메모리에 올림
    (eg, text editors, compilers, window systems).

  • Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함

• Private code and data

  • 각 프로세스들은 독자적으로 메모리에 올림
  • Private data는 logical address space의 아무 곳에 와도 무방

프로그램을 구성하는 페이지들 중에는 다른 프로세스들하고 공유할 수 있는 페이지가 있다. 이것과 관련해서 아래 그림을 보자.

Shared Pages Example

지금 서로 다른 프로세스 P₁, P₂, P₃ 이렇게 3개가 있는데, 이 프로그램들이 만약에 같은 코드를 가지고 프로그램을 돌린다. 예를 들면, 에디터 프로그램(아래아한글 같은..)을 여기 3개으로 돌리고 있으면, 프로그램의 코드 부분은 3개의 프로세스가 똑같은걸 써도 된다. 근데 이 프로그램이 실행되면서 중간중간에 바뀌는 데이터 부분만 내용이 바뀌는거지 코드는 어차피 같은 프로그램이면 같은 내용일 것이다.

그래서, 이런식으로 share할 수 있는 코드, 이걸 우리가 Shared code라고 부르는데, 이런 것들에 대해서 각각을 물리적인 메모리에 별도로 올리는 것이 아니라 이러한 share가 가능한 Shared code에 대해서는 이걸 한 카피만 물리적 메모리에 올리는 것이다. 그래서, P₃에서도 같은 코드를 쓰고, P₂에서도 같은 코드를 쓰고 그러면, 이 프로그램(P₂)의 첫번째, 두번째, 세번째 페이지가 물리적인 메모리의 3번, 4번, 6번 프레임에 올라가 있다. 근데, 이 P₃ 프로그램의 코드 부분도 페이지 테이블은 따로 있겠지만 주소 변환을 해보면 역시 3번, 4번, 6번 프레임으로 매핑이 되어있다. 그래서, 물리적 메모리에 보면 올라와있다. 즉, 공유할 수 있는 코드는 별도로 올리는게 아니라 이렇게 같은 프레임으로 매핑을 시켜서 메모리에 한 카피만 올릴 수가 있다는 것이다.

이런걸 우리가 Shared code라고 하고, 다른말로는 Re-entrant Code 재진입 가능 코드, 또는 Pure code라고 부르는데 이렇게 여러 프로세스가 공유할 수 있는 코드 부분을 같은 물리적인 메모리 프레임으로 매핑해주는 기법을 얘기한다.

이 기법에서는 페이지들을 read-only로 반드시 셋팅을 해야한다. 그러지 않으면 문제가 생길 수가 있기 때문에… read-only로 셋팅하고 대신에 물리적인 메모리에 한 카피만 올려놓는 것이다.

shared code하고 다르게, private code나 또는 data 같은 것… 프로세스마다 별도로 가져야되는 그런 페이지들은 이런식으로(그림 표시) 각각이 다른 프레임으로 매핑 되도록 해놓는다는 것이다.

여기서 말할 중요한 사항!
Shared code 즉 Re-entrant Code는 2가지 조건을 만족해야된다. 그 중에 첫번째는 이미 말한 read-only 페이지여야된다.(read-only로 셋팅해야된다.)는 것이고, 두번째 조건은 이러한 Shared code는 동일한 logical address에 위치를 해야된다.

“동일한 logical address에 위치한다.” 이게 무슨 얘기냐하면 지금 프로세스가 3개가 있는데, 이 3개의 프로세스에서 Shared code에 해당하는 세 페이지(ed 1, ed 2, ed 3)가 동일한 logical address를 가지고 있다.(동일한 physical address를 가지고 있는건 당연하다. 지금 shared code니깐 3, 4, 6, 3, 4, 6, 3, 4, 6해서 동일한 physical address를 가지고 있는건 당연한 일인데, 동일한 logical address를 가져야지 된다는 것이다.) 즉, 여기서(P₁에서) 지금 ed 1, ed 2, ed 3이 첫번째 페이지, 두번째 페이지, 세번째 페이지인데 P₃, P₂도 마찬가지다. 만약에 P₂에서는 ed 3가 data 2랑 바뀌어가지고 세번째 페이지가 shared code인데, 밑에 내려와있는데.. P₃에서는 반대로 위에 올라가있고.. 이러면 안된다는 것이다. 이게 동일한 logical address를 가져야된다는 얘기다.

왜 그런 조건이 붙느냐 하면…?
이 챕터 초반에 이런 코드들이 컴파일이 되있지만 이 안에 주소들이 적혀있다. 맨 앞에 보면, 아래와 같은 예제를 봤었고

이게 일종의 컴파일 되있는 코드인데 여기 보면(파란색 표시 해놓음) 안에 주소들이 적혀있다. 20번지와 30번지에 있는 내용을 더하고 40번지로 점프하라는 식으로… 코드안에는 logical address가 적혀있다. 그런데, 똑같은 코드를 가지고 어떤 친구는 이 코드들이 잘려가지고 있고, 어떤 친구는 logical address가 서로 다른 번지로 배당이 되있으면서 동일한 내용이 들어갈 수가 없다. 왜냐하면, 이 안에 있는 코드는 우리가 share하는 것이고, 이 logical address가 코드 안에 들어가 있는데 이걸 바꿀 수가 없다.

그래서, shared code는 항상 동일한 logical address를 가져야 된다. 이게 제약조건이라는 것이다.

우리가, 이 챕터 들어오기 몇 챕터 전에 shared memory를 이용해서 프로세스 간에 inter process communication(IPC, 프로세스 간 통신)하는 방법을 말한 적이 있다.(아마 프로세스 관리 챕터때인듯…) 그거랑 shared code랑은 조금 다르다. 거기서는 프로세스 간에 통신을 목적으로 어떤 페이지를 여러 프로세스에 주소 공간에 같이 매핑하는 거기까지는 같은데, 거기서는 read / write가 가능하게 해놓고, 한 친구가 write를 하면 다른 친구가 그거를 읽고, 일종의 커뮤니케이션을 목적으로 그렇게 해놓는 거고…
여기서의 shared code는 read-only로 해서 어떤 프로세스가 내용을 접근하다가 다른 프로세스한테 영향을 미치거나 이런 문제를 배제한 그런 코드라는 점에서 기존의 shared memory에서 얘기한 기법과는 조금 다르다.
즉, shared memory에서는 read / write가 가능한 걸 말했었는데, 여기서의 shared page는 read only를 share하는…코드를 공유하는 그런 것이다.

Segmentation

• 프로그램은 의미 단위인 여러 개의 segment로 구성

  • 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
  • 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
  • 일반적으로는 code, data, stack 부분이 하니씩의 세그먼트로 정의됨

• Segment는 다음과 같은 logical unit 들임

  main (),
  function,
  global variables,
  stack,
  symbol table, arrays

Segmentation 기법은 프로세스를 구성하는 주소 공간을 의미 단위로 쪼갠 것이다. 예를 들면, 코드, 데이터, 스택 이런 것들은 프로세스의 주소 공간 중에서 그 의미를 가지는 단위라는 것이다. 그런 각각이 segment가 되는 것이다. 또, 좀 더 세분화해서 segment를 더 잘게 쪼개고 싶다면 코드 중에서도 함수 별로 메인함수가 있고, 또 다른 함수가 있고… 이런 것들을 별도의 세그먼트로 구성을 할 수도 있다는 것이다.

Segmentation Architecture

• Logical address는 다음의 두 가지로 구성
  <segment-number, offset>
• Segment table
  • each table entry has:
    • base - starting physical address of the segment
    • limit - length of the segment
• Segment-table base register (STBR)
  • 물리적 메모리에서의 segment table의 위치
• Segment-table length register (STLR)
  • 프로그램이 사용하는 segment의 수
    segment number s is legal if s < STLR.

세그멘테이션 기법에서 주소 변환은 페이징 기법하고 비슷한 측면이 있다. Logical address를 세그먼트 번호하고, 세그먼트 안에서 얼마나 떨어져있는지를 나타내는 오프셋 이렇게 두 가지로 구성이 되고,

각 세그먼트 별로 서로 다른 메모리 주소에(물리적인 메모리 위치에) 올라갈 수 있게 때문에 세그먼트 별로 주소 변환을 해야돼서 세그먼트 테이블이라는 것을 두고 있다.

그리고, 주소 변환을 위해서 예전에 base register하고 limit register.. 레지스터가 2개 지원되고 있는데, 그 레지스터 2개는 세그멘테이션 기법에서는 세그먼트 테이블의 시작 위치를 나타내는 용도하고, 그 다음에 세그먼트 테이블의 길이를 나타내는… 여기서는 이제 세그먼트 테이블의 길이라는게, 그 프로그램이 사용하는 세그먼트의 개수를 나타내는 즉, 엔트리의 수를 나타내는 그런 용도로 사용이 된다는 것이다.

그래서, 아래 그림을 보면

Segmentation Hardware

세그멘테이션 기법에 의한 주소 변환을 보여주고 있다.

CPU가 논리 주소를 주게 되면 이걸 두 부분으로 나누게 된다. 세그먼트 번호(s)하고, 세그먼트 내에서 떨어진 오프셋(d)으로 나눈다. 그래서, 세그먼트 테이블의 시작 위치는 레지스터가 가지고 있을 것이고, 거기서부터 세그먼트 번호에 해당하는 위치만큼 떨어진 엔트리에 가면 이 세그먼트가 물리적인 메모리에 어떤 번지에 올라가 있는지를 가지고 있다.

그런데, 세그멘테이션 기법은 페이징하고 다르게 엔트리에 2가지 정보를 가지고 있다. 물리적인 메모리 상에 시작 위치(base) 외에 하나를 더 가지고 있어야 되는데, 그게 뭐냐면 limit이라는 건데, 이것은 세그먼트의 길이를 나타내는 것이다. 우리가 페이징 기법에서는 페이지 크기가 다 동일했다. 그렇지만, 세그멘테이션 기법은 의미 단위로 자르는 거기 때문에, 세그먼트의 길이가 균일하지 않을 수가 있어서 이 세그먼트의 길이가 얼만지를 테이블 엔트리에 같이 가지고 있게 되는 것이다.

그래서, 여기서 이제 주소 변환을 할 때 크게 2가지를 체크해봐야 되는데…

첫번째는 CPU에 주어진 논리 주소에서 세그먼트 번호가 예를 들어서… 이 프로그램이 세그먼트 3개로 구성되있는데 세그먼트 번호가 5번이다.. 이렇게 되면 이건 잘못된 요청이다. 그래서, 논리 주소의 세그먼트 번호가 (Segment-table length register (STLR)에 세그먼트 개수가 들어있다.)이 프로그램을 구성하는 세그먼트의 개수 보다 작은 값인지를 확인해서 만약, 그 값보다 큰 세그먼트를 요청했다고 하면 이건 잘못된 시도이기 때문에 트랩이 걸리게 된다.

또 한가지 체크할게 있는데 그거는 이 세그먼트를 통해서 주소 변환을 하는데, 이 세그먼트의 길이가 1000바이트인데, 세그먼트 안에서 떨어진 위치를 2000바이트로 요청했다.. 이런 경우도 있을 수 있다. 그래서, 하나 더 체크하는건 세그먼트의 길이보다 지금 요청한 세그먼트 안에서 떨어진 오프셋의 값이 더 크지는 않은가.. 그러면 잘못된 거니까 트랩을 발생시켜야 된다.

그렇지 않고, 정상적인 요구라고 하면 주소 변환을 하게 되는데, 그 주소 변환은 이 세그먼트의 시작 위치(base)에다가 이 오프셋(d)을 더해서 주소 변환을 하게 되는 것이다.

그래서, (물리적 메모리를 보면) 위에서부터 base위치만큼 떨어진 곳에 이 세그먼트가 시작이 되고(물리적 메모리에서 하얀색 표시), 그 다음에 거기서부터 d만큼 떨어진 위치에 가면 원하는 주소에 내용이 들어있게 되는 것이다. 그래서, 지금 물리적 메모리 그림에서 limit하고 싸여져 있는 부분이 세그먼트의 길이고, base로 싸여져 있는 것이 세그먼트의 시작위치를 나타내는 값이 되는 것이다.

사실 세그멘테이션 기법이 페이징하고 비슷한 것 같지만, 다른 측면이 여러가지가 있다. 페이징 기법은 어차피 페이지 크기가 균일하기 때문에, 오프셋의 크기가 결국에 페이지 크기에 의해서 결정이 되버린다. 그런데, 세그멘테이션 기법에서는 이게 만약 32비트라고 하면 그 중에 오프셋에 해당하는 부분은 미리 결정이 되야된다. 이게 결국 뭘 나타내느냐하면.. 이 비트 수가 이 세그먼트의 최대 길이가 (이 세그먼트가 아니라 이러한 체제 하에서) 세그먼트 길이는 이 오프셋(d)으로 표현할 수 있는 비트 수 이상은 안된다는 것이다. 그게 세그먼트 길이를 제한하는 요소가 되고 있고…

그 다음에 페이징 기법에서는 시작 주소가 프레임 번호로 주어지면 된다. 주소 변환을 할 때 어차피 물리적인 메모리도 같은 크기의 프레임으로 나누어져있기 때문에 몇번 페이지 프레임에 가면 되느냐? 이거였는데…
세그멘테이션에서는 세그먼트 크기가 다 다르기 때문에 그래서, 이 세그먼트가 어디에서 시작이 되는지 그거를 정확한 바이트단위 주소로 매겨줘야될 것이다 base위치도. 그게 페이징 기법하고 차이점이고, 어차피 세그먼트의 크기가 균일하지 않기 때문에.. 우리가 가변 분할 방식.. 앞에서 연속 할당 기법에서 프로그램 크기가 균일하지 않아서 실행을 시켰다가 종료가 되고 이러다보면 중간중간에 여러가지 홀들이 생겼었다. 세그먼트라는 것도 어차피 크기가 균일하지 않기 때문에, 어떤 세그먼트가 빠져나가고 더 작은 세그먼트가 들어오고 이러다보면 중간중간에 사용되지 않는 메모리 공간이 작은게 여기저기 생기게 되는 것이다.

그게 세그멘테이션 기법의 단점인데…

Segmentation Architecture (Cont.)

• Protection
  • 각 세그먼트 별로 protection bit가 있음
  • Each entry:
    • Valid bit = 0 → illegal segment
    • Read/Write/Execution 권한 bit
• Sharing
  • Shared segment
  • same segment number
  • ^^^ segment는 의미 단위이기 때문에 공유(sharing)와 보안(protection)에 있어 paging보다 훨씬 효과적이다
• Allocation
  • first fit / best fit
  • external fragmentation 발생
  • ^^^ segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들이 발생

크기가 균일하지 않기 때문에, 메모리 크기가 균일하지 않아서 생기는 그런 문제점… first fit이나 best fit 이런것을 써야된다. 외부 조각이 발생하는 그런 문제가 있고,

대신에 세그멘테이션 기법의 장점은 무엇이냐?
우리가 이거는 의미 단위로 쪼개는 것이기 때문에, 의미 단위로 뭔가 일을 하는거는 세그멘테이션 기법이 훨씬 효과적이다. 예를 들면, 프로텍션을 하는 경우에 우리가 어떤 부분은 read only로 되있고, 어떤 부분은 read / write가 가능하고, 또 어떤 부분은 실행 권한이 있고.. 이런거에 대해서 보통 의미 단위로 권한 부여를 하게 된다. 그래서, 코드는 read only가 되고, 데이터는 read / write가 가능하고.. 이런식으로 세그먼트에 대해서 의미 부여를 하는건 대단히 자연스러운 일인데, 페이징에서는 사실 그렇지는 않았다.

어떤 프로그램을 구성하는 이런 페이지들이 있는데 이거를 동일 크기로 자르다보면 어떤 페이지에는 코드하고 데이터가 같이 들어갈 수도 있을 것이다. 그러면 이것은 read only로 해야되느냐, read / write 권한을 다 줘야되느냐…? 이게 결국에는 의미 단위로 자르는게 아니라 같은 크기 단위로 잘랐기 때문에 이러한 문제가 어려워지는 것이다. 그래서 페이징 기법에서는 의미 단위로 프로텍션을 해야되는 경우에 다른 페이지의 위치를 시킨다던지… 이런식의 보완 작업이 필요한 것이다.

그 다음에 sharing도 마찬가지이다.
우리가 어떤 프로세스의 주소 공간을 프로세스끼리 공유시키고 싶다. 그러면 의미 단위로 하는거지, 동일한 크기 단위로 잘라서 하는게 의미가 없다. 그래서 프로세스 간에 셰어링을 할 때도 페이징보다는 세그멘테이션이 더 유리하다. 즉, 의미 단위로 하는 공유나 보안 이런 것들에 있어서는 세그멘테이션이 유리하지만, 세그먼트는 크기가 균일하지 않기 때문에 이런 얼로케이션(Allocation) 상의 문제가 발생한다.

Example of Segmentation

세그멘테이션 기법의 주소 변환 자체는 페이징 기법과 원리는 크게 다르지 않은데, 또 한 가지 봐야될 점이 뭐냐면, 페이징 기법은 프로그램을 구성하는 페이지의 개수가 100만개 이런식이다. 굉장히 많기 때문에 테이블을 위한 메모리 공간 낭비도 대단히 심하다.

거기에 비해서, 세그멘테이션 기법에서는 세그먼트 개수가 5개 이런식이라는 것이다. 따라서 실질적으로 테이블을 위한 메모리 공간 낭비가 페이징 기법에 비해 세그멘테이션 기법이 덜하다.

위 그림으로 제시한 예제는 하나의 프로그램을 구성하는 세그먼트가 5개인 경우이고, 그 중에서 메인함수main program, Sqrt라는 라이브러리 함수, 그리고 subroutine함수 이런것들이 하나의 세그먼트를 형성하고 있고, 또 stack 그리고 symbol table 이런것들이 세그먼트를 형성하고 있기 때문에 각각의 세그먼트에 대해서 주소 변환을 위한 테이블segment table이 그림과 같이 있다. 그래서 이 세그먼트들의 물리적인 메모리 상의 시작 위치가 table열에 적혀있다. 예를 들면, 0번 세그먼트는 물리적인 메모리의 시작위치가 1400번지다. 물리적 메모리에 보면 1400번지부터 시작이 되고, 세그먼트의 길이는 limit컬럼에 적혀있는데 1000이라는 것이다. 그래서, 1400번지부터 2400번지까지 세그먼트 0번이 위치하고 있다. (그림이 조금 잘 그려진 것 같지는 않다. 적당히 보기…)

이와 같이 세그먼트 별로 물리적 메모리에 올라갈 수가 있고, 또 올라가 있지 않고 내려가 있을 수가 있고.. 이러한 방식이 세그멘테이션 기법이 되겠다.

Sharing of Segments

세그멘테이션 기법은 의미 단위로 해야되는 공유.. 이런 작업이 더 수월하다고 말했었는데, 이 그림은 세그먼트를 서로 다른 2개의 프로세스가 공유하는 그런 모습을 보여주는 예제이다.

각각의 프로세스가 지금 2개의 세그먼트가 있는데, 그 중에 0번 세그먼트segment 0는 코드를 담고 있는 세그먼트다. 그래서 이 코드가 2개의 프로세스에서 같은 역할을 하는 코드이기 때문에 Sharing을 한 것이다. 즉, shared segment에 해당하는 것이다. 그래서 이러한 shared segment는 같은 논리적인 주소 상에 있어야된다. 그게 세그먼트 번호가 같아야된다는 얘기이다. 그래서, 공유 세그먼트는 P₁ 프로세스에서도 0번 세그먼트이고, P₂ 프로세스에서도 0번 세그먼트로 돼 있다.

그리고 이 2개의 세그먼트는 주소 변환을 하게 되면.. 0번 세그먼트가 같은 위치인 물리적인 메모리 43062번지에 한 카피가 올라가 있다. 그래서 P₁을 위한 0번 세그먼트와 P₂를 위한 0번 세그먼트가 똑같이 위치하게 되는 것이다.

반면에, Shared segment가 아니고 Private segment인 1번 세그먼트segment 1의 경우에는 2개의 프로세스에서 주소 변환 정보가 서로 다른 위치로 매핑이 돼있다. 프로세스 1번에서는 1번 세그먼트가 물리적 메모리 그림data 1과 같이 와있고, 프로세스 2번에서는 1번 세그먼트가 물리적 메모리 그림data 2과 같이 와있다. 그래서, 이런식으로 셰어 할 수 있는 코드 세그먼트는 (그림과 같이) 셰어를 시킨 것이고, 프라이빗 세그먼트.. 즉, 별도로 존재해야되는 거는 주소 변환을 따로 하도록 만들어 놓은 것이다.

Segmentation with Paging

(Paged Segmentation) 세그멘테이션과 페이징을 혼합하는 기법

• pure segmentation과의 차이점
  • segment-table entry가 segment의 base address를 가지고 있는 것이 아니라 segment를 구성하는 page table의 base address를 가지고 있음

물리적인 메모리를 관리하는 기법으로 연속 할당이 있었고, 그 다음에 불연속 할당에서 프로그램을 구성하는 주소 공간을 자르는건데, 같은 크기 단위로 자르는 페이징 기법, 의미 단위로 자르는 세그멘테이션 기법을 설명했었고…

마지막 Paged Segmentation이라는건 페이징과 세그멘테이션..2가지 기법을 혼합한 것이다. 혼합한건데 특별히 Paged Segmentation이다 그래서, 세그먼트를 갖다가 여러개의 페이지로 구성하는 기법이다.

그래서, 이 기법에서는 세그먼트 하나가 여러개의 페이지로 구성이 되기 때문에, 그래서 먼저, 세그먼트에 대한 주소 변환을 하게 된다. 각 프로그램이 가지고 있는 논리 주소logical address는 세그먼트 번호s와 세그먼트 안에서 얼마나 떨어져 있는지를 나타내는 오프셋d으로 구성이 되고…

그러면 세그멘테이션 기법이니까 먼저 세그먼트 테이블segment table을 찾아야 될 것이다. 세그먼트 테이블이 메모리 어디에 와있느냐..? 아까 말했다시피 레지스터STBR에 세그먼트 테이블의 시작 위치가 들어있고, 위에서부터 세그먼트 번호에 해당하는 s번째 엔트리를 가면 이 세그먼트에 대한 주소 변환 정보가 있었다. 그래서 예전에 오리지널 세그멘테이션 기법에서는 여기(segment table)를 가면 이 세그먼트가 메모리 어디에 올라가있는지 그 시작 위치가 담겨 있었다. 근데, 그 오리지널 세그멘테이션 기법은 세그먼트가 어차피 통째로 메모리에 올라가기 때문에 그래서, 세그먼트가 메모리 어디에 올라가 있는지 시작위치를 알려주면 되는데…

지금 소개하는 이 기법(Paged Segmentation)은 세그먼트 하나가 여러개의 페이지로 구성이 된다. 그렇기 때문에, 메모리에 올라갈 때는 페이지 단위로 쪼개져서 올라가는 것이다. 그러니까 뭐가 장점일까? Allocation 문제가 안생긴다.(중간중간에 크기가 달라서 홀들이 생기는 문제는 이 기법에서는 없을 것이다) 왜냐하면, 어차피 물리적인 메모리에는 페이지 단위로 올라가는 것이다. 그리고 세그먼트라는 것은 페이지 갯수의 배수로 구성이 된다는 것이다. 그래서 메모리에 올라가는건 페이지 단위로 올라가니까 Allocation 문제는 없고, 그렇지만 의미 단위로 해야되는 공유(sharing)나 보안(protection) 같은 업무는 세그먼트 테이블segment table 레벨에서 하는 것이다. 그래서 특정 세그먼트가 프로텍션이 read-only인지 또는 read / write가 가능한지 이런 것들은 세그먼트 테이블에 해당 세그먼트마다 표시를 해주면 된다는 것이다.

의미 단위로 하는 일은 세그먼트 테이블 차원에서 해주고, 그 다음에 실제로 물리적인 메모리에 올라갈 때는 페이지 단위로 쪼개져서 올라가기 때문에, 2가지 방법의 장점을 모두 누릴 수가 있다.

그래서 실제로 오리지널 세그멘테이션을 쓰는 메모리 시스템은 (현실적으로는) 없다. 세그멘테이션 기법을 쓰더라도 그 내부에는 페이징을 이렇게 같이 써야지만 관리가 훨씬 수월한 방법이 되는 것이다.

그래서, 2단계 페이징 기법처럼 주소 변환을 두 단계를 거쳐야되는데, 첫 부분에서 세그멘테이션에 대한 주소 변환을 해주게 되면 페이지 테이블의 시작 위치page-table base가 나온다. 세그먼트 하나가 여러개의 페이지로 구성된다고 했다. 그러면, 각각의 페이지 별로 주소 변환을 해야될 것이다. 그러면 세그먼트 당 페이지 테이블이 존재하는 것이다.page table for segment s(예전에 프로세스 당 페이지 테이블이 존재하는거하고 다르게 여기서는 세그먼트 당 페이지 테이블이 존재하게 되고) 그러면, 세그먼트 테이블의 해당 엔트리에 가면 이 세그먼트를 구성하는 페이지의 테이블의 시작 위치가 나오는 것이다.

그러면, 여기(page table for segment s) 엔트리가 몇 개로 구성되느냐? 그거는 segment length에 담아놓는다. 세그먼트의 길이가 얼만지를 보면 이 세그먼트가 페이지 테이블에 몇 개 엔트리가 있는지를 알 수가 있기 때문에 그 길이를 벗어나는 요청에 대해서는 트랩을 발생시킬 수가 있는 것이다. (아래 이미지)

약간 다르게 설명했는데…
세그먼트의 길이segment length가 세그먼트 테이블에 있는데, 우리가 logical address의 d랑 비교를 해봐야 된다. 세그먼트의 길이보다 세그먼트 안에서 떨어진 오프셋 값d이 더 크다면 그게 또 잘못된 메모리 접근 시도이기 때문에 세그먼트 테이블에서 세그먼트의 길이segment length와 실제로 요청한 그 세그먼트 내에서의 오프셋d을 비교해봐서 그 오프셋이 세그먼트 길이 이내인 경우에만 주소 변환을 해줘야 겠다는yes 얘기이다.

그 다음에 테이블의 시작 위치로부터 얼만큼 떨어져야지만 해당하는 페이지에 대한 주소 변환을 할 수 있느냐?

여기서(그림 하늘색 표시) 다단계 페이지 테이블에서처럼 세그먼트 안에서의 이 오프셋 d를 다시 자른다(그림 초록색 표시). 그래서 앞 부분p은 페이지 번호로 사용하고, 뒷 부분d'은 그 페이지 안에서 얼마나 떨어져있는지에 해당하는 페이지 오프셋으로 사용하는 것이다.

그러니까 여기(하늘색 표시)서의 d는 세그먼트 오프셋..세그먼트 안에서 얼만큼 떨어져 있는가를 나타내는 오프셋인데, 이걸 이제 세그먼트 하나가 여러 개의 페이지로 구성되기 때문에, 다시 이거를 쪼개서(초록색 표시) 앞 부분p은 페이지 번호, 뒷 부분d'은 페이지 안에서 얼마나 떨어져있는지 오프셋 그걸로 쓰는 것이다.

그래서, 아까 그 페이지 테이블의 시작 위치page-table base로부터 이 페이지 번호p만큼 떨어진 엔트리에 가면, 이 페이지에 대한 주소 변환 결과(page table for segment s에서f).. 물리적인 메모리의 몇 번째 프레임인지 프레임 번호(physical address에서f)가 나올 것이다. 그러면, 그 프레임 번호f를 앞에다가 붙여주고 페이지 안에서의 오프셋p'은 그대로 넘겨주면(노란색 표시) 이게 물리적인 메모리의 주소가 된다.

그래서 논리적인 주소 값이 물리적인 메모리 주소로 위와 같이 바뀌게 되고, 각각의 페이지 별로 메모리 다른 위치에 올라가게 되는 것이다.

그래서 이 기법은 쭉 따라가보면 주소 변환은 예전처럼 실행을 할 수가 있다.

---

📝 마무리

이 챕터의 제목은 메모리 관리인데, 메모리 관리 중에서도 사실은 물리적인 메모리 관리였다.

그러면, 이 챕터에서 운영체제의 역할이 뭐였는가?

이 챕터에서 주요한 내용은 ‘주소 변환’ 이었다. 어떤 프로세스가 논리적인 주소를 가지고 있고, CPU가 논리적인 주소를 주면 그거를 물리적인 메모리 주소로 변환해서, 메모리 참조를 하게 된다는게 이 챕터의 내용인데, 그러면 주소 변환에 있어서 운영체제의 역할이 뭐였는지 짐작이 가는가?

챕터를 통째로 설명했지만, 사실 이 챕터에서 주소 변환을 위한 운영체제의 역할은 없다. 이거 다 하드웨어가 해줘야되는 역할이다.

처음에 주소 변환을 위해서 MMU라는 하드웨어를 통해서 주소 변환을 한다고 말했었고, 뒤에 세그멘테이션 기법이나 페이징 기법으로 넘어가면 CPU가 논리 주소를 주면 물리적인 메모리 주소로 바꿔서 메모리 참조를 하게 되는데, 여기 주어진 이 일련의 과정에서 운영체제가 하는 역할은 하나도 없다. 전부 다 하드웨어적으로 하드웨어가 해줘야되는 역할이다.

왜 그런지를 설명하자면…

지금 어떤 프로세스 하나가 지금 CPU를 잡고 실행을 하고 있으면서

이 프로세스의 이 주소logical address 요청을 한 것이다. 그러면 메모리 참조를 해야되는데, 어떤 프로세스가 CPU를 가지고 있으면서 메모리 접근을 하는건 운영체제의 도움을 받는가? 안 받는가? 운영체제의 도음을 전혀 안받는다.

왜 그러냐? 만약에 어떤 프로세스가 CPU를 가지고 메모리 접근을 하는데, 주소 변환을 할 때마다 운영체제가 중간에 개입을 해야된다고 하면 CPU가 이 프로세스로 부터 운영체제로 넘어가야 될 것이다. 넘어갔다가 다시 또 주소 변환 했으니까 CPU가 프로세스한테 넘어온다? 이거 사실 말이 안되는 것이다.

그러니까, 프로세스가 CPU를 가지고 있었으면, 매 CPU 클럭 사이클마다 메모리에서 어떤 인스트럭션을 읽어와서 CPU에선 실행을 하고, 또 필요시 데이터를 CPU로 읽어들여서 실행을 하고… 이러한 모든 과정은 주소 변환을 통해서 메모리 접근이 이루어지는데, 그러한 주소 변환 때마다 운영체제의 도움이 필요하냐? 그렇게 되면 CPU가 운영체제로 넘어갔다, 사용자 프로세스로 넘어갔다, 이렇게 해야된다는건데 그건 사실 말이 안되는 얘기고 그래서, 주소 변환은 무조건 하드웨어적으로 이루어지는 일이라는 것이다.

운영체제가 끼어들어야되는 경우는 언제였는가?
메모리 접근이 아니라 I/O 장치를 접근하는건 운영체제가 끼어들어야된다. I/O 장치를 접근할 때는 이 사용자 프로세스가 직접 I/O 접근을 못하기 때문에, 운영체제한테 대신 해달라고 요청을 한다. 디스크를 접근하거나.. 이런 일들은 CPU가 운영체제한테 넘어가서 해야되는 일이다.

그렇지만, 매번 메모리 접근 할 때 마다 운영체제가 뭔가 일을 해줘야된다? 그거는 상식적으로 말이 안되고, 당연히 이건 하드웨어가 해야되는 일이라는 것이다. 운영체제한테 CPU가 넘어가도 결국에는, 운영체제가 뭔가 일을 하려면 CPU를 잡고 있으면서 주소 변환을 해서 인스트럭션 형태로 운영체제가 일을 하는 것이다.

즉, 운영체제라는 것도 사실은 하나의 프로그램이기 때문에, 그래서 CPU를 잡으면 인스트럭션을 실행하는 거는 다른 프로그램과 크게 다르지 않다.

이 챕터에서 사실상 운영체제의 역할은 없었다.

그렇지만, 다음 챕터로 넘어가면 Virtual Memory 부분이 나오는데, 이 Virtual Memory 부분에서는 운영체제가 중요한 역할을 하게 된다.

맨 위로 이동하기