[운영체제] 9. 메모리 관리

2022.06.11 - [컴퓨터 공학/0 +운영체제] - [운영체제] 8. Scheduling 기법(2) -유닉스/리눅스 스케줄링

[운영체제] 8. Scheduling 기법(2) -유닉스/리눅스 스케줄링

 

지난 포스팅에서는 유닉스/리눅스 스케줄링에 대해서 소개 했다..

 

이번에는 메모리관리에 대해서 포스팅해보겠다..

 

어딘가 들어본듯 한 이 멜로디~

떠올라 작은 기억들이 마이 메모리~

 

지난 번 내용에 대해서 포스팅하다가 너무 어려움을 느껴서 구(구글)선생님에게 물어본 결과

http://www.kocw.net/home/search/kemView.do?kemId=1046323 

운영체제

 

위와 같은 강의가 있다는 것을 알게 되었다..! 꼭 들어보시는 것을 추천하고 강의에는 따로 강의 자료가 없어 아래 책도 사는 것을 추천한다.

아래 포스팅은 운영체제와 정보기술의 원리를 정리한 내용이다.

http://www.yes24.com/Product/Goods/90124877

운영체제와 정보기술의 원리 - YES24

 

 

---

 

 

 

메모리 관리

우리가 사는 집마다 고유의 주소가 있듯이 메모리 역시 주소를 통해 접근하는 장치이다.

우리가 사용하는 컴퓨터는 32 또는 64bit 주소체계 이다.

컴퓨터 상의 주소는 32비트를 그대로 사용하지 않고, 효율적인 운영을 위해 연속된 일련의 영역을 나누어 사용한다.

우리도 주소를 '서울특별시 동대문구 서울시립대로 163' 이런식으로 계층적으로 나누는 것처럼 말이다.!

보통 컴퓨터는 4KB(=2^12byte)단위로 묶어서 페이지(page)라는 하나의 행정구역을 만든다.

페이지 하나의 크기가 4KB이므로 페이지 내에서 바이트별 위치 구분을 위하여 12비트가 필요하다.

따라서 전체 32비트의 주소 중 하위 12비트는 페이지 내에서 주소를 나타낸다.

 

그러면 프로그램이 물리적 메모리에 어떻게 적재되어 주소를 할당 받는거지??????

 

---

 

주소 바인딩(address binding)

주소 바인딩은 프로세스의 논리적 주소를 물리적 주소(메모리)로 연결 시켜주는 작업이다.

논리적 주소(가상 주소)란
프로그램이 실행을 위해 메모리에 적재되면 프로세스를 위한 독자적인 주소 공간이다.

 

CPU는 프로세스마다 독립적으로 갖는 논리적 주소에 근거하여 명령을 실행한다.

논리적 주소는 각 프로세스마다 할당되며 0번지부터 시작한다.

물리적 주소는 물리적 메모리에 실제로 올라가는 위치를 말한다.

일반적으로 물리적 메모리의 낮은 주소 영역에는 운영체제, 높은 주소 영역에는 사용자 프로세스들이 올라간다.

결국 프로세스가 실행되기 위해서는 물리적 메모리에 올라가 있어야하는데, 

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

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

 

주소 바인딩의 종류

• 컴파일 타임 바인딩(절대코드를 생성하는 바인딩 방식)
  • 물리적 메모리 주소가 프로그램을 컴파일할 때 결정되는 주소 바인딩 방식
  • 물리적 메모리의 위치를 변경하고 싶으면 컴파일을 다시 해야함
  • 현대의 시분할 컴퓨팅 환경에서는 잘 사용하지 않음
• 로드 타임 바인딩
  • 프로그램 실행이 시작될 때 물리적 메모리 주소가 결정되는 주소 바인딩 방식
  • 로더(loader)의 책임하에 물리적 메모리 주소가 부여
    • 로더란 사용자 프로그램을 메모리에 적재 시키는 프로그램
  • 프로그램이 종료될 때까지 물리적 메모리상의 위치 고정 
  • 컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우에 가능함
• 실행 시간 바인딩
  • 프로그램이 실행을 시작한 후에도 그 프로그램이 위치한 물리적 메모리상의 주소가 변경될 수 있는 바인딩 방식
  • CPU가 주소를 참조할 때마다 해당 데이터가 물리적 메모리의 어느 위치에 존재하는지 주소 매핑 테이블(address mapping table)을 이용해 바인딩을 점검
  • 기준 레지스터, 한계 레지스터가 필요함
    • 실행시간 바인딩 방식이 가능하기 위함
  • MMU(Memory Management Unit)라는 하드웨어지원이 뒷받침 되어야함
    • MMU란 논리적 주소를 물리적 주소로 매핑해주는 장치

 

 

MMU 기법

CPU가 특정 프로세스의 논리적 주소를 참조하려고 할 때

MMU 기법은 그 주소값에 기준 레지스터의 값을 더해 물리적 주소값을 얻어낸다.

reloactaion register(재배치 레지스터)는 기준 레지스터라고 불린다.

MMU기법은
프로그램의 주소 공간이
물리적 메모리의 한 장소에
연속적으로 적재되는 것을 가정한다.

따라서, 물리적 메모리상의 시작주소만 알면 주소변환을 쉽게 할 수 있다.
사용자 프로그램이나 CPU는 노리적 주소만 다를 뿐, 실제 물리적 주소는 알지 못하며 알아야 할 필요도 없다. 

CPU는 프로세스의 논리적 주소가 346이면 물리적 주소가 시작위치인 14000을 더해서 물리적 주소 14346을 참조하게 된다.

이때 논리적 주소는 346번지는 물리적 메모리의 시작위치인 재배치 레지스터값으로부터 요청된 위치가 얼마나 떨어져 있는지를 나타내는 offset의 개념으로 생각 할 수도 있다.

 

프로그램이 여러개 실행될때는??😨

프로세스는 자기 자신만의 고유한 주소 공간을 갖고 있다.
따라서 동일한 논리적 주소라고 하더라도 각 프로세스마다 서로 다른 내용을 담고 있다.

예를 들어
cpu가 논리적 주소 100번지를 참조한다고 했을 때
현재 cpu에서 수행되고 있는 프로세스가 무엇인지에 따라서
100번지가 가리키는 내용은 다르다.

MMU기법에서는 문맥교환으로 cpu에서 실행 중인 프로세스가 바뀔 때마다
재배치 레지스터 값을 그 프로세스에 해당되는 값으로 재설정 해서 각 프로세스에 맞는 물리적 주소에 접근하는 것을 지원한다.

 

물리적 메모리의 공간을 벗어나는 경우?😱

그렇다. 논리적 주소와 재배치 레지스터안에 있는 값을 더한 결과가 물리적 주소 공간을 벗어나는 경우가 발생 할 수 있다.그래서 앞에서 언급했듯이 한계 레지스터(limit register)가 필요하다.한계 레지스터는 자신의 주소 공간을 넘어서려는 메모리 참조를 하려고 하는 확인하는 용도로 사용된다.현재 cpu에서 수행 중인 프로세스의 논리적 주소의 최댓값을 갖고 있다.(해당 프로세스의 크기를 담고 있다.)

 

 

위 그림처럼 cpu가 메모리 참조 요청을 했을 때 그 주소가 limit register보다 큰지 먼저 확인 한다.

이처럼 물리적 메모리 영역에 대한 보안을 유지 한다.

1. 논리적 주소값이 한계 레지스터 내에 저장된 그 프로세스의 크기보다 작은지 확인

2. 작다면 논리적 주소값에 재배치 레지스터값을 더해 물리적 주소를 구하여 해당 물리적 메모리에 접근하도록 허락한다.

3. 크다면 trap을 발생시켜 해당 프로세스를 강제종료 시킨다.

 

---

 

 

이제 메모리와 관련된 용어를 알아보도록 하자.

 

동적로딩(dynamic loading)

나중에 나오겠지만, 중첩(overlays)과 개념적으로 비슷하다.

여러 프로그램이 동시에 메모리에 올라가서 수행되는 다중 프로그램 환경에서 메모리 사용의 효율성을 높이기 위해 사용하는 기법이다.

프로세스의 주소 공간에 전체가 메모리에 적재되는 환경이 아니라,

메모리를 좀더 효율적으로 사용하겠다는 말이다.

 

어떻게 효율적으로 사용해??

해당 부분이 불릴 때 그 부분만 메모리에 적재하는 방식을 이용한다.

즉 프로세스 내에서 실행에 필요한 부분이 실제로 불릴 때마다 메모리에 적재하는 것을 말한다.

다시말해서 사용되지 않을 많은 양의 코드가 메모리에 올라가는 것을 막아 메모리를 좀 더 효율적으로 사용할 수 있도록한다.

동적로딩으로 같은 크기의 물리적 메모리에 더 많은 프로그램을 적재 할 수 있다.

운영체제의 특별한 자원 없이 프로그램 자체에서 구현이 가능하고, 운영체제가 라이브러리를 통해 지원 할 수도 있다.

실제 프로그램의 코등 중 상당 부분은 오류 처리루틴과 같이 아주 특별한 경우에만 가끔씩 사용되는 방어용 코드이다.
따라서 프로세스의 주소 공간전체를 물리적 메모리에 올리는 경우 자주 발생하지는 않지만 많은 메모리를 사용하는 이러한 오류 처리 코드가 메모리 공간의 상당 부분을 차지하게 되어 메모리의 낭비가 초래된다.

 

 

동적연결(dynamic linking)

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

*연결이란
프로그래머가 작성한 소스 코드를 컴파일하여 생성된 목적 파일과, 이미 컴파일된 라이브러리 파일들을 묶어 하나의 실행파일을 생성하는 과정을 말한다.

라이브러리 실행 시점에 연결이 된다.

실행 파일에 라이브러리 코드가 포함되지 않으며, 프로그램이 실행되면서 라이브러리 함수를 호출할 때가 되어서야 라이브러리에 대한 연결이 이루어진다.

동적연결을 가능하기 위해서는 실행파일의 라이브러리 호출부분에 스텁(stub)이라는 작은 코드를 둔다.

stub: 해당 라이브러리의 위치를 찾기위함

라이브러리 호출시 스텁을 통해 해당 라이브러리가 메모리에 이미 존재하는지 살펴보고
이미 존재하면 그 주소의 메모리 위치에서 직접 참조하며,
존재하지 않다면 디스크에서 동적 라이브러리 파일을 찾아 메모리로 적재한 후 해당 코드를 실행한다.

 

다수의 프로그램의 공통으로 사용하는 라이브러리르 메모리에 한 번만 적재하기 때문에 메모리 사용 효율성을 높일 수 있다!!!🤗

이러한 동적연결 기법은 운영체제 지원이 필요하다.

 

대비되는 개념인 정적연결은 프로그래머가 작성한 코드와 라이브러리 코드가 모두 합쳐져서 실행파일이 생성된다.

모두 합쳐지기 때문에 실행파일의 크기가 상대적으로 크고, 동일한 라이브러리를 각 프로세스가 개별적으로 메모리에 적재해야 하므로 물리적 메모리가 낭비되는 단점이 있다.

비록 동일한 라이브러리 코드라 하더라도 각 프로레스의 주소 공간에 독자적으로 존재하는 코드이기 때문에 별도의 적재가 필요하다.

 

 

중첩(overlays) = 수작업 중첩(manual overlays)

프로세스의 주소 공간을 분할해 실제 필요한 부분만을 메모리에 적재하는 기법을 말한다.

동적로딩과 개념적으로 유사하지만, 사용하는 이유는 다르다..!

중첩은
초창기 컴퓨터 시스템에서 물리적 메모리의 크기 제약으로 인하여
하나의 프로세스 조차도 메모리에 한꺼번에 올릴 수 없을 때,
프로세스의 주소 공간을 분할해서 당장 필요한 일부분을 메모리에 올려 실행하고
해당 부분에 대한 실행이 끝난 후에 나머지 부분을 올려 실행하는 기법을 의미한다.

즉 프로그램의 크기가 물리적 메모리의 크기에 비해 작다면 주소 공간 전체를 한꺼번에 올릴 수 있지만 그렇지 않다면 분할해 메모리에 올리는 것

if(프로그램 크기 < 물리적 메모리 크기) 한꺼번에 적재;
else 프로세스의 주소 공간 분할하여 메모리에 적재;


동적로딩은
다중 프로그래밍 환경에서 메모리의 이용률을 향상 시키기 위해 프로세스의 주소 공간 중 당장 실행에 필요한 부분을 그때그때 메모리에 동적으로 올린다.

 

동적로딩은 메모리에 더 많은 프로세스를 동시에 올려놓고 실행하기 위해서 사용..!

중첩은 단일 프로세스만을 메모리에 올려 놓는 환경에서 메모리 용량보다 큰 프로세스를 실행하기 위한 어쩔 수 없는 선택..!

 

중첩은 운영체제 지원 없이 개발자에 의해 구현했다.(해당 과정은 매우 복잡하다....)

 

 

스와핑(swapping)

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

스왑영역은 backing store라고 부르며, 디스크 내에 파일 시스템과는 별도로 존재하는 일정 영역을 말한다.

 

스와핑의 가장 중요한 역할은
메모리에 존재하는 프로세스의 수를 조절하는 것이다.
즉 다중 프로그래밍의 정도(degree of multiprogramming)를 조절할 수 있다. 

 

파일 시스템은 비휘발성 저장공간임에 비해 스왑영역은 프로세스가 수행 중인 동안에만 디스크에 일시적으로 저장하는 공간이므로 저장 기간이 상대적으로 짧은 저장공간이다.

• 다수의 사용자 프로세스를 담을 수 있을 만큼 충분히 큰 저장공간이여 하고
• 접근 속도도 어느정도 보장되어야 한다.

주의 할 점은 스와핑은 프로세스가 종료되어 그 주소공간을 디스크로 내쫓는 것이 아니라,

특정한 이유로 수행 중인 프로세스의 주소 공간을 일시적으로 메모리에서 디스크로 내려놓는 것을 의미한다.

• 스왑 인(swap in)
  • 디스크에서 메모리로 올리는 작업
• 스왑 아웃(swap out)
  • 메모리에서 디스크로 내리는 작업

1. 스와핑은 스와퍼라고 불리는 중기스케줄러에 의해 스왑 아웃 시킬 프로세스를 선정
2. 스왑 아웃 대상으로 선정된 프로세스에 대해서 현재 메모리에 올라가 있는 주소 공간의 내용을 통째로 디스크 스왑 영역에 스왑 아웃 시킨다.
3. 메모리에 있는 프로그램에 충분히 실행되고 나면, 메모리에서 내쫓고 그 자리에 스왑 아웃되었던 프로그램을 다시 올린다.
 3-1) 컴파일 타임 바인딩 방식과 로드 타임 바인딩 방식에서는 스왑 아웃된 프로세스가 다시 스왑 인 될때 원래 존재하던 메모리 위치로 다시 올라가야함.
 3-2) 실행시간 바인딩은 빈 메모리 영역 아무곳에나 프로세스를 올릴 수 있다.

 

스와핑에 소요되는 시간은 디스크의 탐색시간(seek time)이나 회전지연 시간(rotational lantency)보다는

디스크 섹터에서 실제 데이터를 읽고 쓰는 전송 시간(transfer time)이 대부분을 차지한다.

 

스와핑 예시

 

 

---

 

물리적 메모리의 할당 방식

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

운영체제 상주 영역은 낮은 주소 영역(인터럽트 벡터와 함께)을 사용하고 운영체제 커널이 이곳에 위치하게 된다.

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

 

사용자 프로세스 영역관리 방법에 대해서 살펴보도록 하자

• 연속할당
  • 각각의 프로세스를 물리적 메모리의 연속적인 공간에 올리는 방식
    • 고정분할
      • 물리적 메모리를 고정된 크기의 분할로 미리 나누어 두는 방식
    • 가변분할
      • 분할을 미리 나누어놓지 않은 채 프로그램이 실행되고 종료되는 순서에 따라 분할을 관리하는 방식
• 불연속할당
  • 하나의 프로세스를 물리적 메모리의 여러 영역에 분산해 적재하는 방식 
    • 페이징
      • 페이지로 잘라서 메모리에 페이지 단위로 적재하는 방식
    • 세그먼테이션
      • 프로그램의 주소 공간을 의미있는 단위(코드, 데이터, 스택 등)인 세그먼트로 나누어 세그먼트 단위로 적재하는 방식
    • 페이지 세그먼테이션
      • 세그먼트 하나를 다수의 페이지로 구성하는 방식

프로세스를 메모리에 올리는 방식에 따라 -> 연속, 불연속 할당
분할을 관리하는 방식에 따라 -> 고정분할, 가변분할
주소공간을 나누는 방식에 따라 -> 페이징, 세그먼테이션, 페이지드 세그먼테이션

 

---

 

연속할당 방식

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

 

고정분할 방식

물리적 메모리를 주어진 갯수만큼의 영구적인 분할(partition)로 미리 나누어두고 각 분할에 하나의 프로세스를 적재하는 방식이다.

이때 분할의 크기는 모두 동일하게 또는 서로 다르게 할수도 있다.

하지만, 두 방식 모두 하나의 분할에는 하나의 프로세스만 적재 할 수 있다.

이렇듯 고정분할 방식은 동시에 메모리에 올릴 수 있는 프로그램의 수가 고정되어 있다.

수행 가능한 프로그램의 최대 크기 또한 제한된다.(가변분할 방식에 비해 융통성이 떨어진다.)

 

고정분할 방식을 이용하면 외부조각(extrenal fragmentation)과 내부조각(internal fragmentation)이 발생할 수도 있다.

• 외부조각(외부 단편화)
  • 프로그램의 크기보다 분할의 크기가 작은 경우 해당 분할이 비엉 있는데도 불구하고 프로그램을 적재하지 못하기 때문에 발생하는 메모리 공간을 의미한다.
  • 프로그램이 배정되지 않은 빈 공간임에도 현재 상태에서 사용될 수 없는 작은 분할을 의미한다.
  • (프로그램 크기 > 분할 크기)이면 분할 크기가 작아서 적재가 불가하다
    • 분할 크기 만큼 메모리 공간이 낭비된다.
  • 외부조각의 크기보다 작은 크기의 프로그램이 도착한다면 적재가 가능하다
    • 프로그램이 배정되지 않은 빈공간이기 때문
• 내부조각(내부 단편화)
  • 프로그램의 크기보다 분할의 크기가 큰 경우 해당 분할에 프로그램을 적재하고 남는 메모리 공간을 의미한다
  • 하나의 분할 내부에서 발생하여 사용되지 않는 메모리 조각을 말한다
  • 내부조각에 수용할 수 있는 충분히 작은 크기의 프로그램이 있다 해도 공간을 활용할 수 없어 메모리가 낭비된다
  • (프로그램 크기 < 분할 크기)이면 분할 크기 - 프로그램 크기 만큼 메모리 공간 낭비

 

 

 

 

가변분할 방식

가변분할 방식은 고정분할 방식과 달리 메모리에 적재되는 프로그램의 크기에 따라 분할의 크기, 개수가 동적으로 변하는 방식이다.

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

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

 

동적메모리 할당 문제(dynamic storage allocation problem)

가변분할 방식에서 주요하게 쟁점은 물리적 메모리 내 가용 공간 중 어떤 위치에 올릴 것인지 결정하는 문제이다.

이를 동적 메모리 할당 문제라고 한다.(이때 가용 공간은 사용되지 않은 메모리 공간을 뜻한다.)

연속할당 기법에서는 새로운 프로세스를 메모리에 올리기 위해 프로세스의 주소 공간 전체를 담을 수 있는 가용 공간을 찾아야 한다.

물리적 메모리 내에서는 다양한 크기의 가용 공간들이 흩어져 있기 때문에 이를 효율적으로 관리하기 위해

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

 

동적메모리 할당 문제 해결법

• 최초적합(first fit)
  • 크기가 n 이상인 가용 공간 중 가장 먼저 찾아지는 곳에 프로세스를 할당
  • 가용 공간을 모두 탐색하는 방법이 아니라서 시간적인 측면에서 효율적
• 최적적합(best fit)
  • 크기가 n 이상인 가장 작은 가용 공간을 찾아 그곳에 새로운 프로그램을 할당
  • 모든 가용 공간 리스트를 탐색해야하기 때문에 시간적 오버헤드가 발생하고, 다수의 작은 가용 공간들이 생길 수 있다
  • 공간적인 측면에서 효율적
• 최악적합(worst fit)
  • 가용 크기가 큰 곳에 새로운 프로그램을 할당
  • 모든 가용 공간 리스트를 탐색(오버헤드 발생)
  • 상대적으로 더 큰 프로그램을 담을 수 있는 가용 공간을 빨리 소진

 

실제 시스템에서 실험한 결과에 따르면 최초적합과 최적적합 방식이 최악적합 방식에 비해 속도와 공간 이용률 측면에서 효과적이다.

 

컴팩션(compaction)

가변분할 방식에서 외부조각 문제를 해결하기위한 방법

물리적 메모리 중에서 프로세스에 의해 사용 중인 메모리 영역을 한쪽으로 몰고 가용 공간들을 다른 한쪽으로 모아서 하나의 큰 가용 공간을 만드는 방법

현재 수행 중인 프로세스의 메모리상의 위치를 상당 부분 이동시켜야 하므로 비용이 매우 많이 드는 작업

따라서 프로그램의 실행 도중에 프로세스의 주소가 동적으로 바뀔 수 있는 실행시간 바인딩 방식이 지원되는 환경에서만 수행 가능하다.

 

---

 

불연속할당 기법(noncontiguous allocation)

불연속할당 기법이란 하나의 프로세스가 물리적 메모리의 여러 위치에 분산되어 올라갈 수 있는 메모리 할당 기법

프로그램을 분할하는 기준에 따라 아래와 같이 나눌수 있다.

• 페이징
  • 페이지로 잘라서 메모리에 페이지 단위로 적재하는 방식
• 세그먼테이션
  • 프로그램의 주소 공간을 의미있는 단위(코드, 데이터, 스택 등)인 세그먼트로 나누어 세그먼트 단위로 적재하는 방식
• 페이지 세그먼테이션
  • 세그먼트 하나를 다수의 페이지로 구성하는 방식

 

 

페이징 기법(paging)

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

페이징 기법에서는 각 프로세스의 주소 공간 전체를 물리적 메모리에 한꺼번에 올릴 필요가 없고,

일부는 백킹스토어에(스왑 아웃), 일부는 물리적 메모리에 혼재 시키는 것이 가능하다.

물리적 메모리를 페이지와 동일한 크기의 프레임(frame)으로 미리 나누어 둔다.

메모리에 올리는 단위가 동일한 크기의 페이지 단위이므로,(메모리에 올리는 크기 = 페이지 크기)
메모리를 같은 크기로 미리 분할해두더라도 빈 프레임이 있으면 어떤 위치이든 사용될 수 있다.

프로세스의 주소 공간과 물리적 메모리가 모두 같은 크기의 페이지 단위로 나누어 지기 때문

외부조각 문제가 발생하지 않으며,
프로그램의 크기가 항상 페이지 크기의 배수가 된다는 보장이 없기 때문에 내부조각이 발생할 가능성은 있다.

 

따라서 페이징 기법은 앞서 연속할당에서 발생했던 동적 메모리 할당 문제가 발생하지 않는다...!!😎

 

 

하나의 프로세스라고 하더라도 페이지 단위로 물리적 메모리에 올리는 위치가 다르기 때문에 논리적 주소를 물리적 주소로 변환하는 작업이다소 복잡하다..😨

특정 프로세스의 몇 번째 페이지가 물리적 메모리의 몇번째 프레임에 들어있다는 페이지별 주소 변환 정보를 유지하고 있어야 하기때문...

따라서, 페이징 기법에서는 모든 프로세스가 각각의 주소변환을 위한 페이지 테이블을 가지며, 이 테이블은 프로세스가 가질수 있는 페이지 갯수 만큼 주소 변환 엔트리를 가져야 한다.

 

주소 변환 기법(address translation)

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

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

 

 

 

페이지 테이블의 구현

페이지 테이블은 주소 변환을 하기 위한 자료구조로, 물리적 메모리에 위치하게 된다.

운영체제는 2개의 레지스터를 사용한다.

• 페이지 테이블 기준 레지스터(page-table base register)
  • 페이지 테이블의 시작 위치
• 테이블 길이 레지스터(page-table length register)
  • 페이지 테이블의 크기

 

메모리 접근 연산은 2번의 메모리 접근이 필요하게 되는데..

주소 변환을 위해 페이지 테이블에 접근하는 것과, 변환된 주소에서 실제 데이터에 접근하는 것...!!!

즉 메모리에 한 번 접근하기 위해서는 매번 메모리에 두번 접근해야하는 오버헤드가 뒤따르게 된다.

이와 같은 문제를 해결하기 위해서(오버헤드와 메모리의 접근 속도를 향상시키기 위해)

TLB(Translation Look-aside Buffer)라고 불리는 고속의 주소 변환용 하드웨어 캐시가 사용된다.

하지만, TLB는 가격이 비싸기 때문에 모든 정보를 담을 수는 없고, 자주 참조되는 페이지에 대한 주소 변환 정보만을 담게 된다.

또한, 주소변환 정보는 프로세스별로 다 다르기 때문에 문맥교환 시 TLB 내용은(이전 프로세스의 주소변환 정보를 담고 있던) 모두 지워야 한다.

페이지 테이블과 TLB에 저장되어 있는 정보는 구조가 조금 다르다.

페이지 테이블에는 하나의 프로세스를 구성하는 모든 페이지에 대한 주소 변환 정보가 페이지 번호에 따라 순차적으로 들어있기 때문에, 페이지 번호만 주어지면 테이블의 시작 위치에서 페이지 번호만큼 떨어진 항목에 곧바로 접근하여 페이지에 대응되는 프레임 번호를 얻을 수 있다.

반면 TLB를 사용한 주소변환의 경우 프로세스의 모든 페이지에 대한 주소 변환 정보를 TLB가 갖고 있지 않기 때문에 페이지 번호와 이에 대응 하는 프레임 번호가 쌍으로 저장되어야 한다.
추가로 TLB를 통한 주소변환을 위해서는 해당 페이지에 대한 주소 변환 정보가 TLB에 있는지 확인하기 위해... TLB의 모든 항목(entry)를 다 찾아봐야 하는 오버헤드가 발생한다.... ㅠ0ㅠ
그래서 이러한 오버헤드를 줄이기 위해 병렬탐색이 가능한 연관 레지스터(associative register) 두두둥장!

 

 

메모리 접근 시간(Effective Access Time: EAT)

메모리에 접근하는 시간 = 1
연관 레지스터에 접근하는 시간 = e (1보다 충분히 작은 값)
요청된 페이지에 대한 주소 변환 정보가 연관 레지스터에 존재할 확률 = a


EAT = (1 + e)a + (1 + (1 + e))(1 - a) = 2 + e - a
             <hit>              <miss>

 

 

계층적 페이징

페이지 테이블에 사용되는 메모리 공간의 낭비를 줄이기 위해 2단계 페이징 기법(two-level paging)을 사용한다.

32비트 주소 체계를 사용하는 컴퓨터는 2^32 = 4GB의 주소 공간을 갖는 프로그램 지원 가능
페이지 크기가 2^12 = 4KB라고 하면
페이지 테이블은 4GB/4KB = 1MB개의 페이지 테이블 항목이 필요
각 페이지 항목이 4byte가 필요하다면
페이지 테이블 당 1MB * 4byte = 4MB 크기의 메모리 공간이 필요

1. 프로세스의 수가 증가함에 따라 전체 메모리의 상당 부분이 주소변환을 위한 페이지 테이블에 할애됨
2. 실제 메모리 공간이 줄어듦
3. 프로세스는 주소공간(4GB) 중 지극 히 일부분만을 사용..
4. 페이지 테이블을 위한 메모리의 사용은 심각한 공간 낭비.......

 

주소 변환을 위해 외부 페이지 테이블과 내부 페이지 테이블을 사용한다.

• 외부 페이지 테이블(outer page table)
  • 사용되지 않는 주소 공간에 대해서는 외부 페이지 테이블을 NULL로 설정
• 내부 페이지 테이블(inner page table)
  • NULL에 대응하는 내부 페이지 테이블을 생성하지 않음

 

2단계 페이징 기법을 사용하면 1단계 페이징 기법에 비해 메모리 낭비를 크게 줄일 수 있지만,

주소 변환을 위해 접근해야 하는 페이지 테이블의 수가 증가하기 때문에 시간적인 손해가 생기게 된다.

 

 

2단계 페이징 기법

논리적 주소

• 페이지 번호
  • p1: 외부 페이지 테이블의 인덱스
  • p2: 내부 페이지 테이블의 인덱스
• 페이지 오프셋
  • d: 페이지 오프셋

1. 외부 페이지 테이블로 부터 p1만큼 떨어진 위치에서 내부 페이지 테이블의 주소를 얻는다.
2. 내부 페이지 테이블로부터 p2만틈 떨어진 위치에서 요청된 페이지가 존재하는 프레임의 위치를 얻는다.
3. 해당 프레임으로부터 d만큼 떨어진 곳에서 원하는 정보에 접근한다.

 

 

그러면 32비트 논리적 주소 중 페이지 번호와 페이지 오프셋을 위해 각각 몇 비트를 할당 해야할까?!

1. 페이지 크기가 4KB이므로 12비트가 필요하다.
2. 32비트 중 최하위 12비트가 오프셋 d로 사용
3. 내부 페이지 테이블 자체를 하나의 프레임으로 보관하므로 내부 페이지 테이블도 4KB가 된다.
4. 테이블 항목의 크기가 4byte이므로 4KB/4byte = 1KB의 항목을 가지게 된다.
5. 1KB는 10비트 이므로 내부 페이지 테이블의 인덱스는 10비트가 할당 된다.
6. 외부 페이지는 남은 10비트를 할당 받는다.

p1 = 10bit, p2 = 10bit, d = 12bit

 

프로세스의 주소 공간이 커질수록 외부 페이지 테이블의 크기도 커지기 때문에 메모리 공간 낭비는 더욱 심각하게 된다.

따라서 3단계, 4단계에 이르는 다단계 페이지 테이블이 필요하게 된다.

다단계 페이지 테이블을 사용하면 사용하는 메모리 공간의 소모를 줄일 수 있지만, 그만큼 메모리에 대한 접근 횟수가 많아지기 때문에 접근 시간이 늘어나는 문제가 발생한다.... ㅠ0ㅠ

이러한 시간적인 오버헤드를 줄이기 위해서는 TLB를 사용하는 것이 매우 효과적이다.

TLB를 사용하면 다단계 페이지 테이블로 인해 공간적인 이득을 얻을 수 있고, 메모리 접근 시간도 그다지 크지 않아 시간적인 효율성도 얻을 수 있다.!!!

TLB 짱!!!!!

 

 

역페이지 테이블(inverted page table)

페이지 테이블로 인한 메모리 공간 낭비가 심한 이유는

모든 프로세스의 모든 페이지에 대해 페이지 테이블 항목을 다 구성해야 하기 때문이다..!

이러한 문제를 해결하기 위해 역페이지 테이블 기법을 사용 할 수 있다.

역페이지 테이블 기법은 물리적 메모리의 페이지 프레임 하나당 페이지 테이블에 하나씩의 항목을 두는 방식이다.

 

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

물리적 주소에 대해 페이지 테이블을 만드는 것이다.

그러면 각 프로세스마다 페이지 테이블을 두지 않고, 시스템 전체에 페이지 테이블을 하나만 둘수 있다.

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

역페이지 테이블은 물리적 주소로부터 논리적 주소를 얻기 수월한 구조!!

역페이지 테이블에 주소 변환 요청이 들어오면, 그 주소를 담은 페이지가 물리적 메모리에 존재하는지 여부를 판단하기 위해 페이지 테이블 전체를 전부 탐색해야 하는 어려움이 있다.
따라서 다소 비효율적인 측면이 있다.

하지만 일반적으로 메모리에 유지하는 대신 연관 레지스터에 보관해(TLB처럼) 테이블 전체 항목에 대한 병렬 탐색을 가능하게 하여 시간적 효율성을 얻으려 한다.

 

 

공유 페이지(Shared Page)

 

공유 페이지란

공유 코드를 담고 있는 페이지를 말한다.

공유 코드(Shared code)는
메모리 공간의 효율적인 사용을 위해 여러 프로세스에 의해 공통으로 사용될 수 있도록 작성된 코드
재진입 코드(re-entrant code), 순수 코드(pure code)라고도 불리며 읽기 전용(read-only)의 특성을 갖고 있다.

 

여러 프로세스에 의해 공유되는 페이지이므로 물리적 메모리에 하나만 적재되어 메모리를 효율적으로 사용 할 수 있다.

모든 프로세스의 논리적 주소 공간에서 동일한 위치에 존재해야 한다.

즉 그 페이지를 공유하는 모든 프로세스의 주소 공간에서 동일한 페이지 번호를 갖고 있어야 한다.

 

사유 페이지

공유 페이지와 대비되는 개념으로

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

프로세스의 주소 공간 중 어떤한 위치에 있어도 무방하다

 

 

코드1, 2, 3페이지는 3개 프로세스의 주소 공간 내에서 동일한 위치에 존재해야하며, 물리적 메모리에는 하나씩의 코드만 올라간다.

데이터1, 2, 3은 각 프로세스의 주소 공간 내의 어느 위치에 존재해도 상관 없으며 프로세스마다 독립적으로 사용한다.

 

 

메모리 보호

페이지 테이블의 각 항목에는 주소 변환 정보 뿐 아니라

메모리 보호를 위해 보호비트(protection bit), 유효-무효 비트(valid-invalid bit)를 두고 있다.

• 보호비트
  
  • 각 페이지에 대해 어떠한 접근을 허용하는지의 정보 저장
  • 읽기-쓰기/읽기 전용 등의 접근 권한 저장
• 유효-무효 비트
  • 페이지 내용이 유효한지 정보 저장
  • 유효
    • 해당 메모리 프레임에 그 페이지 존재 => 접근 허용
  • 무효
    • 프로세스가 해당 주소 사용 하지 않음 => 접근 권한 없음
    • 프로세스가 백킹스토어 존재 가능성 => 접근 권한 없음

 

---

 

세그먼테이션(segementation)

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

프로세스를 구성하는 주소공간은 일반적으로 코드(code), 데이터(data), 스택(stack) 등의 의미 있는 단위로 구성된다.

세그먼트는 이와 같이 주소 공간을 기능 단위 또는 의미 단위로 나눈것이다.

이렇듯 의미를 가질 수 있는 논리적인 단위로 나눈 것이기 때문에 크기가 균일 하지 않다..

따라서 물리적 메모리 관리에서 외부조각이 발생하고, 세그먼트를 어느 가용공간에 할당할 것인지 결정하는 문제가 발생..

가변분할 방식에서의 문제와 동일한 범주의 문제이다..

세그먼트를 가용 공간에 할당하는 방식

• 최초적합
  • 세그먼트 크기보다 크거나 같은 첫 번째 가용공간에 할당
• 최적적합
  • 세그먼트 크기보다 크거나 같은 가용 공간 중 가장 작은 공간에 할당

 

논리적 주소가 <세그먼트 번호, 오프셋>으로 나뉘어 사용된다.

• 세그먼트 번호
  • 해당 논리적 주소가 프로세스 주소 공간 내에서 몇 번째 세그먼에 속하는지에 대한 정보
• 오프셋
  • 그 세그먼트 내에서 얼마만큼 떨어져 있는지에 대한 정보

 

주소변환을 위해 세그먼트 테이블을 사용한다.

• 기준점(base)
  • 물리적 메모리에서 그 세그먼트의 시작 위치
• 한계점(limit)
  • 세그먼트의 길이

세그먼트는 길이가 균일하지 않기 때문에 위치정보와 길이정보 둘다 보관해야 한다.

페이징 기법에서는 모든 페이지의 길이가 동일 하기 때문에 페이지 테이블의 항목에 기준점이라고 할 수 있는 페이지 프레임만 위치하면 된다.

주소변환시 또한 2개의 레지스터를 사용한다.

• 세그먼트 테이블 기준레지스터(segment table base register)
  • 현재 CPU에서 실행 중인 프로세스의 세그먼트 테이블이 메모리의 어느 위치에 있는지 시작 주소값
• 세그먼트 테이블 길이 레지스터(segment table length register)
  • 프로세스의 주소 공간이 총 몇개의 세그먼트로 구성되는지(세그먼트의 갯수)

논리적 주소를 물리저구 주소로 변환하는 과정

1. 요청된 세그먼트 번호가 STBR에 저장된 값보다 작은지 확인
2. 작지 않으면 예외 발생(존재하지 않은 세그먼트에 대한 접근이기 때문)
3. 논리적 주소의 오프셋값이 세그먼트의 길이보다 작은지 확인
4. 작지 않으면 예외 발생

 

 

• 보호비트
  • 각 세그먼트에 대해 읽기/쓰기/실행 권한 표시
• 유효비트
  • 주소 변환 정보가 유효한지 표시
  • 세그먼트가 현재 물리적 메모리에 적재되어 있는지

 

앞서 말한것 처럼 의미 단위로 나누었기 때문에 세그먼트의 길이는 균일하지 않다.

 

공유 세그먼트(Shared Segment)

세그먼트를 공유하는 모든 프로세스의 주소 공간에서 동일한 논리적 주소에 위치해 있어야 한다.

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

 

---

 

페이지드 세그먼테이션(paged segmentation)

페이지드 세그먼테이션은 페이징 기법과 세그먼테이션 기법의 장점만을 가지고 있다.

세그먼테이션 기법과 마찬가지로 프로그램을 의미 단위의 세그먼트로 나눈다.

단, 세그먼트의 길이는 동일한 크기 페이지들의 집합으로 구성된다.

그리고 메모리에 적재하는 단위는 페이지 단위로 한다.

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

 

주소 변환을 위해 외부세그먼트 테이블, 내부 페이지 테이블 이렇게 구성된다.

하나의 세그먼트가 여러 개의 페이지로 구성되므로 각 세그먼트마다 페이지 테이블을 가진다.(2단계 페이지 테이블과 유사)

 

<세그먼트 번호, 오프셋>으로 구성된 논리적 주소를 물리적 구조로 변환하는 과정

1. 논리적 주소의 상위 비트인 세그먼트 번호를 통해 세그먼트 테이블의 해당 항목에 접근
2. 세그먼트 길이값과, 논리적 주소 중 하위 비트인 오프셋 값 비교(세그먼트 길이를 넘어서는 메모리 접근 시도인지 확인)
3. 오프셋이 더 크면 트랩 발생
4. 오프셋이 작으면 오프셋 값을 다시 상위.하위 비트로 나누어
상위 비트는 그 세그먼트 내에서 페이지 번호로 사용하고
하위 비트는 페이지 내에서의 변위로 사용
5.페이지 번호만큼 떨어진 페이지 테이블 항목으로부터 물리적 메모리의 페이지 프레임 위치를 얻는다.