[CS] 메인 메모리

effiRin·2023년 4월 30일
0

CS

목록 보기
1/1
post-thumbnail


[운영체제 스터디 - Operating System Concept 9장]


이 장의 목표

  • 논리 주소와 물리 주소의 차이점
  • 주소를 변환할 때 MMU(메모리 관리 장치)의 역할
  • 메모리를 연속적으로 할당하기 위해 최초, 최적 및 최악 접합 전략을 적용
  • 내부, 외부 단편화의 차이점
  • TLB(translation look-aside buffer)가 포함된 페이징 시스템에서 논리 주소를 물리 주소로 변환한다.
  • 계층적 페이징, 해시 페이징 및 역 페이지 테이블을 설명한다.




Logical Address / Physical Address

메모리 : 각각 주소가 할당된 일련의 바이트들로 구성

Logical address(=virtual address)

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

Physical address

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

일단 메모리에는 주소가 매겨져 있다.
그 주소는 크게 ‘논리적인 주소’와 ‘물리적인 주소’로 구분할 수 있다.
이걸 이해하기 위해서 프로그램의 실행 과정을 잠시 생각해보자.

1) 프로그램을 메모리 가져와서 프로세스 문맥에 배치하고,
2) 해당 시점에 이용 가능한 CPU에서 실행한다.
3) 그렇게 프로세스가 실행되면 메모리에서 명령이나 데이터에 엑세스를 하는데,
이 실행 과정에서 프로그램만의 독자적인 주소 공간이 형성된다.
이 주소가 바로 ‘논리적인 주소’이다.

논리적인 주소는 프로그램마다 0번지부터 시작하는 각자의 논리 주소를 가지게 되는데, 이게 실행되려면 물리적인 메모리로 올라가야 한다.
올라가는 과정에서 주소가 바뀌게 되는데,
이를 ‘주소 변환’, 또는 주소를 결정한다고 해서 ‘주소 바인딩’이라고 한다.




주소 바인딩

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

주소는 Symbolic Address → Logical Address → Physical address 이와 같이 변환 과정을 거치는데

여기서 Symbolic Address는 프로그래머가 쓰는 주소, 예를 들면 코드의 변수나, 메소드 같은 것들이다. 이 Symbolic Address가 컴파일러를 통해 010101과 같은 숫자 주소, ‘Logical Address’로 바꿔준다.

그렇다면 그 다음, 논리적인 주소가 물리적인 메모리 주소로 변환되는 과정은 언제 이루어지는가?

여기엔 3가지 시점이 있다.

컴파일 시간(compile time) 바인딩

  • 컴파일 시 주소 변환이 이루어지는 방법
  • 시작 위치 변경 시 재 컴파일
  • 컴파일러는 절대 코드(absolute code)를 생성한다

적재 시간(load time) 바인딩

  • 프로그램의 실행이 시작될 때 주소 변환이 이루어지는 방법
  • Loader의 책임 하에 물리적 메모리 주소 부여
  • 컴파일러가 이진 코드를 재배치 가능 코드(relocatable code)로 만든 경우 가능

실행 시간(execution time) 바인딩

  • 프로그램이 시작된 이후, 즉 실행 중에 주소 변환이 이루어지는 방법
  • 수행이 시작된 이후에도 프로세스의 메모리상 위치를 옮길 수 있음
  • CPU가 주소를 참조할 때마다 binding을 점검(address mapping table)
    - 하드웨어적인 지원이 필요하다 (→ base and limit register / MMU )

이렇게 3가지 바인딩이 있는데,
자세한 것은 예시를 통해 알아보자.




주소 바인딩 예시

왼쪽을 보면 예시 소스코드가 있다.
Add A, B 그리고 Jump C라는 명령어가 있고,
이 코드는 A와 B를 더하고 C를 통해 나가는 코드이다.

여기서 컴파일이 되어서 실행파일이 되면 Logical Address가 된다.
0번지부터 시작해서
Add A와 B가 Add 20, 30 이 되고
C로 Jump하라는 것이 Jump 40 이런 식으로 주소가 바뀌게 된다.
즉 Logical Address로 표시가 된 것.

이제 실행되려면 앞서 말한대로 물리적인 메모리에 올라가야 한다.
그리고 그 물리적인 메모리 주소가 결정되는 시점이 아까 말한 3가지가 있었는데,


  1. 첫 번째, 컴파일 타임 바인딩
  • 컴파일 시점에 물리적인 메모리 주소가 결정되는 것인데,
    여기서 중요한 것은 컴파일 타임 바인딩은 컴파일 시점에 이미 물리적인 주소가 결정되는 것이기 때문에 논리적인 주소가 사실 물리적인 주소가 된다는 점이다.
  • 이처럼 논리적인 주소가 물리적인 메모리로 또 고정된다는 점에서 이런 코드를 ‘앱솔루트 코드’(절대 코드)라고 한다.
  • 컴파일 시점에 물리적인 주소까지 고정되기 때문에 만약 주소를 바꾸고 싶다면 컴파일을 다시 해야한다. 또한 다른 주소가 많이 비어있음에도 프로그램이 0번지부터 붙기 때문에 대단히 비효율적이다. 그래서 현대의 컴퓨터 시스템에서는 이 컴파일 타임 바인딩을 사용하지 않는다고 한다.

  1. 두 번째, 로드 타임 바인딩은
  • 프로그램이 시작되어서 메모리에 올라갈 때, 물리적인 메모리 주소가 결정된다.
  • 컴파일 시점에는 논리적인 주소까지만 결정이 된 상태고, 이를 실행시키면서 메모리를 쭉 보는데 500번지부터 비어있다고 하면, 그 논리적인 주소 0번지를 물리적인 메모리 500번지에 올린다.

  1. 세 번째, 런타임 바인딩
  • 로드 타임 바인딩처럼 실행시에 물리 주소가 결정되는 것은 똑같지만,
    다른 점은 실행 도중에 주소가 바뀔 수도 있다는 것이다.
  • 처음엔 물리적인 주소 300번지에 바인딩 되었다가, 실행 도중에 700번지로 이동할 수도 있다는 이야기.
    ⇒ 그래서 현대 컴퓨터 시스템은 런타임 바인딩을 지원하고 있다.



MMU

그런데 이 런타임 바인딩을 하려면, 주소 변환을 도와주는 하드웨어가 필요하다.
프로그램이 시작될 때 이미 주소가 다 결정되는데,
이 런타임 바인딩은 프로그램 실행 중에도 계속 주소가 바뀔 수 있어야 하기 때문에
CPU가 메모리 주소를 요청할 때마다 그때마다 바인딩을 체크하고 주소 변환을 해줘야 한다.

그래서 이를 도와주는 하드웨어를 MMU라고 부르며,
프로그램이 실행 도중엔 이 MMU를 통해 주소 변환 작업이 이루어진다.

우선 MMU는 프로그램의 시작 주소를 가진 Base register (참고로 이젠 relocation register라고 부른다고 함)

그리고 마지막 주소를 가진 Limit register, 간단한 산술 연산기로 이루어져있다.

기본적인 MMU에서는, Base register와 Limit registe 레지스터 두 개를 통해서 주소 변환을 하게 된다.

이중에서 책은 ‘base register 기법을 이용한 아주 단순한 MMU 기법을 설명하고 있어 이에 대해 먼저 알아보자.




base register 기법을 이용한 MMU 기법

우선, 기본적으로 base register를 이용하여 변환하는 전체적인 흐름은 CPU를 사용중인 프로세스가 요청하는 논리 주소에 base register에 들어있는 시작 주소를 더해서 물리주소로 변환시키는 것.

예를 들어, 재배치 값이 14000이고, 프로세스가 346번지에 접근할 때, 물리 주소는 이 둘을 더한 값 14346이 되어서 실제로 메인 메모리의 14346번지에 엑세스하게 된다.

이런 식으로 완성된 물리 주소로, 메모리에서 프로세스가 가진 정보를 정확하게 찾아 이용할 수 있게 된다.

그리고 하나 더 알아둘 것은 limit register를 이용하여 올바른 주소 변환 요청을 하는지 체크한다는 것이다.

limit register는 이 프로그램(프로세스)의 크기를 담고 있다.
예를 들어 이 프로그램의 크기는 3000번지까지라고 가정했을 때,
여기서 크기가 3000번지까지 임에도 불구하고, CPU가 4000번지에 있는 내용을 달라는 잘못된 요청을 한다면
이 프로세스 p1, 즉 이 프로그램 바깥의 다른 프로그램이 존재하는 메모리 위치를 요청하는 것이 된다.

잘못된 요청일뿐더러, 어쩌면 악의적인 의도로 다른 프로그램 메모리를 보려고 하는 것일 수도 있기 때문에, limit register는 CPU가 요청한 논리 주소가 혹시 프로그램의 크기보다 더 크진 않는지 체크한다.

그래서 limit register의 값에 벗어나는 요청이면 trap에 걸리게 되고, 하던 일을 멈추고 CPU 제어권을 운영체제에게 넘긴다.




동적 적재 (Dynamic Loading)

앞서 프로세스가 실행되기 위해 그 프로세스 전체가 미리 메모리에 올라와야 한다고 했다. 이 경우, 프로세스의 크기는 메모리의 크기보다 커선 안된다.

메모리 공간을 더 효율적으로 이용하기 위해선 ‘동적 적재’를 하는 것이 좋다.
다이나믹 로딩이란, 말 그대로 메모리에 동적으로 올린다는 것이다.
그때그때 필요할 때마다 메모리에 올리는 것을 말하며,
메모리를 통째로 올리는 것과 비교하면 메모리를 효율적으로 사용할 수 있다.

오류 처리 루틴과 같이 아주 간혹 발생하면서도 실행할 코드가 많은 경우에 특히 유용하다.



동적 연결 및 공유 라이브러리 (Dynamic Linking & Shared Libraries)

Linking을 실행 시간(execution time)까지 미루는 기법

Static linking

  • 라이브러리가 프로그램의 실행 파일 코드에 포함됨
  • 실행 파일의 크기가 커짐
  • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비(printf 함수의 라이브러리 코드)

Dynamic linking

  • 라이브러리가 실행 시 연결(link)됨
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둔다.
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고, 없으면 디스크에서 읽어온다.
  • 운영체제의 도움이 필요
  • 동적 연결 개념은 앞서 말한 동적 적재의 개념과 유사하다.
    동적 적재에서는 로딩(loading)이 실행 시까지 미루어졌었지만,
    동적 연결에서는 연결(linking)이 실행 시기까지 미루어지는 것이다.

  • 우선 Linking이 무엇이냐?
    Linking은 여러 군데 존재하는 컴파일된 파일들을 묶어서 하나의 실행 파일을 만드는 과정을 말한다.
    보통 우리가 프로그램을 만들면 컴파일 하고 그 다음 링크를 해서 실행 파일을 만들게 된다.

  • 그렇다면 Static Linking은 무엇인가.
    라이브러리가 그 예시가 된다. 우리가 코딩하다가 어떤 유용한 라이브러리를 쓰는 경우가 있다. 그런 라이브러리들도 결국엔 링킹이 되어 실행 파일을 만들어주면, 그건 라이브러리 코드가 내 코드 안에 포함되는 것과 마찬가지다.

이런 식으로 링킹이 되는 것을, 즉 라이브러리가 프로그램의 실행 파일 코드에 이미 포함되는 식의 개념을, static linking이라고 한다.


  • Dynamic Linking은 무엇인가?
    라이브러리를 넣을 때, 라이브러리를 별도의 파일로 존재하고 있고 그 라이브러리 위치를 찾을 수 있는 일종의 ‘포인터’ 코드 (stub)만 실행 파일 안에 두고 라이브러리 자체는 포함을 하지 않는 것을 말한다.

프로그램이 실행되다가 해당 라이브러리를 호출하는 부분에 이르면 그 라이브러리가 어디있는지 찾아서 메모리에 올려서 실행시키는 것.


  • 즉, 스태틱 링킹과 다이나믹 링킹을 비교하자면…
    스태틱 링킹은 이미 내가 만든 실행 파일에 포함되어 있어서
    100명이 각각 그 라이브러리를 이용해서 프로그래밍을 하고 그 프로그램 100개를 실행시킨다면 그 코드가 100개가 copy되어서 메모리에 올라가는 것이고
    다이나믹 링킹은 그 코드가 직접 100개 들어가는 게 아니라 그 위치를 찾아서 메모리에 올려 실행하는 게 된다.
    이는 메인 메모리 낭비를 막는 효과를 불러일으킨다.

  • DLL의 또 다른 장점은 이러한 라이브러리를 여러 프로세스 간에 공유할 수 있어 메인 메모리에 DLL 인스턴스가 하나만 있을 수 있다는 것이다.
    예를 들어 100명의 사용자 중에서 다른 사용자에 의해 다이나믹 링킹되는 라이브러리가 이미 메모리에 올라와있다면, 추가로 메모리에 올릴 필요 없이 올라와 있는 그 라이브러리를 같이 공유해서 사용할 수 있을 것이다.
    이처럼 다이나믹 링킹을 해주는 라이브러리를 쉐어드 라이브러리(공유 라이브러리)라고 부른다.
    윈도우, 리눅스 시스템에서 광범위하게 사용되고 있다.



연속 메모리 할당

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

Contiguous allocation (연속 할당)
: 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것

  • Fixed partition allocation (고정 분할 방식)
  • Variable partition allocation (가변 분할 방식)

Noncontiguous allocation (불연속 할당)
: 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음

  • Paging
  • Segmentation
  • Paged Segmentation

메인 메모리는 일반적으로 운영체제를 위한 부분 / 사용자 프로세스를 위한 부분, 2가지 영역으로 나뉘어져 있다.

그리고 여기서 사용자 프로세스 부분의 메인 메모리에 대해 살펴보겠다.

여러 사용자 프로세스가 있을 때, 일반적으로 이 프로세스들이 동시에 메모리에 있는 것을 원할 것이다. 그렇다면 이 메모리를 효율적으로 할당하는 것이 중요하다.

그래서 사용자 프로그램이 올라가는 영역을 관리하는 방법은 크게 2가지가 있다.
연속 할당과 불연속 할당.

연속 할당은 각각의 프로세스가 연속적으로, 통째로 올라가는 방법을 말하고,
불연속 할당은 프로그램을 구성하는 메모리 주소 공간을 잘게 쪼개서 여기저기 분산해서 올리는 방법이다.

이 중에서도 책에서 언급된 가변 분할 방식을 위주로 살펴보자.




가변 분할 방식

고정분할(Fixed partition) 방식

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

가변분할(Variable partition) 방식

  • 프로그램의 크기를 고려해서 할당
  • 분할의 크기, 개수가 동적으로 변함
  • 기술적 관리 기법 필요
  • External fragmentation 발생

이 두 방식은 메모리를 파티션 단위로 분할하는데,
각 파티션에는 정확히 하나의 프로세스만 적재될 수 있다.

여기서 고정분할은 미리 분할 파티션을 영구적으로 고정해놓는 방식이라서 굉장히 융통성이 없다는 문제가 있다.

그래서 보통 가변 분할 방식을 쓰게 되는데, 이 방식도 프로그램이 실행되고 종료되는 과정에서 hole 이라는 메모리의 비어있는 공간이 발생하는 문제가 있다.

그리고 고정분할은 내부 단편화(Internal fragmentation), 외부 단편화(External fragmentation) 문제를 겪고, 가변 분할은 외부 단편화(External fragmentation)를 문제를 겪게 되는데 이 문제는 뒤에 다루고

hole이란 개념 먼저 살펴보자.




Hole

예를 들어 위 그림처럼 프로세스 5, 8, 2가 적재되어 있다면
프로세스 8이 종료된 후 하나의 연속된 공간이 생기는데 이걸 hole 이라고 한다.
나중에 프로세스 9가 들어와 메모리가 할당되고
프로세스 5가 종료된다면 두 개의 비연속적인 hole이 생긴다.

이처럼 일반적으로 메모리에는 다양한 크기의 hole이 여기저기 산재하게 된다.
그럼 운영체제는 이 메모리에서 어느 부분이 사용되고 있고, 어느 부분이 비어있는 hole인지를 관리하고 있을 것이다.

만약 새로운 프로그램이 실행되면, 이 운영체제는 hole 중에 적당한 위치에 그 프로그램을 올리고 그제야 프로그램이 실행될 것이다.
그러면 이 여러 hole 중에 어디에 이 프로세스를 넣을 것인가에 대한 문제가 있다.

이처럼 가변 분할 방식에서 특별히 생기는 문제, 이를 동적 메모리 할당 문제라고 부른다.




동적 메모리 할당 문제

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

1. First-fit

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

2. Best fit

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

3. Worst-fit

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

⇒ (실험 결과)
(1) First-fit과 best-fit이 worst-fit보다 속도와 메모리 이용 효율 측면에서 효과적
(2) 속도는 First-fit이 일반적으로 빠르다.

동적 메모리 할당 문제를 해결하는 방법은 크게 3가지를 이야기할 수 있다.

3가지 알고리즘인데 first-fit은 size가 n 이상인 hole 중에 가장 먼저 발견되는 홀에 할당하는 것을 말한다.

두 번째 Best-fit은 전체를 다 살펴본 다음에 가장 적합한 hole에 넣는 것이다. 그러다보니 탐색하는 데 부담이 따른다고 한다.

세 번째 Worst-fit, 가장 큰 hole에 할당하는 것인데 이름처럼 약간 어리석은 방법이라고 한다.


우선 가장 큰 hole을 찾으려면 마찬가지로 모든 리스트를 탐색해야 한다.
그리고 할당해 주고 남게 되는 가용 공간은 다른 프로세스들을 위해 사용될 수 있는데
이는 또 다른 말로는 큰 hole을 작은 hole로 만든다는 말도 될 수 있다.

즉, 제일 큰 hole에 넣는다는 것은, 나중에 그 hole에 더 적합한, 더 큰 프로그램이 있을 수도 있는데 일단 큰 곳에 넣음으로써 그 큰 hole을 작은 hole로 만들어버리는 것이다.

그렇기 때문에 그다지 좋은 방법은 아니라고 한다.

결론적으로 이 3가지 방법을 이용하여 실험을 해보았을 때,

First-fit 과 best-fit이 시간, 메모리 이용 효율 측면에서 worst-fit보다 좋다는 것이 입증되었고,

공간 효율성 측면에서 First-fit, best-fit 둘 중에 어느 것이 항상 더 좋다고 말할 수 없지만 속도는 일반적으로 first-fit이 빠른 것으로 나타났다고 한다.




단편화

아까 앞서 말한 것처럼 단편화 문제에는 외부 단편화, 내부 단편화가 있는데.
그 중 first-fit 전략과 best-fit 전략은 모두 외부 단편화로 인해 어려움을 겪는다고 한다.

  • 그럼 일단 단편화 문제가 뭔지 알아보자.

우선 앞서 말한 것처럼 단편화 문제에는 ‘내부 단편화, 외부 단편화’가 있다.
예를 들어 이 그림처럼 100MB의 메모리에 80MB 크기의 프로세스를 올릴 거라고 해보자.

내부 단편화

내부 단편화는 그림처럼 작은 크기의 잔여 메모리가 발생해 해당 메모리를 사용할 수 없게 되는 것을 말한다.
이처럼 내부 단편화는 프로그램의 크기보다 분할의 크기가 큰 경우
하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각이라고 할 수 있겠다.



외부 단편화

반면 외부 단편화는 프로그램의 크키보다 할당되는 분할의 크기가 작은 경우를 말한다.

그림과 같이 남아있는 메모리 공간은 50MB+50MB =100MB로 요청한 메모리 공간 80MB보다 크지만, 남아있는 공간이 연속적이지 않아 Process C를 할당할 수가 없게 된다. 따라서 남아있는 메모리 공간이 낭비되게 되는 문제가 발생한다.



정리

External fragmentation (외부 단편화)

  • 프로그램 크기보다 분할의 크기가 작은 경우
  • 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할

Internal fragmentation (내부 단편화)

  • 프로그램 크기보다 분할의 크기가 큰 경우
  • 하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각
  • 특정 프로그램에 배정되었지만 사용되지 않는 공간

그래서 단편화 문제를 정리하면 이와 같다.

앞서 말한 first-fit과 best-fit 전략은
프로세스들이 메모리에 적재되고 제거되는 일이 반복되면서, 메모리에 너무 많은 수의 작은 조각들이 분산되는 ‘외부 단편화 문제’가 발생할 수 있다는 것이다.

즉, 메모리가 너무 많은 수에 너무 작은 조각들로 단편화되어 효율적으로 쓰기 어려워 진다.




Compaction

Compaction

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

그래서 이를 해결하기 위한 여러 방법들이 등장하는데
그 중 compaction (압축)이 있다.

그림처럼 외부 단편화로 인해 생기는 메모리 조각들,
즉 hole을 한 곳으로 몰아서 큰 블록을 만드는 것이다.

흩어져 있던 공간을 연속된 공간, 즉 하나의 공간으로 만들면 기존에 할당 할 수 없던 프로세스를 할당할 수 있게 된다.
그러나 이 압축 방법이 쉬운 방법이 아니다.

프로그램 하나만 영향을 미치는 게 아니라 전체 프로그램의 바인딩과 관련된 문제이기 때문에, 굉장히 복잡하고 비용이 많이 드는 작업이라고 한다.

또한 이 압축 방법이 항상 가능한 것도 아니다.
적어도 런타임 바인딩이 지원되어야 한다. 즉 그 메모리 위치가 실행 중에도 변경될 수 있는 기능이 지원되어야만 compaction을 할 수 있을 것이고.

이외에도 고려해야 할 문제가 많다고 한다.


페이징

외부 단편화 문제를 해결할 수 있는 다른 방법은 “한 프로세스의 논리 주소 공간을 여러 개의 비연속적인 공간으로 나누어 필요한 크기의 공간이 가용해지는 경우 물리 메모리를 프로세스에 할당하는 방법이다. 이는 컴퓨터 시스템에서 가장 일반적인 메모리 관리 기법인 페이징에서 사용되는 전략이다.”

<사용자 프로세스 영역의 할당 방법>
1. Contiguous allocation (연속 할당)
: 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것

  • Fixed partition allocation (고정 분할 방식)
    - Variable partition allocation (가변 분할 방식)

  1. Noncontiguous allocation (불연속 할당)
    : 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
  • Paging
  • Segmentation
  • Paged Segmentation

실제로 현대 컴퓨터 시스템에서 사용하는 방법은 연속 할당이 아닌 불연속할당이기 때문에, 비교적 이런 단편화 문제들로부터 자유롭다고 한다.

그래서 책에서도 외부 단편화에 대한 또 다른 해결책으로 불연속할당 방법인 ‘페이징’을 제시하고 있다.

지금까지는 연속 할당의 경우인 ‘고정 파티션, 가변 파티션’, 그에 따른 단편화 문제를 이야기를 했었고,

이제는 여러 개의 비연속적인 공간으로 나누는 ‘불연속 할당’, 그 중 Paging 기법을 중심으로 살펴볼 것이다.



페이지 / 프레임

페이징
논리 메모리 - 페이지(page)
물리 메모리 - 프레임(frame)

우선, 페이징은 위의 그림처럼 주소 공간이 동일한 크기의 블록으로 나누어진다.
논리 메모리는 페이지(page)라 불리는 블록으로,
물리 메모리는 프레임(frame)이라는 블록으로 나누어진다.

그리고 페이징은 프로그램을 구성하는 논리적인 메모리를 각각의 페이지별로 물리적인 메모리의 비어있는 곳 어디든, 적당한 위치에 올라갈 수 있게 해주는 방법이 페이징이다.

그렇다면 이 페이징의 경우, 주소 변환이 앞서 말한 것처럼 단순히 시작 위치를 더해서 이루어질 수 있는 게 아니라, 각각의 페이지 별로 주소변환을 해주는 방법이 필요하다.




페이지 테이블

페이징 기본 방법(Basic Method)

  • physical memory를 동일한 크기의 frame으로 나눔
  • logical memory를 동일 크기의 page로 나눔 (frame과 같은 크기)
  • 모든 가용 frame들을 관리
  • page table을 사용하여 logical address를 physical address로 변환
  • External fragmentation 발생 안 함
  • Internal fragmentation 발생 가능

그래서 이 페이징 기법에는 주소 변환을 위한 ‘페이지 테이블’이란 것이 사용된다.

각각의 논리적 페이지들이 물리적 메모리의 어디에 올라가 있는지 알려주는 테이블이라고 생각하면 된다.

그래서 이 페이지 테이블은 논리적인 메모리의 페이지 개수만큼 엔트리가 존재하게 된다.

그림에서 보이듯 이 페이지 개수만큼 테이블 엔트리가 존재하고, 각각의 테이블의 엔트리엔 그 페이지가 몇 번 물리적인 프레임에 올라가 있는지를 나타내주고 있다.

page 0은 1번 프레임, page 1은 4번 프레임, page 2는 3번 프레임, page 3은 7번 프레임에 있다는 것을 알 수 있다.

그래서 페이지 번호만 안다면 페이지 테이블을 통해 바로 프레임 번호를 찾아서 주소 변환을 해줄 수 있을 것이다.



  • 이걸 다른 구조로 보면 이와 같은 그림이 된다.

  • CPU에서 나오는 모든 주소는 페이지 번호(p)와 페이지 오프셋(d)으로 나누어진다.
    • 페이지 테이블은 물리 메모리의 각 프레임의 시작 주소를 저장하고 있고, 오프셋은 참조되는 프레임 안에서의 위치이다.
    • 따라서, 프레임의 시작 주소와 페이지 오프셋이 결합하여, ‘물리 메모리 주소’가 된다.

CPU에서 나오는 모든 주소는 페이지 번호(p)와 페이지 오프셋(d) 두 개의 부분으로 나누어진다.
페이지 테이블은 물리 메모리의 각 프레임의 시작 주소를 저장하고 있고, 오프셋은 참조되는 프레임 안에서의 위치이다.
따라서, 프레임의 시작 주소와 페이지 오프셋이 결합하여 물리 메모리 주소가 된다.

즉, 논리 주소 → 물리 주소 변환 단계를 정리하면…
1. 페이지 번호 p를 추출하여 페이지 테이블의 인덱스로 사용
2. 페이지 테이블에서 해당 프레임 번호 f를 추출
3. 논리 주소의 페이지 번호 p를 프레임 번호 f로 바꿈
(오프셋 d는 변하지 않으므로 대체되지 않음)

이런 단계를 거치게 되는데
오프셋 d는 변하지 않기 결국 논리적인 페이지 번호를 물리적인 프레임 번호로 바꿔주기만 하면 주소 변환이 된다.


  • 그렇다면 이 페이지 테이블이 어디에 들어있을까?

이를 알아보기 전에 페이지 테이블의 용량에 대한 이해가 필요하다.
우선 페이지는 2의 거듭제곱으로, 보통 4KB로 자른다.
여기서는 페이지 테이블의 엔트리가 4개인데, 실제로는 100만 개 정도가 필요하다고 한다.

그런데 중요한 것은, 이게 프로그램 하나를 이렇게 여러 개의 페이지로 자르는 거라서
프로그램 하나의 주소 공간이 100만 개 페이지로 잘린다는 뜻이 된다.
즉, 프로그램 마다 별도의 페이지 테이블이 존재해야 하기 때문에 많은 용량이 필요해진다.

그렇다면 이 페이지 테이블을 어디에 넣는 것이 적합할까…

용량이 작다면 레지스터를 사용하는 게 적합하지만,
그러나 대부분의 현대 CPU는 훨씬 큰 페이지 테이블을 구현할 필요가 있기 때문에 용량이 많이 필요하다.

  • 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번
    ⇒ 접근 시간 2배
  • 속도 향상을 위해 translation look-aside buffer (TLB)라고 불리는 고속의 lookup hardware cache 사용

그래서 대부분의 컴퓨터는 페이지 테이블을 ‘메인 메모리’에 저장하고, 페이지 테이블 기준 레지스터 (PTBR)로 하여금 페이지 테이블을 가리키도록 한다.

그렇기 때문에 페이징 기법으로 데이터에 엑세스하라면 실제로 두 번의 메모리 엑세스가 필요하다. 따라서 메모리 접근 시간은 2배로 느려지고 이는 대부분 상황에서 허용할 수 없는 지연 시간이다.

그래서 이 문제를 해결하기 위해 TLB(translation look-aside buffers)라고 불리는 특수한 소형 하드웨어 캐시가 사용된다.

속도를 개선하기 위해 TLB 라는 캐시 메모리를 이용해서 빈번이 참조되는 일부 엔트리를 캐싱하는 것이다.




TLB

TLB는 페이지 테이블과 함께 다음과 같이 사용된다.

  • 우선 TLB는 페이지 테이블의 일부분만 저장한다.
    그리고 CPU가 논리 주소를 생성하면 MMU는 해당 페이지 번호가 TLB에 있는지 확인한다.
    TLB에서 페이지 번호가 발견되면 이를 TLB hit 라고 하며, 해당 프레임 번호를 즉시 알 수 있어 메모리를 접근하는데 사용된다.

  • 페이지 번호가 TLB에 없으면 TLB 미스라고 하는데, 이럴 경우 어쩔 수 없이 오리지널 페이징 기법대로 페이지 테이블을 참고하며 어쩔 수 없이 메모리에 2번 접근한다.
    (이렇게 미스가 나면 어쨌든 2번 참조하니까 수행 속도에 크게 나아지지 않을 것 같다고 생각할 수 있지만, 대부분의 프로세스는 한번 참조했던 곳을 다시 참조할 가능성이 높기 때문에 크게 우려하지 않아도 된다고 함.)

  • 그리고 TLB는 key-value 형태로,

논리적인 페이지 번호 page number P와 그에 대한 주소 변환된 프레임 번호 frame number F, 이 두 개를 쌍으로 가지고 있어야 한다.

이게 일반적인 페이지 테이블과의 차이점이다.

그런데 여기서 중요한 점은
페이지 테이블이 각각의 프로세스 별로 존재한다는 점이다.
즉 이 페이지 테이블의 일부를 담는 TLB도 프로세스마다 다른 정보가 될 것이다.
그렇기 때문에 이 TLB에 있는 정보는 새 프로세스가 컨텍스트 스위치를 해서 실행할 경우,
다른 실행 프로세스가 주소 변환을 잘못하지 않도록 flush를 해서 TLB 안에 있는 모든 엔트리를 비워야만 한다.




페이지 테이블의 구조

페이지 테이블을 구성하는 일반적인 방법

  • 계층적 페이징
  • 해시 페이지 테이블
  • 역 페이지 테이블

이제 페이지 테이블을 구성하는 가장 일반적인 방법을 살펴보자.
책에서는 ‘계층적 페이징, 해시 페이지 테이블, 역 페이지 테이블’을 소개하고 있다.



계층적 페이징

  • 2단계 페이징

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

  • 32비트 address 사용시 : 2의 32승(4GB)의 주소 공간
  • page size가 4KB일 경우, 100만(2의 32승 / 2의 12승 = 2의 20승)개의 page table 필요
  • 그러나 대부분의 프로그램은 4GB의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비된다.

우선 계층적 페이징을 먼저 살펴보자.

일단 현대 컴퓨터는 매우 큰 주소 공간(2의 32승에서 2의 64승 → 32비트에서 64비트)를 가지고 있다. 이러한 환경에서는 페이지 테이블도 상당히 커진다.

예를 들어, 32비트 논리 주소 공간을 가진 시스템이 있다면 4GB까지 표현할 수 있다.

여기서 페이지의 크기가 4KB (2의 12승) 로 자른다면, 페이지 테이블은 100만 (2의 20승 = 2의 32승 / 2의 12승)개 이상의 페이지 테이블 엔트리로 구성될 것이다.

거기에 각각의 페이지 테이블 엔트리가 4B로 구성되기 때문에
4B * 100만하면 4MB, 즉 각각의 프로세스마다 페이지 테이블만을 위해서 4MB의 공간이 필요하다.

하지만 대부분의 프로그램은 4GB의 주소 공간 중 일부분만 사용하므로 page table 공간이 심하게 낭비된다고 함

왜냐하면 이 페이지 테이블은 배열 같은 거라서, 인덱스를 통해서 접근을 하는데 중간에 사용 안하는 페이지가 있다고 해서 해당 부분을 비우고 페이지 테이블을 만들 수 없기 때문




이를 해결하기 위한 방법 중 하나로,
페이지 테이블을 여러 개의 작은 조각으로 나누는 것이 있는데
이것도 여러 가지 방법이 가능하다.

그 중 하나의 방법은 2단계 페이징 기법이다.
페이지 테이블 자체가 다시 페이징되게 하는 것이다.

우선 우리가 지금까지 살펴본 이 페이지 테이블은 그림처럼 1단계로 구성된 거였다.
그런데 2단계 페이지는 이 페이지 테이블이 두 단계로 존재하는 것을 말한다.

예를 들면 서울시 마포구 ← 이런 식으로 주소 체계를 계층적으로 하나 더 주는 것과 같다.
(서울시 밑에 마포구, 강남구, 등등 있는 것럼...)

그래서 이 그림과 같은 형태가 된다.

바깥쪽 페이지 테이블 엔트리 하나 당 안쪽 페이지 테이블이 하나씩 만들어지는 것이다.

그렇게 되면 안쪽 페이지 테이블이 굉장히 여러 개가 생길 것.



그래서 주소를 찾는 과정은 위와 같다.

가장 바깥쪽 logical address에서 outer page table의 인덱스를 찾을 페이지 번호를 가지고 가서, p1 번째 엔트리로 가서 주소 변환 정보를 얻는다.

그러면 저 색칠된 부분을 얻는데, 저 부분이 곧 여러 개의 안쪽 페이지 테이블 중 어떤 페이지 테이블인지를 알려준다.

요걸 이용해서 p2번째 엔트리에 가면 물리적인 페이지 프레임 번호를 얻게 된다.

이 페이지 프레임 번호를 덮어씌우면 그 페이지 프레임이 나오고,
그 페이지 안에서 오프셋 d 번째만큼 떨어진 위치에서 원하는 정보를 찾을 수 있다.



# 2단계 페이지 테이블 기법

  • page table 자체를 page로 구성
  • 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL
    (대응하는 inner page table이 없음)

정리하자면 지금까지 설명한 것처럼 2단계 테이블 기법은 페이지 테이블 자체를 페이지로 구성하는 것이고,

그리고 아까 2단계 페이지 테이블을 쓰는 이유가 구성하는 공간 중 사용하지 않는 부분에 대한 공간 낭비를 막기 위함이라고 했다.

실제로 이 기법을 사용하면, 사용이 안 되는 주소에 대해서 안쪽 페이지 테이블 안 만들어지고 포인터가 그냥 널 상태로 되어있게 된다.


64비트의 페이지 테이블

(2의 64승 / 2의 12 승 → 2의 42승)

하지만 64 비트 논리 주소 공간을 갖는 시스템에서는 2단계 페이징 기법도 적절하지 않다.

예를 들어 페이지 크기가 4KB(2의 12승)라고 할 경우, 64비트의 경우 주소는 위의 그림과 같이 가지게 된다.

outer 페이지 테이블은 2의 42승 엔트리를 가지고 되고, 2의 44승 바이트로 구성된다.

아까 32비트의 2단계 페이징을 했을 떄 아우터 페이지 테이블의 엔트리가 2의 10승이었던 것을 감안하면 outer page의 크기가 크다.

그럼 큰 아우터 페이지 테이블을 피하기 위해서 아우터 페이지 테이블을 한번 더 작게 나누면 해결이 될까?

그러면 3단계 페이징을 해야한다.



그래도 여전히 외부 페이지가 2의 32승개 엔트리, 즉 2의 34 바이트, 즉 16기가 바이트의 크기를 요구한다.

여기서 4단계 페이징을 해서 2단계 외부 페이지 테이블도 페이징해줄 수 있을 것이다.

하지만 64비트 UltraSPARC 구조는 7단계 페이징을 해야 하며 각 논리 주소를 얻기 위해 너무 많은 메모리 접근을 필요로 하게 된다.

이 예시를 통해 볼 수 있듯 64비트 구조에는 계층적 페이지 테이블이 부적합하다는 것을 알 수 있다.


해시 페이지 테이블

주소 공간이 32비트보다 클 경우,
논리 주소를 해시로 사용하는 ’해시 페이지 테이블’을 많이 사용

해시 테이블의 각 엔트리는 연결 리스트를 가지고 있으며
각 원소는 3가지 부분으로 나눈다.

(1) 논리 주소의 페이지 번호,
(2) 매핑된 페이지 프레임의 값,
(3) 연결 리스트의 다음 원소를 가리키는 포인터

그래서 주소 공간이 32비트보다 커지면 논리 주소를 해시로 사용하는 해시 페이지 테이블을 많이 쓴다.
해시 값이 곧 논리 주소의 페이지 번호가 되는 것임.

그래서 해시 페이지 테이블의 알 고리즘은 다음과 같다.

해시 함수를 통해서 논리 주소의 페이지 수(p)를 해싱하여 해시 테이블에서 찾아보고, 논리 페이지 수를 연결 리스트의 1번 원소와 비교함.

만약 둘이 같다면 해당하는 페이지 프레임를 통해 원하는 물리 주소를 반환한다.
만약 같은 원소가 없다면 연결리스트의 다음 원소와 비교함.

이거의 반복이다.



역 페이지 테이블

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)
  • 단점 : 테이블 전체를 탐색해야 함
  • 조치 : TLB(associative register) 사용 → but 비쌈
  • 이 그림처럼 인버티드 페이지 테이블은 원래 페이지 테이블을 통한 주소 변환을 완전히 역발상으로 뒤집어 놓은 것이다.

원래 이 페이지 테이블이 프로세스마다 존재했는데, 인버티드 페이지 테이블은 시스템 안에 페이지 테이블이 딱 하나만 존재하는 것을 말한다.

즉, 페이지 테이블에 엔트리가 프로세스의 페이지 개수만큼 존재하는 게 아니고
물리적인 메모리에 페이지 프레임 개수만큼 존재하는 것이다.

그리고 각 엔트리는 그 프레임에 올라와 있는 페이지 주소, 그리고 그 페이지를 소유하고 있는 프로세스의 ID를 표시하고 있다.


  • 그렇다면 주소 변환은 어떻게 하느냐?

원래는 p번 페이지를 주소변환하고 싶어서 p번째 엔트리에 가면 페이지 프레임 번호가 몇 번인지 나오는 방향이었지만,

역방향으로 페이지 프레임 i번째 엔트리에 가면 거기서 논리적 페이지 번호가 나와서 이를 통해 주소 변환을 하는 식으로 주소 변환을 해야한다.

그니까 우리는 논리 주소를 통해서 물리적인 주소를 알아내야만 하는데,
이 물리 주소를 통해서 논리 주소로 바꾸는 테이블에서 어떻게 찾고 어떻게 주소 변환을 하느냐?

이 논리 주소에 해당하는 페이지 번호 p가 물리 메모리의 어디에 있는지 찾기 위해서 전체 엔트리를 다 뒤져봐야 한다.

즉, 전체를 전부 탐색해서 i번째 엔트리에서 해당하는 페이지 번호 p가 나와서 알아내는 방식인 것


  • 원래 페이지 테이블의 장점은 배열처럼 인덱스를 통해서 위에서 p번째 떨어진 위치를 바로 검색하는 게 장점이었다.
    하지만 인버티드는 그런 장점 없이 전체를 검색해야하는데 왜 쓰는 걸까?

결국 공간이 줄어들기 때문이다. 시스템 안에 하나만 존재하니까 공간을 많이 줄일 수 있지만 대신 시간적인 오버헤드가 발생하게 되는 것

→ 그래서 이 문제를 해결하기 위해 TLB를 이용하고 해시 테이블을 이용한다.

TLB는 associative (어소시어티브) 레지스터를 사용해서 병렬적으로 동시에 검색이 가능하기 때문에 이런 시간적 오버헤드를 줄일 수 있다.



연습문제 중 하나

  1. 페이지 테이블의 두 항목이 메모리의 동일한 페이지 프레임을 가리키도록 하는 효과는 무엇인가?
    이 효과를 사용하여서 한 장소에서 다른 장소로 많은 양의 메모리를 복사하는 데 필요한 시간을 줄일 수 있는 방법을 설명하라.
    한 페이지의 일부 바이트를 수정하면 다른 페이지에 미치는 영향은 무엇인가?

By allowing two entries in a page table to point to the same page frame in memory, users can share code and data. If the code is reentrant, much memory space can be saved through the shared use of large programs such as text editors, compilers, and database systems. “Copying” large amounts of memory could be effected by having different page tables
point to the same memory location.
However, sharing of nonreentrant code or data means that any user having access to the code can modify it and these modifications would be reflected in the other user’s “copy

페이지 테이블의 두 항목이 동일한 페이지 프레임을 가리키도록 허용함으로써 메모리에서 사용자는 코드와 데이터를 공유할 수 있습니다.

만약 코드가 재진입 가능한 경우 텍스트 편집기, 컴파일러 및 데이터베이스 시스템과 같은 대용량 프로그램의 공유 사용을 통해 메모리 공간을 절약할 수 있습니다.

많은 양의 메모리를 복사하는 것은 다른 페이지 테이블들이 동일한 메모리 위치를 가리키도록 함으로써 영향을 받을 수 있다.

그러나 비재진입 코드 또는 데이터 공유는 모든 사용자가 코드에 엑세스할 수 있으면 코드를 수정할 수 있으며 이러한 수정은 다른 사용자의 "카피"에 반영됩니다



출처

[10분 테코톡] 🤷‍♂️ 현구막의 리눅스 메모리 관리

운영체제

[운영체제] 내부 단편화, 외부 단편화란? | 외부단편화 해결 방법

운영체제 (공룡책) - 9

Operating System Concept 9장

profile
모종삽에서 포크레인까지

0개의 댓글