Memory Management

• Subdividing memory to accommodate multiple processes
• Memory needs to be allocated efficiently to pack as many processes into memory as possible

우리가 사용하고 있는 메모리 시스템은 프로그램 전체를 통으로 집어넣을 수 없다.
메모리 크기에 비해 프로그램의 크기가 굉장히 큰 것도 있고, 동시에 여러 프로그램들을 실행시키고 싶어서 가능한 많은 프로그램을 메모리에 올려 놓으려는 측면도 있다. 그러다보니 프로그램의 일부만 메모리에 올라와서 실행을 하게 되는 시스템이 구현되었다. 이를 Virtual Memory System 이라고 한다.

Virtual Memory System 은 8장에서 조금 더 자세히 배우고 7장은 그 이전 단계를 배우게 된다.

이 때는 프로그램 전체를 메모리에 다 집어 넣었다.
프로그램이 실행을 하려면, 프로그램 전체가 메모리에 들어 있어야만 실행이 되는 상태인 것이다.
이러한 시스템을 Real Memory System 이라고 한다.

Real Memory System 에서 메모리 관리를 어떻게 하는지에 대해 알아보도록 하자.

한번에 한 프로세스만 메모리에 들어가는 것이 아니기 때문에 여러 프로세스들이 메모리에 들어 있어야 한다.

메모리를 잘 나누어서 여러 프로세스들을 메모리에 넣고 동시에 여러 프로세스들을 실행시키고 싶은데,
이때 가능한 많은 프로세스가 메모리에 들어가면 좋을 것이다.

메모리 공간을 잘 나눠서 최대로 많은 프로세스들을 메모리에 집어 넣고 실행을 시키고자 하는 것이 목적이다.

---

Memory Management Requirements

프로세스 여러개를 메모리에 집어 넣을 때, 해결되어야만 하는 아주 중요한 문제가 존재한다.

1. 🌟 Relocation 🌟

프로그램은 PCB, Data, Stack으로 이루어져 있다.

Jump O

Jump 명령: 코드를 순차적으로 실행하다가 어느 지점으로 이동해서 실행하는 명령

프로그램 코드를 보면, 굉장히 많은 Jump 명령들이 존재 → Jump + 몇번지

• A 함수 호출 → A 함수로 Jump
• if 문의 조건에 맞지 않아 else로 이동 → Jump
• 반복문: 처음으로 돌아가기 → Jump

Jump X

Jump 하지 않는 애들 → Data 읽기

⇒ 프로그램 코드는 대부분 뒷 부분에 주소가 존재한다.

프로그램을 Compile 할 때는, 이 프로그램이 메모리 어디 들어가는지 알 수 없다.
⇒ 실제 코드하나하나 데이터 하나하나가 메모리 몇 번지에 있는지 알 수 없기 때문에, 그냥 간단하게 0번지를 기준으로 Compile 한다.

Compile	실제 Memory 번지
0번지 기준으로 Compile	→ 3000번지

ex) 100번지에 있는 데이터를 가져와라 라고 하는 명령어
	⇒ 3100번지에 있는 데이터를 가져와라 라는 명령어로 바뀌어야 한다.

일단 Compile 을 해둔 다음, 메모리 몇번지에 들어갈지 확정이 된 다음, 주소를 다 바꿀 수는 없고,
그렇게 되면 프로그램이 메모리에 들어갈 때 시간이 어마어마하게 많이 걸린다.
⇒ 간단하게 주소를 바꿀 수 있는 방법이 필요하다.

위와 같이 주소를 다 바꿀 수는 없다. → 시간 소요가 많다.
⇒ Rellocation (재배치) 를 이용한다.

Rellocation : 프로그램 안에 있는 주소 값들을 실제 주소에 맞게 전부 다시 재배치하는 과정이다.

2. 🌟 Protection 🌟

프로그램이 메모리에 들어 있을때,
이 프로그램은 1000번지 ~ 1050번지에 들어 있다.

당연히 여기 있는 모든 주소들은 1000~1050번지까지의 코드나 데이터를 access 하는 주소여야 한다.

그런데 갑자기 900번지에 있는 데이터를 가져와라 라는 코드가 튀어나오거나,
2000번지에 있는 코드로Jump 해라 라는 코드가 튀어나오면,
뭔가 잘못된 것이다.

→ 이 경우에는 프로그램을 실행시킬 수 없다.

Protection : 각 프로세스에 할당된 메모리 영역 이내에서만 데이터나 코드를 access 하는지 확인하는 과정이다.

Protection 이 지켜지지 않으면 프로그램을 종료해야 한다.

3. Sharing

서로 다른 프로세스가 공통으로 어떤 메모리 영역을 access 해야하는 경우가 있는데, 이를 시스템이 지원해주어야 한다.

앞으로 얘기할 것

1. 메모리 어떻게 잘 잘라서 최대한 많은 프로세스 메모리에 집어 넣고 실행을 시킬 수 있을까?
2. 메모리를 잘라서 실행을 시키는 과정에서 🌟 Relocation , Protection 을 어떻게 할 것인가?
   → 이 두 문제가 해결이 안되면, 프로그램을 실행시킬 수 없다.

---

---

Partitioning

Fixed Partitioning

고정된 크기로 메모리를 아예 잘라놓고 시작한다.

좋은점: 메모리를 딱 n등분 했을 때 → 각 Partion의 시작점이 이미 정해져있다.
⇒ Relocation 작업이 따로 필요하지 않다. / Relocation 작업이 간단하다.

나쁜점: 공간의 크기를 맞추기 어렵다. 프로세스의 크기가 메모리 공간의 크기에 맞는지 안맞는지 알기 어렵기 때문에 공간의 낭비 가 생길 수 있다.

ex) 프로그램을 Compile 할 때, 
1000번지에 들어가서 실행하고 싶으면, 1000번지 기준으로 Compile 하면 된다. 
3000번지에 들어가서 실행하고 싶으면, 3000번지 기준으로 Compile 하면 된다. 

Equal-size partitions

• 같은 크기로 자르기
• 문제점
  1. Partition 보다 큰 프로그램 크기 → 실행 불가
  2. Partition 보다 작은 프로그램 → 실행 불가
     ↳ 우리의 목표는 최대한 많은 프로그램을 동시에 실행시키는 것이기에,
     남은 빈공간을 이용해서 다른 프로그램을 실행을 시키고 싶은데,
     이 시스템에서는 Fixed Partitioning 이라 Compile 을 할 때부터, 각 Partition 의 시작점에 맞춰서 하기 때문에 빈공간을 이용할 수 없다.

Unequal-size partitions

• 다양한 크기로 자르기
• 컴파일할 때 크기 확인
  (Compile을 할 때, 내 프로세스의 크기가 8M라 8M 메모리에 들어가면 되겠다 싶으면, 8M Partition에 맞춰서 Compile 하면 된다.)
• 메모리 공간 낭비가 덜하진 않다.
  → 반 이상 낭비될 수 있다.
  ↳ 특정 크기의 프로세스의 수요가 많아 특정 크기의 메모리 공간은 대기하는 프로세스가 많지만, 수요가 적은 크기의 메모리 공간은 이용되지 않고 낭비될 수 있다.

⇒ Equal-size Fixed Partitioning 보다 낫다고 할 수 없다.

Dynamic Partitioning

메모리 크기가 고정된 Partition X → 프로그램의 크기만큼 메모리를 자른다.

External fragmentation problem

External fragmentation : 프로세스와 프로세스의 사이

Dynamic Partitionin 의 가장 큰 문제점이다.

⇒ Can resolve using compaction

External fragmentation problem 을 해결하는 유일한 방법 : Compaction ⇒ 모든 프로세스들을 위로 올려 붙여서 공간을 확보한다.
↳ 전체 프로세스를 전부 다시 읽어서 다시 써야한다.
⇒ 시간이 어마어마하게 오래 걸린다.

↑ 위의 그림은 메모리가 효율적으로 사용되는 것처럼 보인다.
프로세스와 프로세스 사이에 공간이 하나도 없다.

↑ 하지만, 프로세스가 작업을 끝내거나, Swap Out이 된다면, 프로세스는 메모리 바깥으로 나가게 된다.

이렇게 되면, 메모리안에 프로세스와 프로세스 사이에 사용할 수 없는 빈 공간 (짜투리 공간) 이 생기게 된다.

이 빈 공간을 합치면 프로세스 다시 실행시킬 수 있지만, 떨어져 있는 각각의 짜투리 공간으로는 프로세스를 실행시키지 못하고 공간이 낭비되게 된다.

---

Dynamic Partitioning Placement Algorithm

프로세스를 어느 공간에 배치할까? → Compaction 횟수랑 관련이 있다.

Operating system must decide which free block to allocate to a process

• Best-fit
• First-fit
• Next-fit
• Worst-fit

가능한 Dynamic Partitioning 을 사용하면서, 가능한 Compaction 횟수를 줄여야 한다.

Free Block : 메모리의 빈 공간

Best-fit

• 전체를 탐색 O
  ⇒ 서치 시간이 증가한다.
• External fragmentation 가 적어 Compaction이 적은 공간을 찾아 프로세스에게 공간을 할당한다.
• Free Block 이 너무 많으면, 전체 Free Block 전부를 검색하기엔 시간이 너무 오래 걸린다.

ex) 새로운 프로그램 16M 를 어디에 배치해야 External fragmentation 가 적어, 
Compaction이 적게 할 수 있을까?

프로세스의 크기인 16M와 제일 가까운 18M에 16M 프로세스를 집어 넣는다. 
⇒ 2M가 남는다.
⇒ External fragmentation 최소

First-fit

• 전체 탐색 X
  ⇒ Free Block 전체를 서치할 시간에 Compact 를 더 하자
• 처음부터 탐색: 위에서부터 프로세스 크기에 맞게 할당 가능한 첫 번째 공간 찾기
  → 항상 앞에서부터 할당하므로, 앞쪽은 굉장히 작은 짜투리 공간만 남아 있을 것
  ⇒ 앞쪽은 프로세스를 할당할 수 없는 경우가 많아 밑으로 한참내려가야 한다.

Next-fit

• 전체 탐색 X
  ⇒ Free Block 전체를 서치할 시간에 Compact 를 더 하자
• 마지막으로 allocation 한 부분 이후부터 탐색한다.
  ⇒ 뒤쪽에 훨씬 더 큰 공간이 남아 있을 수 있다.
• first-fit 보다 좋다.

Worst-fit

• 제일 안맞는 공간을 찾는 것 : 내 프로그램이 메모리에 들어가고 제일 빈 공간이 큰 곳을 찾는다.
• 내 프로그램 → 빈 공간
  ⇒ 남아 있는 공간 중 제일 큰 공간 을 할당한다.
  ⇒ 제일 External fragmentation 가 크다.
• 사용하는 이유: 제일 큰 공간이기 때문에 여러 프로세스가 들어갈 수 있다.

---

Buddy System

Dynamic Partition과 Fixed Partition 의 단점을 피한 시스템

• Entire space available is treated as a single block of 2^U
• If a request of size s such that 2^(U-1) < s <= 2^U, entire block is allocated
  • Otherwise block is split into two equal buddies
  • Process continues until smallest block greater than or equal to s is generated

어떤 크기의 메모리가 필요할 때
→ 그 크기의 메모리를 나눠주는 것 X
→ 그 크기보다 큰 2^U 공간을 할당해준다.

알아야 할 것
1. 할당 받는 공간의 크기를 알아야 한다.
2. 이 공간을 아무렇게 떼어 주는 게 아니라, 항상 메모리를 반씩 나누어 나한테 할당해 줄 수 있는 크기만큼 잘라졌을 때, 그 공간을 할당해준다.

	ex) 10k 의 공간이 필요할 때 → 16k를 할당해준다.
    8k <= 10k <= 16k

• External fragmentation X
• Compaction X
• 단, Internal Fragmentation O

100k 보다 큰 2^u 값 = 2^7 = 128

100k 크기의 프로세스를 메모리에 할당
→ 메모리 1M 를 반으로 나누면 512k, 512k buddy가 만들어지는데, 여전히 100k 보다 크므로 두개 중 하나만 다시 반으로 나눈다.
→ 512k 를 반으로 나누어 256k, 256k Buddy 가 만들어지는데 아직 100k 보다 크므로 이를 다시 반으로 나눈다.
→ 64k, 64k Buddy 가 만들어지는데 이는 100k 보다 작으므로 100k 프로세스는 128k 공간에 할당된다.
→ 이렇게 되면, 28k 가 남게되어 Internal Fragmentation 이 발생하게 된다.

→ 프로세스에게 메모리 공간을 할당하고 프로세스가 종료하고 나면,
Buddy 끼리 다시 합친다.
→ 큰 공간으로 가지고 있는다.
↳ 이 공간을 최대한 크게 가지고 있어야 크기가 큰 프로그램도 실행시킬 수 있기 때문이다.
→ 공간을 합칠 때는, 같은 Buddy끼리만 합칠 수 있고, 다른 Buddy 끼리는 합칠 수 없다.

Fixed Partition 의 단점 극복: 공간이 최대 메모리의 크기랑 같은 프로그램의 크기 실행시킬 수 있다. Fixed Partition은 고정된 Partition으로 나누어 놨기 때문에 프로그램의 크기가 최대 Partition의 크기보다 크면 실행을 할 수 없다.
→ 여기서는 전체 메모리 크기도 사용하여 프로그램을 실행시킬 수 있다.
⇒ Fixed Partition 의 크기 제한이 없다: 프로그램 크기와 상관 없이 모든 프로그램을 실행시킬 수 있다.

메모리를 자르고 다시 합치는 과정에서 External Fragmentation 이 존재하지 않는다. Partition 과 Partition 사이에 뭔가 남아있는 것이 없고, Compaction 을 하지 않는다.
단, Internal Fragment 가 존재한다.

Internal Fragment

Partition 과 Partition 사이의 공간이 아니라 나에게 주어진 Partition 내부의 공간 이 남는 것

Internal Fragment 는 나에게 할당된 공간의 반을 넘어갈 수 없다.
적어도 반보다 작다.
→ 만약, 내게 할당된 공간의 반보다 더 작은 프로그램이었으면 한번 더 반으로 잘랐을 것이다.

---

Address

• 메모리를 어떻게 나누지?
• 어느 공간으로 들어가지?

Fixed Partition 내가 어느 공간으로 들어갈지 미리 정하면, Compile 할 때, 아예 그 공간에 맞춰서 Compile 하기 때문에 Relocation이 필요없다.

그러나, 같은 크기의 Partition 은 내가 Compile 할 때 Fix 해 놓으면, 그쪽 줄에 서 있는 프로세스가 많으면, 다른 곳에 공간이 있어도 실행을 할 수 없다.
⇒ Fix 를 안해 놓는 것이 좋다.

UnEqual Size Partition 같은 경우도, 내가 8M 크기에 맞추어 딱 Compile을 해 놓았는데, 8M 크기의 공간에는 자리가 없고, 그보다 큰 12M 쪽은 자리가 있을 겨우, 큰 공간에 가서 실행을 할 수도 있지만 미리 fix 해 놔서 이용할 수 없다.
⇒ 따라서 Compile 할 때 Relocation 을 미리 해 두는 것은 좋지 않다.

이런 경우 어떻게 Relocation 을 할 수 있을까?
↳ Base Register와 Bound Register 를 이용한다.

↓ 밑에와 같은 경우에 Base Register와 Bound Register 를 사용할 수 있다.

• Fixed Partition 을 사용하는데, Compile 할 때 Relocation 을 미리하지 않은 경우
• Dynamic Partition 과 Buddy System 의 경우
  (이 두 시스템은 어차피 내 프로그램이 어디에 들어갈지 알 수 없기 때문에 미리 Compile 을 해둘 수 없다. )

Logical Address

• reference to a memory location independent of the
  current assignment of data to memory
• translation must be made to the physical address

실제 위치랑 상관 없이, 어떠한 논리적인 방법으로 주소를 표현하는 것

Paging System 에서는 Logical Address 를 사용해서 주소를 표현한다.
→ 페이지 번호 와 offset 으로 표현한다.

offset : Page 안에서 몇번째 줄에 있는지를 나타낸다. (줄은 0번부터 시작)

몇번째 Page 의 몇번째 줄(Offset)에 있다고 표현하는 것이다.

↳ 1번 페이지의 476번째 줄에 있다는 것을 의미한다.

Relative Address

address expressed as a location relative to some
known point

0번지 기준으로 계산한 번지이다.

특정 번지를 기준으로 컴파일 한다.
→ 대부분 0번지 기준으로 컴파일 한다.

프로그램이 메모리 어디에 들어갈지 알 수 없는 상황이기 때문에 0번지에 들어간다고 가정하고 Compile 을 한다.

실제 프로그램 안에는 모든 주소가 relative address 로 되어 있다

Physical Address

the absolute address or actual location in main memory

실제주소를 나타낸다.
⇒ 진짜 메모리 몇번지에 데이터나 코드가 있는지?

Relocation = Relative Address → Physical Address

---

Registers Used during Execution

Hardware Suport for Relocation

Base Register

Relocation 은 Base Register 를 사용한다.

Base Register : 프로그램은 PCB + Data + Stack 으로 이루어져 있는데, Base Register 안에는 프로그램 코드의 메모리 (physical) 시작 주소가 적혀 있다.

프로그램 코드의 시작 주소 이지, 프로세스 코드의 시작 주소가 아니다! 프로세스의 시작 주소는 오른쪽 main memory 의 제일 윗 부분 (PCB 의 시작부분) 이다.

프로그램은 PCB 밑에부터 들어가게 된다.
0번지를 기준으로 Compile을 하면 PCB 밑에 부분의 번지를 0번지라고 생각하고 Compile 하는 것이다. 즉, 이 프로그램 앞에 PCB가 붙을 것을 생각하지 않고, 내가 출발지라고 생각하고 0번지로 Compile 한다.

이 프로그램 Code와 Data의 모든 주소는 Program의 시작점에 맞춰져 있다.
⇒ Base Register 의 값은, 프로그램 코드의 시작 주소이다.

만약, 이 프로세스의 프로그램 코드가 3000번지에 적재가 됐다고 가정한다면, 
Base Register에 3000이 들어가야 한다.

Relocation 작업

명령어를 IR 로 가져온다.
명령어 분석 → 앞쪽에 Operation Code, 뒷쪽에 주소 O

만약 jump|200 으로 적혀 있다면, 실제로는 3200번지로 이동해야 한다.
200은 Relative Address 를 가르킨다.
⇒ 3200 번지가 실제 데이터가 있는 위치이다.

⇒ Base Register + Relative Address
= 프로그램 코드의 시작 주소 + IR 의 뒷부분의 주소 부분
= Physical Register
⇒ 실제 Data 가 위치하는 주소

Protection 작업

이 프로그램 코드는 3000~5000 번지 사이에 들어 있다.
⇒ 당연하게도 이 프로그램 안에서 사용하는 모든 주소(Physical Address)는 3000~5000 사이여야 한다.

1000 번지나 5000번지를 가져오라고 하면, 이 프로세스에게 할당된 코드의 범위를 넘어 남의 코드를 가져오는 것이므로, 프로그램을 중단 시켜야 한다.

→ 이를 확인하는 방법: Bound Register

Bound Register

Bound Register : 프로그램 코드의 제일 마지막 부분의 주소를 넣어둔다.
Physical Address <= Bound Register 인지 비교한다.

• 만약 Physical Address <= Bound Register → 내 프로그램 영역
  ⇒ 점프하거나 데이터를 가져오면 된다.
• 만약 Physical Address > Bound Register
  ⇒ 프로그램 인터럽트가 걸리게 된다.

Physical Address = Base Regiser 에 Relatice Address 를 더한 값

Q. 이 시스템에서는 프로세스가 100개가 동시에 실행이 되고 있다. 메모리 안에 프로그램이 100개가 들어 있다. Base Register와 BoundRegister가 몇개씩 필요할까?

100개 X 1개 O

주소를 변환하는 과정(Relocation)은 실행하면서 하는 것이다.
⇒ 즉, 실행을 할때만 Base Register와 BoundRegister가 필요하다는 뜻이다.
⇒ CPU 가 하나이면, 시스템 안에 프로세스가 몇개가 있든 상관 없이, 딱 한 명만 실행한다.
⇒ BaseRegister와 BoundRegister는 하나씩만 있으면 된다.
→ 실행을 시작할 때 BaseRegister와 BoundRegister 값을 세팅한다.

ex) A Program 실행 → B Program 실행 
	⇒ BaseRegister와 BoundRegister 값이 새로 세팅된다.

필요한 가정

프로그램을 메모리에 집어 넣을 때, 이 프로그램을 자를 수가 없다.
⇒ BaseRegister와 BoundRegister로 Relocation과 Protection을 하는 것은 프로세스가 연속된 공간에 할당된다 는 가정이 필요하다.

↓ 모두 프로그램을 연속된 공간에 할당하는 시스템들이다.

• Compile 할 때 Relocation 을 미리하지 않은Fixed Partition
• Dynamic Partition
• Buddy System

단점

• 공간 낭비가 존재한다.
  (공간 낭비가 적은 Buddy System 도 최악의 경우 프로그램이 2^u +1 의 크기를 갖으면, 공간 낭비가 심해지게 된다.)
• 실제 위치와 상관이 없다.

---

Paging System

메모리와 프로그램을 잘라서 사용하는 시스템

• Partition memory into small equal-size chunks and divide each process into the same size chunks
• The chunks of a process are called pages and chunks of memory are called frames
• Operating system maintains a page table for each process
  • contains the frame location for each page in the process
  • memory address consist of a page number and offset within the page

우리의 목표는 메모리에 최대한 빈큼 없이 최대한 많은 프로그램을 넣는 것이다!

그러므로 프로그램을 자르자!
↳ 프로그램을 자르려면 어떤 크기로 잘라야 하는지 기준이 있어야 한다.

Page Frame

먼저 메모리를 잘라야 한다.
메모리를 같은 크기로 자를거고, 이 잘라놓은 한조각 한조각을 Page Frame 이라고 한다.

Page

프로그램도 Page Frame 크기에 맞추어 잘라야 한다.

프로그램을 자른 한 조각을 Page 라고 한다.

⇒ Page Frame 안에 Page 를 집어 넣는다.

Assignment of Process Pages to Free Frames

↑ 위의 그림은 전체 메모리와 프로그램을 15조각으로 나눈 것이다.

• A 프로그램은 4Page 이므로 4Page Frame 을 차지하게 된다.
• B 프로그램은 3Page 이므로 3Page Frame 을 차지하게 된다.

• C 프로그램은 4Page 이므로 4Page Frame 을 차지하게 된다.
• B 프로그램은 Swap Out 하게 되어 3개의 free block 이 생기게 된다.
• D 프로그램은 5Page이다.
  → 만약 이 시스템이 Dynamic Partitioning 이었다면 D 프로그램은 실행시키지 못했을 것이다.
  ↳ D 프로그램은 4, 5, 6 Frame 에도 들어갈 수 없고, 11, 12, 13, 14 Frame 에도 들어갈 수 없다.
  → 이 시스템은 Paging System 이기 떄문에 D 프로그램은 실행이 가능하다.

Paging System 은 페이지들이 연속적이지 않은 공간에 들어가도 된다.
⇒ 최대한으로 공간을 사용한다.
⇒ External Fragment X ← Frame 크기 = Page 크기 이기 때문
⇒ Internal Fragment 는 1개 존재 가능
↳ 프로그램을 Page 크기로 나누는 것이기 때문에,
만약 프로그램이 Page의 배수가 아닌 경우 마지막 Page는 Frame 보다 조금 작을 수 있다.
⇒ Internal Fragment 가 존재할 수는 있지만, Internal Fragment 는 아래의 그림 처럼 ↓ 전체 프로그램 에 딱 한 Page 만 발생하게 된다.

정리

이 방식보다 더 메모리 공간을 낭비 없이 사용할 수 있는 방법은 없다.
Paging System 은 가장 완벽한 시스템이다.

• External Fragment X
• Compaction X
• Internal Fragment 있기는 하지만, 프로그램 중에 딱 1페이지만 있는 거기 때문에 무시할 수 있을 정도이다.

• Bound Register와 Base Register 사용불가 ← 연속적으로 프로그램이 메모리 공간에 할당되지 않기 때문이다.
  ⇒ Bound Register와 Base Register을 사용해서 Relocation, Protection 을 구현할 수 없다.

다른 방식으로 Relocation, Protection 을 해야 한다.
⇒ Page Table 을 사용한다.
↳ 각 프로세스마다 Page Table 이 존재한다.

---

Page Tables for Example

밑에와 ↓ 같은 것들을 Page Table 에 적을 것이다.

• 프로세스의 0번 Page 가 메모리 몇번 Frame 에 들어있나?
• 프로세스의 1번 Page 가 메모리 몇번 Frame에 들어있나?

프로세스 B 는 메모리에 없는 상태이다.

Free frame list : 사용하고 있지 않은 공간

Page# 와 Frame# 는 밑에와 ↓ 같이 2차원 배열이 아니라, 1차원 배열 을 이용해서 나타낸다.

• Page# → Index#
• Frame# → 배열[Page#]

→ X

---

Logical Address

(a) 는 Partitioning, Dynamic Sytem이든, Fixed 이든, Buddy System 이든, Relative address 를 사용한 것이다.
→ 화살표로 표시된 위차가 1502 번지이다.
⇒ 내가 1502 번지에 있는 데이터를 읽고 싶은 것이다.

(b) 는 Paging System에서 Logical Address로 표현한 것이다.

• 얘를 일정한 크기의 Page 로 잘랐다.
• 여기서는 Page 의 크기를 1K 로 가정했다.
  → 1K = 2^10 = 1024 (byte)
• 따라서 1502 번지는 Page1 의 478 번지(offset)가 된다.
  → 1502 - 1024 = 478 (byte)

즉, (a) → (b) 로의 변화는 별도의 계산이 따로 필요하지 않다.
추가로 아무것도 하지 않아도 된다.
→ 해석만 다르다.

이진수가 동일하다 → 주소: 몇번 페이지인지 알아야 한다.
→ 계산 방법: 내 주소 / 페이지 크기

Compile 을 할 때, Relative Address 를 이용하면 0번지를 기준으로 Compile 하면 된다.
그런데, Logical Address 를 사용하려면 Page 번호와 offset 으로 표현해야 한다.
Relative Address Compile 하던 Compiler 를 Logical Address 를 기준으로 Compile 하는 Compiler 로 바꾸려면, 어떤 계산을 추가로 해야할까?
⇒ 추가로 아무것도 안해도 된다.
⇒ 2진수는 동일하다. 내가 어떤 주소를 줬을 때 이게 어떤 페이지인지 알아야 한다. 몇 번 페이지인지 알려면, 내 주소를 페이지 크기로 나누어야 한다.

---

Paging

위의 예시에는 페이지 하나당 1K이므로, 1024줄 씩 존재한다.
위의 예시에서 Physical Address 에서

• frame# = 6
  (현재 frame 앞에 1024*6 줄의 코드가 존재한다. 6번째 frame 에 위치한다.)
• offset = 476

Logical Address 에서 Page 번호는 Process Page Table 을 통해 Page Frame 번호로 바뀌게 되고,
이렇게 얻게 된 Page Frame 번호와 Logical Address 에서 얻은 offset 으로 physical Address 를 얻는 relocation 작업을 진행한다.

내가 어떠한 Page Frame 으로 들어가든지, offset 의 변화는 없다.

2진수 계산

• 곱하기 2 → 왼쪽으로 한칸 움직인다.
• 나누기 2 → 오른쪽으로 한칸 움직인다.

⇒ 2^10 → 왼쪽으로 10칸 움직인 것
⇒ 6*2*10 = 000110 0000000000
⇒ + 478(offset) ⇒ 000110 0111011110 = Physical Address