[OS 기초] Segmentation and Paging

# Segmentation

# Paging

# Paged Segmentation

# Enhancing Mechanisms

# Case Studies

# Conclusion

# Segmentation

: 과거, 한 job이 하나의 Segment를 받아서 multi-programming을 수행하여 프로세스간 sharing이 원활하지 못했기 때문에, 한 process에 여러개의 segment를 부여하게 됨

- 하나의 User Process의 Memory Section들이 하나의 Memory Segment를 할당받는다면,

1. 두 User Process가 동일한 코드(Text Segment)를 공유하기 어려움

2. 각 Memory Section들에게 다른 Read/Write 속성을 설정하기가 어려움

=> Read, Read-only, Read/Write 타입에 따른 메모리 영역의 구분하기로 함. (Memory Segmentation)

- 각 Segment마다 Bound Register와 Base Register를 별도로 유지해야할 필요가 생김 

=> Address Transration Logic이 복잡해져야함

=> 하드웨어적인 logic 구현의 두가지 방법

1. 과거의 Intel Process Archictecture

: 프로세스당 할당할 Segment의 수를 미리 고정 (4개의 세그먼트만 할당하겠다)

: code segment 처리시에는 code segment의 base address틑 특정 register로 맵핑, 

data segment 처리시에는 data segment의 base address를 특정 regster로 매핑,

(하으웨어적으로 segment base address + offset)

=> 별도의 Segment Address Register들을 별도로 가짐

2. 별도의  register를 할당하지 않고 Main Memory에 Segment의 base/bound register의 pair들을 테이블형태로 기록 (더 일반적인 방법)

=> 다소 많이 복잡함

: segment가 하나만 필요하던 때에는 base/bound register가 하나의 pair만 필요했지만, 여러개의 segment가 사용되면 segment마다 pair가 각각 필요하게 되며,

해당 pair들을 관리하기 위해 table이 필요하게 됨. 

: table은 physical memory에 직접 access하는 unmapped된 공간에 저장됨

# Computer System에서 사용하는 Address

--------------------------------------------------------------------------------

CPU         =>                 MMU                 =>             Physical Memory

logical address                    physical address

--------------------------------------------------------------------------------

* MMU : Memory Management Unit, CPU가 Physical Memory에 접근하는 것을 관리하는 하드웨어 장치

- table lookup을 통해 segment의 base register를 얻고, base register 더한 후, compair 하는 기능

- table lookup을 위해 메인메모리에 접근하는 기능

1. logical address(virtual address)

: CPU가 생성하는 Address, Compiler/Linker가 사용하는 address

2. physical address

: MMU가 변환시키는 Address

ex. 32bit Process - 메모리 공간 : 0 ~ 2^32-1

: 상위 2bit를 segment ID로 사용(segment table의 Index), 하위 30bit를 segment offset으로 사용

: code segment(ID : 00), data segment(ID : 01), stack segment(ID : 10), unused(ID : 11)

- Memory Sharing을 위해 Segment Table의 기본적인 정보

: Segment ID, Base Address(시작주소), Bound Address(크기), RW속성

(* Segment Table의 Base Address는 Physical Address)

- MMU의 입장에서 테이블에 접근하려면, segment의 index만 알아서는 안되고 해당 테이블의 시작 주소도 알아야함함

=>  Segment Table Base Resgiter(STBR)가 필요

각 프로세스는 자신만의 Segment table을 가져야하며, 

Process가 Context Switching이 되면, OS는 지금 들어오는 Process의 STBR정보를 MMU에 reloading 해야함

(context switching이 되면 table을 STBR값을 바꿔줘야함)

- 예제

<segment table>

--------------------------------------------

segment | Base        | Bounds        | RW        

--------------------------------------------

0            | 0x4000  | 0x6FF          | 10

1             | 0x0000 | 0x4FF         | 11

2            | 0x3000  | 0xFFF          | 11      

3            |                 |                     | 00

--------------------------------------------

<1. Logical Address "0x1600"의 Address Transration>

    0x1600

--------------------------------------------

    0x / 01(segment id) / 6 / 0 / 0

+  0x0000

--------------------------------------------

    0x600 (=>이 주소로 transration)

but, 해당 주소는 segment table에서 봤을때, 해당 segment의 id(01) 항목의 Bound Address의 범위(0x4FF)를 넘거가게 됨

=> Memory Fault가 발생 -> SW Interrupt 발생

<2. Logical Address "0x3002"의 Address Transration>

=> unused 항목을 가르키게되어 Memory Fault가 발생 -> SW Interrupt 발생

# Segmentation의 문제점

- Memory를 Access하기 위해 2번의 Memory Access가 필요

: MMU가 segment table의 entry를 가지고 오기 위해 access

: MMU에서 얻은 Physical Address의 access

- Segment가 Main Memory에 많이 존재하면 fragmentation이 발생

- Function Call의 depth가 깊어지면, 주어진 Stack Segment의 크기보다 stack이 overflow 될 수 있음

=>에러로 처리하거나 OS가 stack segment의 사이즈를 늘려줄 수 있음. 

- 공간이 남는다면 바로 할당해줌

- 모자르다면, disk로의 swapping을 수행

* Fragmentation이 발생하는 원인

: Memory Allocation Request의 사이즈가 항상 다르기 때문

: request되는 메모리공간 전체를 physical memory 공간에서 연속적인 공간을 할당해야함

=> 두가지를 배제하면 fragmentation 문제를 피할 수 있음

* Segmentation에서 fragmentation등의 문제가 생기게 됨(메모리 할당시 요구되는 사이즈가 모두 다르고, 물리 메모리에서 할당되는 공간이 연속적이여야 한다는 이유로)

=> 해당 부분을 해결하고자 paging 기법이 등장

- 메모리 할당의 단위를 고정시키고, 메모리 할당시 흩어진 메모리를 할당 받을 수 있도록 함

# Paging

: Memory Allocation을 Page라고하는 일정한 사이즈 단위로 수행하는 방법

* page와 frame

page : Logical address space를 일정한 크기로 나눈 Memory Block

frame : Phygical address space를 일정한 크키로 나눈 Memory Block, page의 크키와 같음

* Paging시에 Memory Allocation

1. logical/physical address space를 일정한 크키로 나누기

과거에는 0.5, 1, 2, 4K처럼 작은 단위로 나누었지만, 요즘은 Bus의 Bandwith의 크기나, memory의 크기가 커지므로 page의 크기도 커지는 추세임

: swapping을 염두하고 page크기를 정하였음. 즉, block 사이즈와 동일하게 page사이즈를 결정

2. Address Transration 

- page table을 이용하여  MMU가 수행

=> MMU가 상위 비트에서 page number 얻기(상위 비트 : page number, 하위 비트 : page offset)

- page number를 이용해 page table을 뒤져 page frame number를 얻어와야 함

=> MMU는 Page Table Base Register(PTBR)라고하는 Page Table의 시작주소를 저장하는 레지스터가 필요하게 됨

=> OS는 Context Switching이 발생할 때마다  PTBR을 새로운 Process의 PTBR의 값으로 바꿔주어야 함

* segmentation과의 차이

: segmentation은 실제 segment의 크기는 가변적이므로 bound register를 사용하여 관리하지만, 

paging은 동일한 사이즈를 가지고 작업을 하므로 fragmenation의 문제를 해결할 수 있음

but, internal fragmentation이 발생할 수 있음

* Paging의 장점

- fragmentation 해결

- Memory Allocation과 swapping이 용이함

* Paging의 단점

- Address reference 할때마다, 2번의 physical memory reference를 2번해야함

(page table에서 entry를 가지고 오기 위해서, 실제 데이터(인스트럭션)을 가지고 오기 위해서)

-  segmentation과 달리 page table의 크기가 기사급수적으로 방대해 질 수 있음

*page table entry (32bit 환경인 경우)

: physical address : 32bit의 주소에서에서 상위 비트(frame number), 하위 비트(속성)을 나누어 저장

* 예제 : 32bit 환경, 1KB pages 사용

- page table의 size ? 

--------------------------------------------

| page frame(22bit)                  | offset(10bit) |

--------------------------------------------

page의 갯수 : 2^22 * 4Bytes(1page마다 1word) = 16MB 

(상당히 큰 크기의 페이지 테이블이 필요해 메인 메모리가 부족하므로 디스크로의 swapping 과정이 필요함)

*참고. 운영체제의 메모리 주소 지정방식 -Segmenthttp://zkakira.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%EC%9D%98-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%A3%BC%EC%86%8C-%EC%A7%80%EC%A0%95%EB%B0%A9%EC%8B%9D-Segment