OS - 2.1 (MV) (1) Memory Virtualization

  지금까지 우리는 Process Virtualization에 대해 알아보았다. 이번 포스팅부터는 Memory Virtualization이다. 1.1 포스팅에서 언급했듯, 이 두 Virtualization이 모두 이루어져야 진정한 현대 OS가 탄생한다.

  한편, 사실 과거 SP나 Process Virtualization에서 이 MV Chapter 내용의 일부분을 이미 여러 차례 언급한 바 있다. Process의 Address Space, 그것이 바로 본 Chapter의 핵심인데, 과거 포스팅부터 쭉 읽어온 자라면, 이미 어느 정도 익숙할 것이다. 단지 이번엔 이 개념을 좀 더 깊숙히, 자세히 알아보는 것일 뿐이다.

  본격적인 설명에 앞서, 잠시 System Programming 및 Operating System Programming 시에 상당히 도움이 되는 'Binary & Hexadecimal 읽기' 방법을 언급하겠다.

• 다음의 값들은 외워두는 것이 편리하다.

  • 2^10 = 1024 = K
    • 2^15 = 2^5 x K = 32K
  • 2^20 = M
  • 2^30 = G
    • 2^33 = 2^3 x G = 8G
  • 2^40 = T

• Hex 주소 읽는 법

  • ex) 0x400000
    • Hex에서 1 Digit는 4 Bit이다. 따라서, 0x400000은 '4x5+2'비트로 나타낼 수 있다.
      • 이는 2^22로, 4M가 된다.

  이제 진짜 개념 설명을 시작한다. 먼저, '만약 OS가 Address Space에 대한 Abstraction을 제공하지 않는다면 어떤 일이 벌어질지'를 알아보자. 아래의 그림은 초기 Operating System의 구조를 보여준다.

Early Operating System : Load only one process in memory!

That means, it had Poor Utilization and Efficiency ★

~> OS SW가 메모리에 저장된 영역에 대해 아무런 보호 조치가 없고, 구분도 없었기에 Program이 의도 또는 실수로 접근해 OS를 죽이더라도 아무런 대응책이 없었다.

Virtual Address Space

  알다시피, 이러한 초기 OS에서, Multi-Programming, Multi-Tasking 개념이 등장하면서 지금의 모습으로 발전이 이뤄졌다.

• Multi-Programming

  • Memory에 Multiple Processes가 Load된다.
  • 각 Process는 짧은 시간 동안 수행되고, Switch되는 과정을 반복한다.
  • Utilization과 Efficiency가 높다.

• Time-Sharing

  • CPU는 여러 Job을 계속해서 Switch해가며 돌린다. 이를 통해 User에게 'Interactive Computing' 환경을 제공한다.
    • 이러한 Time-Sharing의 구현을 위해선 Protection을 신경써야한다. ★★★

      • Process 간의 Errant Memory Access를 막아야한다. ★★★

        • Errant : 잘못을 하는

        • "내 Process가 다른 Process를 오염시키거나, OS를 오염시키는 일이 생겨선 아니된다!!!"

          • 이를 위해 등장한 개념이 Process Address Space이다.

• OS는 각 Process에게 'Physical Memory의 Abstraction'인 'Virtual Address Space (Process Address Space)'를 제공한다.
  • Running Process에 대한 정보가 담겨 있다.
  • Code, Data, Heap, Stack 등의 영역으로 구성된다.

Every address in a running program is virtual!! ★★★★★

OS가 Virtual Address를 Physical Address로 변환한다.

int main(int argc, char *argv[]) {
	printf("Address of code : %p\n", (void *) main);		// main 함수의 주소
	printf("Address of heap : %p\n", (void *) malloc(1));	// Heap 영역의 주소
	int a = 5;
	printf("Address of stack : %p\n", (void *) &a);		// Stack 영역의 주소

	return 0;
}

(출력, 64-Bit Linux Machine 기준)
Address of code : 0x40047e
Address of heap : 0xcf2024
Address of stack : 0x7fff8ca42fcd

~> main 함수는 Text 영역 어딘가에 위치한다.
~> malloc(1)이 반환한 공간은 Heap 영역 어딘가에 위치한다.
~> Local Variable a는 Stack 영역 어딘가에 위치한다.
~~> 알다시피, Heap과 Stack 사이엔 커다란 Free 공간이 있고, 서로가 마주보며 확장한다. Heap은 높은 방향으로, Stack은 낮은 방향으로! ★
===> 이들은 모두 Virtual Memory Address이며, OS는 이러한 Virtual Address를 Physical Address로 Mapping한다. ★★★

Reserved Kernel Area

  모든 Process는 각자의 Virtual Address Space를 가진다.

이때, 그 Virtual Address Space 중 일부는 Kernel을 위한 영역으로 Reserve되어 있다.

• 주로, 최상단 Stack 영역이 있으면, 그보다 더 상위 주소에 Kernel 영역이 Reserve되어 있다. 이를 'Kernel Virtual Memory'라고도 부르며, 이 영역이 Process Virtual Memory 영역과 합쳐져서 Process Address Space가 되는 것이다.

Process(Virtual) Address Space
= Process Virtual Memory + Kernel Virtual Memory

• Kernel Virtual Memory 영역은 Process Virtual Memory 영역의 Stack Segment 최하 위치의 바로 다음(상위) 위치부터 시작한다.

  • Kernel Virtual Memory 영역은 Process 개별마다 데이터가 다른 'Process-Specific' 영역과, 모든 Process가 공통의 데이터를 가진 영역으로 나눌 수 있다.

• 위 그림은 32-Bit Linux Machine 기준이다. ★

  • 총 4G의 Virtual Address Space가 있고, 그 중 최상위 1G가 Kernel Virtual Memory!
    • Kernel Address Space는 0xC0000000부터 시작한다. ★★★
  • Linux Version에 따라 다를 수 있으며, 중간에 변형도 가능하다.

• 한편, Process Virtual Memory에서 Code Segment는 0x00000000에서 바로 시작하는 것이 아니라 0x00400000 영역에서부터 시작함을 주목하자.

  • 0x400000 = 2^22 = 4M로, 즉, Code 영역은 0번지에서부터 4M만큼 띄워놓고 시작한다. ★
    • Memory Accesing 간의 효율성 제고를 위해 이렇다고 한다.

Process가 Trap Interrupt를 Kernel에게 걸 때, Kernel은 Process의 Kernel Virtual Memory 영역을 사용해 Service를 제공한다. ★

즉, System Call을 사용할 때 Kernel Virtual Memory를 사용하는 것! ★

• Process Virtual Memory는 가상화된 데이터가 Linear하더라도, 실제 Physical Memory에선 무작위로 Mapping될 수 있다.

  • 예를 들어, Process가 "int arr[16384];"로 큰 Global Array를 선언하면, 그 Array는 Data 영역에 Linear하게 잡힌다.
    • 허나, 실제 Main Memory에선 Linear하지 않을 가능성이 높다. ★

• 반대로, Kernel Virtual Memory는 Physical Memory에 Linear하게 Mapping된다. ★★

  • Physical Memory에 저장되어 있는 OS Data를 빠르게 접근하기 위해! ★

Kernel Stack

Application Program에는 우리가 흔히 Stack이라 부르는 User Stack 뿐만 아니라 Kernel Stack도 존재한다.

User Mode에서 돌아갈 땐 User Stack이 사용되고,
Kernel Mode에서 돌아갈 땐 Kernel Stack이 사용된다.

~> 즉, Process가 일반적인 Command를 수행할 땐 User Stack을 사용하고, System Call을 수행할 땐 Kernel Stack을 사용하는 것이다. ★★★

• Application이 System Call을 호출하면,
  • Trap Interrupt를 통해 Kernel에 진입한다.
  • User Stack에서 Kernel Stack으로 Switch한다. ★★★
    • pintOS에선 Kernel Stack이 PCB 시작 지점에서 4KB 떨어진 곳에 할당된다.
      • 그래서, Kernel Code에서 너무 큰 Data Structure를 잡으면 터질 수 있다.
    • 이를 통해 Privilege Level을 높일 수 있다. ★★

~> Kernel Virtual Memory에는 Kernel Code & Data, Physical Memory, Kernel Stack 등이 주소가 높아지는 순서로 마련되어 있고, Trap 시 CPU의 EIP(Instruction Pointer) Register Value가 Process Virtual Memory Code Segment의 특정 명령에서 Kernel Virtual Memory Code Segment의 특정 명령으로 이동됨을 주목하자. ★★★

• 위 그림들을 보자. 각 Process의 PCB를 비롯한 Kernel Memory 영역은 Physical Memory에 Linear하게 마련된 OS 영역에 Linear하게 Mapping된다. ★★
  • 이때, 각 Physical Memory의 OS Code 부분에 각 Process의 PCB를 비롯한 Data 부분들이 존재할텐데, 바로 이곳에 각 Process의 Kernel Stack이 자신들의 PCB 위치에서 4KB 정도 떨어진 곳까지의 영역을 점유한다. (pintOS 기준) ★★★
    • 각 Process의 User Stack은 자신들의 Process Memory 영역에 다들 개별적으로 존재하는 것과 대조적이다.

각 Process의 User Stack은 자신들의 Process Address Space가 Mapping된 Random한 Physical Memory에 개별적으로 존재한다. ★★★

반면, Kernel Stack은 모두 OS가 저장되어 있는 Physical Memory 영역에, 그중에서도 Process들의 PCB가 모여있는 곳에 Kernel Stack도 모여있는 것이다. ★★★

  아래는 위에서 설명한 구조가 pintOS 상에선 어떻게 구현되어 있는지를 보여준다. pintos/src/threads/thread.h 파일의 Thread Structure이다. Memory Virtualization 상태를 확인할 수 있다.

struct thread
{
	/* Owned by thread.c. */
	tid_t tid; 						/* Thread identifier. */
	enum thread_status status; 		/* Thread state. */
	char name[16]; 					/* Name (for debugging purposes). */
	uint8_t *stack; 				/* Saved (kernel) stack pointer. */
	int priority; 					/* Priority. */
	struct list_elem allelem; 		/* List element for all threads list. */

	/* Shared between thread.c and synch.c. */
	struct list_elem elem; 			/* List element. */

#ifdef USERPROG
	/* Owned by userprog/process.c. */
	uint32_t *pagedir; 				/* Page directory. */
    
    /***************************************/
    /* User Program Project Implementation */
    /*      ~> This is omitted here!!!     */
    /***************************************/
    
#endif
	/* Owned by thread.c. */
	unsigned magic; 				/* Detects stack overflow. */
};

• stack이라는 Pointer가 바로 Kernel Stack을 가리킨다. ★

• magic Number는 Kernel Stack의 Stack Overflow를 체크하는 용도로 도입된 것인데, Kernel Stack이 자라나다가 magic Number에 도달하면 터지는, 그런 원리로, 추후 다시 설명할 것이다.

Mapping

  User Program은 항상 Logical(Virtual) Address를 다룬다. 항상 Process(Virtual) Address Space를 다루며, 절대로 Physical Address Space에 직접 접근하지 않는다. ★

• Logical Address : CPU, OS에 의해 생성되는 주소 (Virtual Address)

• Physical Address : Memory Unit에서 바라보는 주소

~> 우리는 이제 이 Mapping 관계에 대해 알아볼 것이다.

Virtual Address에서 Physical Address로의 Run-Time Mapping은 MMU(Memory Management Unit)라는 HW에서 수행한다. ★★★

MMU의 종류에 따라 Mapping Algorithm이 달라진다. 가장 널리 쓰이는 방법은 Paging으로, 본 Chapter 2의 핵심 개념 중 하나이다.

여담) 32-Bit Linux Machine의 Maximum Memory Size는 4GB이다. 즉, 사용자 입장에서 가장 크게 사용할 수 있는 크기는 3G밖에 되지 않는 것이다. 1G는 Kernel(OS)것이므로. 그래서 보통 Process의 Logical Memory를 Disk에도 맵핑시키는 것이다. 공간이 한정적이니까!

• Logical(Virtual) Memory를 똑같은 크기의 Block들로 나눈다.

  • 이를 Page라고 부른다.
    • 2^n승 크기로 설정하며, 일반적으로 512B에서 8192B까지 나뉜다.
      • 0.5K ~ 2K Size

• Physical Memory도 고정 사이즈 Block들로 나눈다.

  • 이를 (Page) Frame이라 부른다.

일반적으로 Logical 관점의 Page와 Physical 관점의 Frame은 사이즈가 동일하다. ★★★

Mapping을 위해선 Free Frame들을 추적해야한다.

n개의 Page로 이루어진 Program을 수행하기 위해선 m(<= n)개의 Free Frame이 필요하다.

Frame이 Page 개수보다 적어도 된다. 왜냐? Disk에 올려도 되니까! ★★★

• 각 Process는 Page Table을 구성해 Logical Address를 Physical Address로 변환한다.
  • Page Table의 Index가 곧 Page Number이고, 그 Index의 Slot 안에 있는 Value가 Physical Frame Number, 약칭 PFN이다. ★★★
    • Logical Memory Page i를 Physical Memory Page Frame j로 Mapping하는 것!

각 Process는 자신만의 Page Table을 가지고 있다. ★★★

  금일 포스팅은 여기까지이다. 다음 포스팅에서 이 맵핑을 좀 더 자세히 알아보자.