메모리 관리(2022.04.09 수정)

왜 메모리 관리를 해야할까?

• 일련의 프로세스가 CPU를 공유하면서 CPU 스케줄링을 통해 CPU 이용률과 컴퓨터 응답속도를 향상시킴
• 하지만 결국 성능 향상을 "실현" 시키기 위해서는 많은 프로세스를 메모리에 올릴 수 있어야하고, 유지할 수 있어야함
  • 즉, 메모리를 "공유"해야함
• 따라서 많은 프로세스를 메모리에 올리기 위해서는 메모리 관리를 "효율"적으로 해야할 필요가 있음

 

CPU는 어떻게 작동할까?

• Program Counter 값에 따라 메모리로부터 다음 수행할 명령어를 가져옴
• 명령어는 특정 메모리 주소에서 loading 또는 storing 함
  • 메모리로부터 명령어를 가져오고, 명령어를 해독하여 메모리에서 피연산자를 가져와 피연산자에 대해 명령어를 실행한 후 계산 결과를 메모리에 다시 저장함

 

캐시가 생긴 이유

• CPU가 직접 접근할 수 있는 유일한 저장장치는 메인 메모리와 레지스터 뿐
• 레지스터들은 CPU 접근이 빠름
• 메인 메모리는 "메모리 버스"를 통해 전송되므로 CPU 접근에 많은 시간이 걸림
  • CPU가 수행되는데 필요한 데이터가 없어서 명령어를 수행하지 못하고 지연(stall)되는 현상 발생
• 해결방법으로 CPU와 메인 메모리 사이에 "캐시"를 추가
  • 캐시는 CPU 안에 있으면서, CPU와 메인 메모리 사이에 빠른 속도의 메모리
  • CPU에 구축된 캐시를 관리하여 하드웨어는 OS의 도움 없이 메모리 접근 속도를 향상 시킴

 

CPU와 메모리 간의 접근은 운영체제가 왜 관여하지 않을까?

• 성능 이슈로 인하여
• 따라서 하드웨어가 지원해야줘야함

 

하드웨어가 어떤 방법으로 지원해야할까?

• 각각의 프로세스가 독립된 메모리 공간을 가지도록 보장
  • 왜?
  • 프로세스끼리 서로 보호하고 병행 실행을 위해 여러 프로세스가 메모리에 적재되야함
• 독립된 메모리 공간을 가지기 위해 특정 프로세스만 접근할 수 있는 legal address를 설정
  • base register를 이용하여 가장 작은 legal한 물리 메모리 주소 값 저장
  • limit register를 이용하여 메모리 공간의 크기를 정함
  • base, limit register는 OS에 의해서만 load됨
  • 왜?
  • 해당 레지스터들은 특권 명령에 의해 적재되고, 특권 명령은 커널 모드에서만 수행되고, OS에서만 커널 모드가 수행되기 때문
  • OS만 레지스터들의 값을 변경할 수 있도록하여 user program이 레지스터의 내용을 변경하는 것을 막음
• user mode에서 수행되는 프로그램이 운영체제의 메모리 공간이나 다른 사용자 프로그램의 메모리 공간에 접근하려고 시도하면 OS는 "트랩"을 발생시킴

 

logical address vs physical address

프로그램이 실행되면 독자적인 주소 공간이 형성된다.

이렇게 독자적인 주소공간을  논리적인 주소라고 하는데, 실제 프로그램이 메모리에 올라가서 실행이 되면 물리적 주소가 생긴다

• 논리 주소 -> 물리 주소로 변환시켜주는 것은 MMU라는 것이 있다(MMU는 아래에서 언급)

 

즉, CPU가 생성하는 주소를 "논리 주소", 메모리가 취급하게 되는 주소를 "물리 주소"라 한다

 

컴파일 또는 load 시에 주소를 binding하면 논리 주소와 물리 주소가 같다

• 왜 그럴까?
  • 컴파일 시간에 바인딩이 완료되면 cpu가 생성한 논리주소가 바인딩되므로 논리 주소와 물리 주소가 같아짐
  • load 시간에 바인딩이 완료되면 해당 코드가 absolute code가 아닌 relocatable code가 되는 것 뿐이니까 논리 주소와 물리 주소가 같음
• 논리적 주소(가상 주소)
  • 프로세스마다 독립적으로 할당
  • 0번지부터 시작
  • CPU가 보는 주소
• 물리적 주소
  • 실제 물리적인 메모리에 올라가는 위치
  • 메모리 주소 레지스터(Memory Address Register)에 저장되는 주소
• symbolic 주소
  • 우리는 일반적으로 코드를 작성할 때 변수 값을 몇 번지에 저장하라가 아닌, 변수 이름을 주고 값을 저장한다
  • 또한, 함수를 사용할 떄도 몇 번지에 점프해라가 아닌 함수 이름을 가지고 점프하라한다

 

주소 변환(mapping), 주소 바인딩(binding)

프로그램이 논리적 주소만 있으면 실행될 수 없다.

실행이 되려면 메모리에 올라가야하고, 이때 메모리에 어디에 위치하는지 알려주는 "물리적 주소"를 얻게 된다.

• 주소 바인딩
  
  • 해당 프로그램의 "물리적 주소"를 결정하는 것
  • 논리적 주소를 물리적 메모리 주소로 연결시켜주는 작업
• 주소 변환
  • CPU가 보는 주소는 논리적 주소로 프로그램이 메모리의 어느 위치에 매핑되는지 알기 위해서는 논리적 주소를 물리적 주소로 변환시켜주는 작업이 필요하다

 

Q.
CPU가 보는 주소는 논리적 주소일까, 물리적 주소일까?

A.
아래의 사진을 보면 컴파일 한 뒤 논리적 주소가 만들어진다.
CPU가 실행파일을 실행 시작하면
0 : ADD 20, 30 => 메모리 20번지 내용, 30번지 내용을 읽어 들여서 더하는 연산을 하게 된다.
이때, 20, 30번지는 논리적 주소이다. 
즉, 실행이 돼서 메모리에 올라가더라도 이 실행파일 안에 있는 주소들은 바뀌지 않는다.

그래서 CPU가 매번 메모리 몇 번지에 있는 내용을 가져오기 위해 요청하면
논리적 주소를 주소 변환을 통해 물리적 주소를 찾은 다음에 그 내용을 읽어서 CPU에게 전달한다.

따라서 CPU는 논리적 주소를 본다!

 

주소 바인딩 방식

주소 바인딩 방식은 물리적 메모리 주소가 "결정"되는 시기에 따라 나뉜다

• Complie time binding(컴파일 시점)
  • 컴파일할 때 물리적 메모리 주소가 결정(프로세스가 메모리 내에 들어갈 위치를 안다는 것)
    • 즉, 컴파일하는 시점에 해당 프로그램이 메모리의 몇 번지에 위치할 것인지 결정
  • 절대 코드
  • 메모리의 위치를 바꾸고 싶으면 컴파일 다시 해야 함
• Load time binding(적재 시간 시점)
  • 프로세스가 메모리 내 어디로 올라오게 될지를 컴파일 시점에 알지 못할 경우 
  • 프로그램의 실행이 시작될 때 메모리 주소 결정
  • loader의 책임하에 물리적 메모리 주소가 부여되며, 프로그램이 종료될 때까지 물리적 메모리 상의 위치가 고정
  • 컴파일러가 "재배치 가능 코드"를 생성한 경우에 가능함
    • 프로세스가 메모리 내 어디로 올라오게 될지를 컴파일 시점에 알지 못하는 경우 컴파일러는 이진 코드를 재배치 가능 코드로 만들어야함
  • 프로그램이 시작돼서 메모리에 올라갈 때, 주소가 결정됨
  • 항상 특정 위치에 들어가지 않고, 비어있는 위치에 들어가게 된다
• Execution time binding = Runtime binding(실행 시간 시점)
  • 적재 시간처럼 실행 시에 주소가 결정
  • 실행 중에 주소가 바뀔 수 있음
    • 따라서 CPU가 주소를 참조할 때마다 물리적 메모리의 어느 위치에 존재하는지 주소 매핑 테이블 필요
  • 실행시간 바인딩 방식이 가능하기 위해서는 base register, limit register를 포함한 MMU라는 하드웨어적인 지원 필요
• 차이점
  • 컴파일, 적재 시점은 주소가 결정 나면 더 이상 바뀌지 않지만 실행 시간 시점은 바뀔 수 있다
    그래서 CPU가 메모리 주소를 요청할 때마다 주소 매핑 테이블을 통해 체크해야 한다

 

MMU(Memory Management Unit)

• MMU
  • 논리적 주소 -> 물리적 주소로 매핑해주는 "주소 변환"을 해주는 하드웨어
  • base register + limit register를 통해 매핑을 수행
  • 프로그램의 주소 공간이 물리적 메모리에 통째로 적재한다는 가정 필요
• base register(relocation register)
  • 프로세스의 물리적 메모리 "시작 주소"를 가짐
  • 주소변환을 할 때 논리 주소에 시작 위치를 더해 물리적인 주소를 얻게 됨
  • 그림에서의 14000은 물리적 메모리의 시작 위치, 346은 시작 위치로부터 얼마나 떨어져 있는지 나타내는 offset
  • user program은 실제적인 물리 주소에 접근하지 않음!
    • 논리 주소를 통해 base register가 물리 주소를 binding해주기 때문
• limit register
  • limit register는 현재 p1 프로세스의 크기(3000)를 저장해놓는다

• 주소 변환 과정
  • limit register
    • 처음에 어떤 요청이 4000 번지에 있는 내용을 달라 요청을 하게 되면
      이는 프로세스의 크기를 넘어서는 요청으로, 프로세스 바깥쪽에 접근하게 된다
    • limit register에 벗어난 요청일 시 , trap이 걸리게 되고, cpu 제어권이 운영체제에 넘어가고
      운영체제는 trap이 왜 걸리는지 확인한 다음 응징을 하게 된다
  • relocation register
    • 그래서 요청이 limit 보다 작게 되면 relocation register에 있는 값을 더하여 주소변환을 한 다음
      물리적인 메모리의 어딘가의 내용을 읽은 다음에 CPU에 전달한다.

 

메모리 관리와 관련된 용어

 

Dynamic Loading(동적 적재)

• 다중 프로그래밍 환경에서 메모리 사용의 효율성을 높이기 위해 사용
• loading을 실행 시점까지 지연시킴
• 프로그램이 시작될 때 프로그램을 통째로 메모리에 올려놓는 것이 아닌, 실행에 필요한 부분이 실제로 호출될 때마다 메모리에 올리는 방법
  • 실제로 호출되기 전까지는 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에서 대기
  • main 프로그램이 실행 -> 다른 루틴 호출 시 해당 루틴이 메모리에 적재됐는지 조사 -> 없으면 relocatable linking loader를 불러 해당 루틴을 메모리에 가져옴 -> CPU 제어가 호출한 루틴으로 보내짐
• OS가 지원을 하는 게 아닌 프로그래머가 다이나믹 로딩을 직접 하도록 라이브러리를 사용하여 만듦

 

Dynamic Linking(동적 연결)

• 정의
  • 컴파일을 통해 생성된 파일과 라이브러리 파일 사이의 "연결"을 프로그램 실행 시점까지 지연시킴
    • 따라서 실행 가능한 image(파일+라이브러리)의 크기를 줄일 수 있음(장점1) 
  • 즉, 라이브러리가 실행 시점에 연결된다 
  • 라이브러리가 실행 시점에 연결, 실행 파일에 라이브러리 코드 포함 X
  • 라이브러리를 호출하기 위해 위치를 찾기 위한 "스텁"이라는 작은 코드가 있음
  • 메모리에 이미 라이브러리가 존재하면 메모리 위치에서 직접 참조,
    없을 경우 디스크에서 동적 라이브러리 파일을 찾아 메모리에 적재
  • 다수의 프로그램이 공통으로 사용하는 라이브러리를 메모리에 한 번만 적재하므로
    효율성 매우 높임 ---> 이 방법은 OS의 지원이 필요(동적 적재는 필요 없음)
    • 이러한 라이브러리를 여러 프로세스 간에 "공유"함으로써 메인 메모리에 해당 라이브러리 인스턴스가 하나만 있을 수 있음(장점2)
  • 라이브러리가 갱신될 경우, 동적 연결을 이용하여 새로운 라이브러리를 linking하면 됨

• shared library
  • 동적 연결을 해주는 라이브러리를 shared library라고 한다.
• link
  • 여러 군데 존재하던 컴파일된 파일들을 묶어서 하나의 실행파일을 생성하는 과정
• 정적 연결
  • 프로그래머가 작성한 코드와 라이브러리 코드가 모두 합쳐져 실행파일 생성
    • 실행파일의 크기 커짐. 동일한 라이브러리를 각 프로세스가 개별적으로 메모리에 
      적재하게 되므로 메모리가 매우 낭비

 

Overlays(중첩)

• 다이나믹 로딩과 똑같이 "필요한 부분만 메모리에 올린다"

 

Q.
동적 적재와 Overlays 차이?

A.
컴퓨터 초기에 메모리가 워낙 작아서 하나의 프로그램을 메모리에 올리는 것조차 힘들었다.
그래서 큰 프로그램을 여러 개로 쪼개서 부분 부분 올리는 것이다.

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

이 부분에서 Overlays와 다르다.

동적 적재는 메모리에 더 많은 프로세스를 동시에 올려놓고 실행하기 위한 것,
Overlays는 "단일 프로세스"만을 메모리에 올려놓는 환경에서 메모리 용량보다 큰 프로세스를 실행하기
위한 어쩔 수 없는 선택

 

CPU 스케줄러가 다음으로 수행할 프로세스를 선택할 때, dispatcher는 문맥 교환의 일환으로 재배치 레지스터와 상한 레지스터에 정확한 값을 적재함 

 

물리적 메모리 할당 방식

• 메모리는 일반적으로 운영체제를 위한 부분, 사용자 프로세스를 위한 부분, 총 두 개의 부분으로 나뉘어있음.

"인터럽트 벡터"의 위치와 같은 요소에 따라 운영체제 메모리 주소의 위치가 달라짐

대부분 운영체제는 운영체제를 높은 메모리에 배치한다!(Linux, Windows)

따라서 운영체제는 높은 메모리에 있다고 생각

-> 커널에는 인터럽트 벡터가 있다

 

낮은 메모리 영역에는 사용자 프로그램들이 있다

사용자 프로세스의 영역 관리 방법은 메모리에 올리는 방식으로 구분한다

연속 할당 - 고정 분할, 가변 분할

불연속 할당 - 페이징, 세그멘테이션, 페이지드 세그멘테이션

 

 

 

연속 할당

• 프로세스의 물리 주소 공간이 "연속적"

특징

• 물리적 메모리의 연속적인 공간에 올리는 방식
• 프로그램이 메모리에 올라갈 때 통째로 올라가는 것
• 고정 분할 방식, 가변 분할 방식으로 나뉨

고정 분할 방식

• 메모리 영역을 "미리" 파티션으로 나눔
• 파티션 크기를 균일, 불균일하게 나눌 수 있다
• 하나의 파티션에는 하나의 프로그램만 적재 가능함
• 수행 가능한 프로그램의 최대 크기가 제한됨
  • 이미 파티션을 나눴기 때문에 제일 큰 파티션보다 큰 프로그램은 적재할 수 없음
• 낭비되는 메모리 조각
  • 내부 조각
    • 분할 3의 크기가 프로그램 B보다 크다. 그래서 그 안에 남은 메모리 공간이 있다
      프로그램 B에게 할당됐지만 사용은 안 되는 공간을 "내부 조각"이라고 한다
      따라서 내부 조각보다 작은 크기의 프로그램이 있다 해도 해당 조각에 다른 프로그램이 적재될 수 없다
      1 파티션 = 1 프로세스 이기 때문!!
  • 외부 조각
    • 올리려는 프로그램보다 메모리 조각 크기가 더 작다 그래서 사용을 하지 못한다
      프로그램이 들어갈 수 있는 공간임에도 불구하고 해당 조각 크기가 작아서 들어갈 수 없다
      이런 공간을 외부 조각이라고 한다
    • 내부 조각과 다르게 해당 조각보다 크기가 작은 프로그램을 적재할 수 있다

 

가변 분할 방식

• 실행될 때마다 메모리에 차곡차곡 올려놓는 방식이다.
• 프로그램 B가 끝나면 B가 있던 공간이 비어있게 된다.
  프로그램 D는 B가 있던 곳보다 크기 때문에 B가 있던 공간을 사용하지 못한다. -> 외부 조각
  가변 분할 방식이라도 프로그램 크기가 균일하지 않기 때문에 종료, 생성할 때 외부 조각이 생길 수밖에 없다.
  당연히 "내부 조각"은 생기지 않게 된다.
• hole
  
  • 위처럼 비어있는 가용 공간들을 hole이라 한다.
  • OS는 할당 공간과 가용 공간(hole)을 따로따로 관리한다. 
    종료되면 할당됐던 공간을 hole에 다시 넣고,
    새로운 프로그램이 실행되면 hole에서 적당한 위치에 집어넣는다.
  • Dynamic Storage-Allocation Problem
    • 프로그램이 실행될 때 여러 hole 중 어느 hole에 새로운 프로그램을 넣을 것인가?
      라는 결정을 하는 것
    • First-fit
      • hole 중에서 최초로 발견된 hole에 집어넣는다
    • Best-fit
      • 모든 hole을 탐색한 뒤, 프로그램 크기와 가장 잘 맞는 곳에 집어넣는다
      • hole들이 크기 순으로 정렬돼있지 않기 때문에 모두 탐색해야 하므로 
        시간적 오버헤드 발생, 그러나 공간적 측면에서 효율적
    • Worst-fit
      • 가장 큰 hole에다가 할당
      • 전체 hole 탐색해야 함
    • Compaction
      • 외부 단편화 문제를 해결하는 방법 
      • hole을 전체 탐색하지 않고, hole들을 묶는다
        즉, 사용 중인 메모리 공간을 한 군데로 밀어서 hole을 한 공간으로 만든다
      • 수행 중인 프로세스의 물리적 메모리 위치를 옮겨야 하기 때문에 
        실행시간 바인딩 방식이 지원되는 환경에서만 수행 가능하다
        • 재배치가 적재 시에 정적으로 행해지면 압축될 수 없음
      • 그러나 매우 복잡하고 비용이 많이 드는 방법
    • 외부 단편화를 해결할 수 있는 다른 방법은 "페이징"이 있음
  • first fit과 best fit은 외부 단편화(external fragmentation)으로 인한 메모리 낭비가 있음

 

불연속 할당

불연속 할당은 실제 시스템에서 사용하고 있는 방법들이다

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

 

연속 할당의 단점인 외부 단편화와 compaction의 필요성을 보완한다

 

하나의 프로그램을 분할하는 "기준"에 따라 페이징 기법과 세그멘테이션 기법으로 나뉜다

 

페이징

• 프로그램을 구성하는 주소 공간을 같은 크기의 "페이지"로 자른 다음에, 
  페이지 단위로 물리적인 메모리에 올려놓거나, backing store에 내려놓거나 하는 방법
• 물리적인 메모리에 그 사용자 프로그램이 들어갈 수 있게 똑같은 크기(페이지 크기)로 잘라 놓는다.
  • 이것을 페이지 "프레임"이라고 한다
  • 즉, 물리 메모리는 "프레임"이라는 블록으로, 논리 메모리는 "페이지"라는 블록으로 나눔
• 물리적 메모리를 페이지 크기만큼 자르기 때문에 외부 조각은 발생하지 않음
  • 외부 조각이 발생하지 않아 동적 메모리 할당 문제가 발생하지 않음 
  • 페이지 크기의 배수가 되는 것이 아니기 때문에 내부 조각 발생 가능
    • 질문 : 결국 이건 원하는 모양이 아니기 때문에 외부 단편화라고 말할 수 없는 것인가?
      내부 단편화는 4byte에 char로 1byte를 할당하면 나머지 3byte가 남기 때문에 이를 내부 단편화라고 할텐데
      • 프레임의 크기는 정확하게 짤리는데, 그 안에 사용하는 프로세스 메모리가 채우지 않을수도 있으므로 내부단편화가 있다고 한다
  • 왜 외부 단편화가 발생하지 않는지 헷갈렸지만 다시 정리해보자
    
    • 외부 단편화는 공간이 있긴한데 원하는 모양이 아님
    • 프레임 크기가 페이지 크기와 같으므로 원하는 모양을 무조건 충족할 수 있기 때문에 외부 단편화 X
• 프로그램의 전체를 메모리에 올릴 필요 없고, 일부는 backing store, 일부는 물리적 메모리에 올려놓기 가능
• 잘린 각각의 페이지가 물리적 메모리의 어디에 올려져 있는지 확인해야 함
  • 주소 변환이 복잡하다 논리 -> 물리로 가는 작업이 페이지 단위로 이뤄져야 한다
  • 특정 프로세스의 몇 번째 페이지가 물리적 메모리의 몇 번째 프레임에 들어갔는지 알아야 함
  • 주소 변환을 위해 페이지 테이블을 가지며, 테이블은 프로세스가 가질 수 있는 페이지의 개수만큼 주소변환 엔트리를 가지고 있게 된다.

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

• 페이지 번호 = 페이지 테이블의 인덱스
• 페이지 테이블은 페이지의 물리적 메모리 상의 기준 주소(프레임의 시작 주소)가 저장되있음
  • offset(d)는 참조되는 프레임 안에서의 "위치"
• 특정 프로세스의 p번째 페이지가 물리적 메모리에서의 시작 위치를 알고 싶다면 해당 프로세스의 페이지 테이블에서 p번째 인덱스 값을 찾으면 된다.
• 오프셋은(d) 하나의 페이지 내에서 변위를 알려준다
  • 즉, 기존 주소 값에 오프셋을 더함으로써 요청된 논리적 주소에 대응하는 물리적 주소를 얻을 수 있다.
•  페이지 테이블에서 f를 찾았는데 해당 f는 페이지 프레임 번호이다

 

페이징의 특징

메모리에 대한 프로그래머의 인식과 실제 내용이 서로 "다름"

• 프로그래머 입장
  • 메모리가 하나의 연속적인 공간이고, 메모리에는 이 프로그램만 있다고 생각
• 실제
  • 프로그램은 여러 곳에 프레임 단위로 분산되어 있고, 많은 다른 프로그램이 올라와있음
• 이 차이를 주소 변환 하드웨어에 의해 없앤다
  • 해당 과정은 프로그래머에게 보이지 않고 운영체제에 의해 조정됨

 

페이지 테이블의 구현

페이지 테이블은 페이지 기법에서 "주소 변환"을 하기 위한 자료구조

 

페이지 테이블은 "프로세스마다" 가지고 있다

• 프로세스마다 논리적인 주소 체계가 다르고, 페이지 테이블에 따른 TLB도 프로세스마다 다른 정보가 됨
  다른 프로세스로 CPU가 넘어가면 페이지 테이블의 주소 변환 정보도 달라진다
  따라서, 콘텍스트 스위칭이 발생하면 TLB에 있는 정보들은 flush를 수행하며 비워지게 된다

 

Q.
페이지 테이블은 어디에 있을까?

A.
기본적인 MMU 기법에서는 레지스터 두 개가 주소 변환을 했다
페이지 테이블의 용량은 매우 크기 때문에 레지스터에 넣을 수 없다
(페이지 테이블에 레지스터를 사용하는 것은 페이지 테이블이 작은 경우)
또한, 메모리 접근을 위한 주소 변환인데 테이블을 하드 디스크에 넣을 수도 없다
결국 들어갈만한 곳은 캐시 메모리인데, 캐시에 들어가기에 용량이 너무 크다

결국 메인 메모리에 집어넣게 된다

 

페이지 테이블에 접근하기 위해서는 OS는 2개의 레지스터를 사용함

• 페이지 테이블에 대한 "포인터"는 PCB에 다른 레지스터 값과 함께 저장됨
• 페이지 테이블 기준 레지스터(PTBR)
  • 메인 메모리에 저장되어있는 페이지 테이블을 가리킴
  • 다른 페이지 테이블을 사용하려면 해당 레지스터만을 변화시키면 됨
    • 문맥 교환 시간을 줄일 수 있음
• 페이지 테이블 길이 레지스터(PTLR)
  • 테이블 크기를 보관
• 앞에서는 레지스터 두 개가 주소변환을 했지만, 
  페이징 기법에서는 주소 변환을 "위한" 페이지 테이블에 접근하기 위해 레지스터를 사용한다.
• PTBR을 사용하면 생기는 단점
  • 메인 메모리에 페이지 테이블을 저장하면 "문맥 교환" 속도가 빨리지지만, 메모리 액세스 시간이 느려질 수 있음
  • 왜 그럴까?
  • 메모리에 접근하기 위해서는 주소변환이 필요하다 -> 주소변환을 하기 위해선 페이지 테이블 접근해야 함
    -> 페이지 테이블은 메모리에 존재 -> 결국 메모리에 접근하기 위해서 총 2번의 메모리 접근이 필요
  • 페이지 테이블을 통한 주소 변환 + 주소변환이 되어서 실제 데이터를 메모리에서 접근하기 위해
• 따라서 속도 향상을 위해 "associative register" 또는 translation look-aside buffer(TLB)을 사용한다.

 

페이징 기법을 빠르게 사용할 수 있는 하드웨어적 지원

 

TLB(Translation Look-Aside Buffer)

• 메인 메모리 윗단에 "캐시 메모리"가 있다
• 메인 메모리에서 빈번히 사용되는 데이터를 캐시 메모리에 저장해서 CPU로부터 더 빨리 데이터를 준다.

• 페이지 테이블과 TLB에 저장되어 있는 정보는 구조가 다르다.
  • 왜 다를까?
  • 페이지 테이블에는 인덱스(페이지 번호)가 "순차적"으로 들어있어서 테이블의 인덱스가 해당 페이지의 번호이므로 번호만큼(p) 떨어진 인덱스의 값이 프레임 번호이다
  • TLB는 프로세스의 모든 페이지 정보를 가지고 있지 않다. 즉, 순차적으로 들어있지 않게 된다
    • 페이지 번호와 이에 대응하는 프레임 번호가 "페어"를 이루며 저장되어있다
  • TLB를 통한 주소 변환을 하기 위해선 TLB에 해당 페이지에 대한 주소 변환 정보가 있는지 확인해야 한다.
  • 당연히 TLB는 모든 페이지를 가지고 있지 않기 때문에 완전 탐색을 해야 해서 오버헤드가 발생할 수 있다.
    • 왜 완전 탐색을 해야할까?
    • 나는 처음에 key-value 쌍으로 저장되어있어서 key가 존재하는지 안하는지 확인하면 되지 왜 브루트 포스를 해야할까라는 생각을 해서 스터디에 질문을 함
    • TLB는 "자료구조"가 아닌 "하드웨어"임. 따라서 우리는 하드웨어 내부에서 해당 logical address가 저장되어있는지 찾아봐야하기 때문에 완전 탐색을 해야한다고 함(일반적으로 생각하는 Map 구조가 아니다!!)
  • 그래서 병렬 탐색이 가능한 associative register를 사용한다.
    • 병렬 탐색이란 모든 항목을 동시에 탐색할 수 있는 기능을 말한다.
• TLB는 위에서 말한 것처럼 페이지 테이블에서 빈번히 참조되는 일부 엔트리를 캐싱하고 있다.
• 메인 메모리보다 접근 속도가 빠른 하드웨어로 구성되어있다.
• CPU 각 논리적 주소를 주면 메모리 상에 있는 페이지 테이블을 접근하기 전에 먼저 TLB을 검색한다.
  TLB에 해당 페이지 번호가 있다면 프레임 번호를 얻고, 없다면 페이지 테이블에 접근하여 주소변환을 수행한다.
• TLB에 있다면 이때는 메모리 접근을 1번만 하면 된다.

ASID(address-space idntifiers)

• 어떤 TLB는 ASID를 저장하기도 함
  • ASID란 TLB 항목이 어느 프로세스에 속한 것인지를 알려주면서, 프로세스의 정보를 보호하기 위해 사용
• TLB에서 주소 mapping을 할 때, 현재 수행 중인 프로세스의 ASID와 TLB 항목에 있는 ASID와 같은지 검사
• 맞지 않으면 TLB-miss 처리
• ASID가 있다면 한 TLB 안에 여러 프로세서의 정보를 동시에 보관할 수 있음
• ASID가 없다면 새로운 페이지 테이블이 선택될 때마다(새 프로세스가 실행할 경우), TLB를 전부 플러시해줘야함
  • 그렇지 않으면 이전 프로세스가 사용하던 페이지 번호를 변환에 사용할 수 있어서 에러 발생할 수 있음

 

페이징 환경에서의 메모리 보호

• 앞서 페이지 테이블에는 해당 페이지가 물리적 메모리의 어느 프레임에 위치하는지 매핑되어있다고 했다
• 하지만 그뿐만이 아니라 "메모리 보호"를 위한 "유효-무효 비트" 또는 읽기, 쓰기, 읽기 전용 비트를 두고 있다
• 메모리에 대한 모든 접근은 "페이지 테이블"을 거치므로 protection을 할 수 있음

 

유효-무효 비트

 

 

그림을 보면 6, 7번 idx는 사용하지 않고 있는 페이지다. 그러나 왜 페이지 테이블에 존재하는 것일까?

• 프로그램의 주소 공간에서 상위 부분에는 코드 데이터를 구성하는 페이지가 있고, 
  아래쪽은 스택을 구성하는 페이지가 있고, 중간에는 사용하지 않는 주소 영역이 매우 많이 존재한다
• 이 영역을 비우고 페이지 테이블을 생성하게 된다면
  위에서부터 index를 통해 접근하지만, 중간이 비워진다면 순서가 앞으로 밀리게 된다
  • 페이지 테이블이라는 자료구조 특성을 무시하게 된다
• 따라서 사용하지 않은 페이지에 대해서는 생성하지 않는 것이 아니라 invalild로 기록한다.
• 또한, 0으로 표시되어있는데 이게 페이지 프레임을 말하는 것인지 아무 정보가 없는 건지 모르기 때문에
  invaild로 표시함으로써 사용하지 않는 것이라 알 수 있다!!
  • invalid bit
  • 프로세스가 그 주소 부분을 사용하지 않는 경우
  • 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우

 

접근 권한 bit

• 해당 bit은 page대한 접근 권한을 제한한다.(read/write/read-only)
• read에 관해 write를 시도하면 운영체제가 하드웨어로 "트랩" 발생시킴

 

페이지 테이블 길이 레지스터(page table length register, PTLR) 사용

• 프로세스가 제시한 주소가 유효한 범위 내에 있는지 확인하기 위해 모든 논리 주소 값이 PTLR값과 비교
• 오류 발생 시 "트랩" 발생

 

Shared Pages Example(페이징의 장점)

 

프로그램을 구성하는 페이지들 중에는 다른 프로세스들하고 공유할 수 있는 페이지가 있다.

공유 페이지는 "공유 코드"를 담고 있는 "페이지"

libc 1, 2, 3, 4는 세 개의 프로세스가 똑같은 걸 사용하고 있다.

해당 페이지를 shared page, shared code, 재진입 가능 코드라고 부른다.

• 각각을 물리적 메모리에 올리는 게 아니라 이러한 share가 가능한 shared code에 대해서
  한 카피만 물리적 메모리에 올리게 된다.
  • 메모리 공간 매우 효율적으로 사용할 수 있음!
• 스레드에서의 주소 공간 공유, 프로세스 간의 상호 통신 방법 중 메모리 공유 방법과 비슷
  • 어떤 운영체제는 메모리 공유를 페이지 공유를 통해 구현하기도 함
• 조건
  • read-only로 해야 한다
  • 동일한 논리적 주소 공간에 위치해야 한다
    • 그림을 보면 같은 index에 위치하는 것을 알 수 있다.
    • P2에는 libc2, libc1, libc4, libc3 이렇게 위치하면 안 된다.
  • reentrant code(재진입 코드)일 경우
    • 자체 수정할 수 없는 코드로서 실행 중에는 절대 변경되지 않는 코드
    • 따라서 두 개 이상의 프로세스가 동일한 코드에 "동시에" 실행할 수 있음

 

페이지 테이블의 구조

 

계층적 페이징(Hierarchical Paging)

 

 

Inverted Page Table

• page table은 해당 프로세스의 모든 page에 대해 entry가 존재
  • 즉, page가 메모리에 있든 없든 일단 index는 존재하게 된다
• 또한, page table은 프로세스마다 있음
• 따라서 공간 오버헤드가 매우 큼
• 해당 단점을 보완하고자 "Inverted Page Table"이 나왔다.

특징

• page table은 process마다 존재했지만 IPT는 시스템 안에 딱 1개만 존재한다.
  • IPT에서는 메모리 프레임마다 한 항목씩을 할당 
  • 그렇다면 page table과 다르게 process-id도 들어가야 한다
  • 논리적 주소라는 것은 프로그램마다 별도로 있는 것이므로 해당 페이지가 누구의 p번째 페이지인지 알기 위해서 process-id가 필요하다
• page frame 하나당 page table에 하나의 entry를 둔다.
  • 물리적 메모리 페이지 프레임 개수만큼 존재
• 각 page table에는 물리젝 메모리의 page frame이 담겨 있다.
  • process-id, prcess의 logical address를 가지고 있다.
• 앞에서 본 page table처럼 페이지 번호를 보고 위에서부터 그 페이지 번호만큼 떨어진 것을 찾아서 주소변환을 하지 못함 
  • 왜 하지 못할까?
  • 앞서 본 page table은 논리 페이지마다 항목을 저장하지만 IPT는 메모리 프레임에 대응되는 항목만 테이블에 저장
  • 그리고 IPT는 물리 주소에 따라 "정렬"되어 있고, 탐색은 "가상 주소"를 기준으로 하기 때문에 테이블 전체를 탐색해야함
  • 따라서 논리 주소에 해당하는 p가 물리적 메모리에 어디에 있는지 찾을 때는 모든 엔트리를 다 뒤져야 한다.
• 테이블 전체를 탐색해야 한다 
  • 공간 오버헤드를 줄였지만, 시간적 오버헤드를 얻게 된다
  • associative register 사용
• 테이블 전체를 탐색하는 것을 해결하기 위해 해시 테이블을 사용할 수 있음
  • 결국 메모리 접근마다 해시 테이블을 참조해야하므로 메모리 참조 횟수가 증가됨
  • 해시 테이블에 한 번 + 페이지 테이블에 한 번(TLB hit하면 한 번으로 줄어들 수 있음)

IPT의 문제 중 공유 메모리

• 이전 paging은 프로세스마다 고유한 페이지 테이블이 존재
• 여러 가상 주소를 동일한 물리 주소로 매핑할 수 있음
• IPT는 이 방법을 사용할 수 없음
• 왜?
• 물리 페이지마다 하나의 가상 페이지 항목만 존재하기 때문
• 만약 메모리를 공유하는 다른 프로세스가 참조하면 페이지 폴트가 발생하고 매핑이 다른 가상 주소로 바뀜

정리

CPU가 p, d라는 논리 주소를 주고, 논리 주소에 있는 p가 페이지 테이블에 어디 있는지 검색한다.

해당 p는 프로세스마다 고유한 값이 아니기 때문에 검색할 때, 현재 진행되는 프로세스의 id를 같이 넣어 구분한다.

찾게 되면 찾아진 위치가 위에서부터 몇 번째인지 보고 이 위치에 해당하는 번호를 페이지 프레임에 넣어준다.

 

IPT를 사용할 때 위에서부터 순차적으로 검색하게 되는데 시간낭비가 너무 심하다

따라서 associative register를 사용하여 병렬적으로 탐색하여 시간적 오버헤드를 줄인다.

 

스와핑(Swapping)

 

기본 스와핑

• 메모리에 너무 많은 프로그램이 올라와있으면 시스템이 굉장히 비효율적이기 때문에 "중기 스케줄러"가 일부 프로그램을 골라서 통째로 메모리에서 디스크로 쫓아냄
  • 메모리에 존재하는 프로세스의 수를 조절
• "중기 스케줄러"가 swap out 시킬 프로세스를 "결정"하는 역할
  • 중기 스케줄러를 swapper라고도 부름
• "CPU 우선순위"가 낮은 프로그램을 우선적으로 쫓아낸다.
• 메모리에 올라온 프로세스의 주소 공간 전체를 "backing store"에 일시적으로 내려놓음
  • backing store(swap area)는 하드디스크이다
  • 파일 시스템과는 별도로 존재하는 영역
    • 파일 시스템은 전원이 나가도 유지되야하는 비휘발성
      스왑 영역은 프로세스가 수행 중인 동안에만 디스크에 일시적으로 저장하는 공간(저장기간 짧음)
• 메모리 -> backing store : swap out
  backing store -> 메모리 : swap in
• swapping system이 지원되기 위해서는 바인딩과 연결하여 생각
  • 만일 컴파일, 적재 타임이 사용되고 있다면 쫓겨났다가 메모리로 다시 올라올 때는
    원래 위치로 올라와야 한다. 다른 메모리가 비어있어도 그 자리 그대로 와야 한다는 말이다.
    그래서 swapping의 효과를 발휘하기 어렵다. 따라서 런타임 바인딩이 적용되는 시스템에서
    효과적이다.

 

페이징에서의 스와핑

• 위 방법은 프로세스를 "전체" 이동시키기 때문에 시간이 매우 걸림
  • 최신 운영체제에서는 더는 사용 X
• 따라서 프로세스 전체가 아닌 프로세스 "페이지"를 스왑함
• 메모리 -> backing store : page out
  backing store -> 메모리 : page in 
• 가상 메모리와 함께 잘 작동함

 

세그멘테이션

• 프로세스를 구성하는 주소 공간을 의미 단위로 쪼갠다
  • ex) code, data, stack
  • 더 잘게 code 중에서 main 함수 등 함수 별로 쪼갤 수도 있다.
• 논리적인 단위로 나눈 것으로 크기가 "불균일"하다
•  
• 논리적 주소는 segment-number, offset 구성
• 세그먼트 별로 주소 변환을 해야 해서 주소 테이블이 존재하고, 테이블의 위치를 알려주는 레지스터가 있다.
  • STBR 
    • 물리적 메모리에서의 segment table의 위치
  • STLR
    • 프로그램이 사용하는 segment의 수

 

 

논리 주소 구성

• 세그먼트 번호(s)
  
  • 해당 논리적 주소가 프로세스 주소 공간 내에서 몇 번째 세그먼트인지 나타냄
• 변위(d)
  • 세그먼트 안에서 얼마나 떨어져 있는지를 나타냄

세그먼트 시작 위치는 레지스터가 가지고 있음

그로부터 세그먼트 번호만큼 떨어진 엔트리에 가면 세그먼트가 물리적 메모리에 몇 번지에 있는지 가지고 있다.

 

세그먼트 테이블의 엔트리 개수는 프로그램이 "사용하는 세그먼트의 개수"로 정해진다.

• 페이징 테이블의 엔트리 수는 프로세스의 주소 공간이 가질 수 있는 최대 영역만큼 엔트리가 만들어짐

 

세그먼트 테이블의 정보

• base
  • 시작 위치를 의미
• limit
  • 세그먼트의 길이를 나타낸다.
  • 페이징에서는 페이지 크기가 모두 동일하다.
    하지만 세그멘테이션은 의미 단위로 자르는 것으로 각 길이가 불균일 하다
    그래서 해당 세그먼트의 길이가 얼마인지를 테이블 엔트리에 같이 가지고 있게 된다.

 

주소 변환의 조건

• CPU가 주어진 논리적 주소의 세그먼트 번호가 프로그램의 세그먼트 개수보다 클 수 없다.
  • 요청한 세그먼트 번호는 5번인데, 현재 세그먼트가 3개로 이뤄져 있다 -> trap 발생
• 논리적 주소의 세그먼트 길이가 limit보다 클 수 없다.
  • 세그먼트의 길이가 1000바이트인데, 세그먼트로부터 offset을 2000바이트 요청한다면
    잘못된 요청이다.

 

주소 변환 과정

• 세그먼트의 시작 위치에 offset을 더해서 주소 변환을 하게 된다.
• 위에서부터 base위치만큼 떨어진 곳에 세그먼트가 시작
• 거기서부터 d만큼 떨어진 위치에 가면 원하는 주소의 내용이 들어있게 된다.
• limit가 세그먼트 길이고, base가 세그먼트의 시작 위치를 나타내는 값이다.

 

Paging vs Segmentation

• 페이징 기법은 페이지 크기가 균일하기 때문에 해당 offset의 크기가 결국 페이지 크기만큼 결정
  • 세그멘테이션에서는 32 비트라고 하면 offset 부분은 미리 결정되야한다. 
    세그먼트 길이는 이 offset으로 표현할 수 있는 비트 수 이상은 안되기 때문
• 페이징 기법은 시작 주소가 프레임 번호로 주어지면 된다. 
  물리적 메모리도 똑같은 프레임으로 나눠져 있기 때문이다.
  • 세그멘테이션은 크기가 모두 다르기 때문에 이 세그먼트가 어디에서부터 시작인지,
    그거를 정확히 바이트 단위 주소로 알려줘야 한다.
• 세그멘테이션에서 세그먼트 크기가 불균일하기 때문에 가변 분할 방식을 사용하여
  중간에 사용되지 않는 hole들이 생길 수 있다.

 

editor는 현재 세그먼트 0번으로 공유한 코드이다.

페이징과 마찬가지로 같은 논리상의 주소를 가지며, 같은 세그먼트 번호를 가진다.

 

Segmentation with paging

 

세그먼트 하나가 여러 개의 페이지로 구성되어 있다.

1. 세그먼트에 대한 주소 변환을 한다
2. 논리 주소는 세그먼트 번호와 세그먼트 안에서 얼마나 떨어져있는지 나타내는 offset이 저장
3. 세그먼트 테이블을 찾는다.
   1. 메모리의 어디에 위치하는지 알기 위해 STBR에서 찾는다. 
      시작점부터 s번째 엔트리를 가면 세그먼트 번호에 해당하는 s번째 세그먼트에 갈 수 있다.
4. 이 세그먼트에 대한 주소변환 정보가 있다.
   1. 원래 세그멘테이션 기법에서는 해당 세그먼트가 메모리에 어디에 올라와있는지 처음 위치(base)가
      담겨 있다. ( 세그먼트가 통째로 메모리에 올라가기 때문)
   2. 해당 방법은 세그먼트 하나가 여러 개의 페이지로 나뉘기 때문에 
      세그먼트를 구성하는 page table의 주소(시작점)가 담겨 있다.

 

세그먼트 하나가 여러 개의 페이지로 나뉜다

• 각각의 페이지 별로 주소 변환을 해야 함 -> 세그먼트 당 페이지 테이블 존재
  • 전에는 프로세스 당 페이지 테이블이 존재했음

 

해당 페이지 테이블은 몇 개의 엔트리로 나뉘나?

• 세그먼트 길이가 얼마인지를 보면은 이 페이지 테이블의 엔트리가 몇 개인지 알 수 있음
• 따라서 그 길이에 벗어나는 요청에 대해서는 trap 발생

Q.
주소 변환의 주체는 하드웨어 일까? OS일까?

A.
모두 하드웨어가 해주는 것이다.

 

Q.
어떤 프로세스가 CPU를 가지고 있으면서 메모리 접근하는 것은 운영체제 도움을 받는 것인가?

A.
도움을 전혀 받지 않는다. 주소 변환을 할 대마다 OS가 중간에 개입을 한다면
CPU가 운영체제로 넘어갔다가 다시 주소 변환이 완료된 후 이 프로세스에게 넘어와야 한다.
이 부분이 말이 안 된다. 주소 변환은 무조건 하드웨어적으로 이뤄진다.

OS가 관여하는 것은 I/O 장치가 호출될 때이다.

 

 

---

Reference

출처 :
- ABRAHAM SILBERSCHATZ ET AL., OPERATING SYSTEM CONCEPTS, NINTH EDITION, WILEY, 2013
- 반효경, 운영체제와 정보기술의 원리, 이화여자대학교 출판부, 2008

 

https://core.ewha.ac.kr/publicview/C0101020140425151219100144?vmode=f   

https://core.ewha.ac.kr/publicview/C0101020140429132440045277?vmode=f    

https://core.ewha.ac.kr/publicview/C0101020140502151452123728?vmode=f    

https://core.ewha.ac.kr/publicview/C0101020140509142939477563?vmode=f   

 

운영체제와 정보기술의 원리 (반효경 지음)