지밍이 블로그

http://learnbranch.urigit.com/?demo

http://rogerdudler.github.io/git-guide/index.ko.html

http://git-scm.com/book/ko/v1

git

Git은 커밋을 가능한 자유롭게 하고자하여 커밋할 때마다 디렉토리 전체를 복사하지 않음

각 저장소의 이전 버전과 다음 버전의 변경내역("delta")를 저장

대부분의 커밋이 그 커밋위의 부모 커밋을 가리키고 있게 됨

저장소 복제("clone")을 하려면, 모든 delta를 풀어야 함

=> " resolving deltas "

git commit

git branch 

: 하나의 커밋과 그 부모 커밋들을 포함하는 작업 내역

특정 커밋에 대한 reference로 branch를 많이 만들어도 메모리나 디스크 공간에 부담이 되지 않음.

작업내역을 쌓아놓기보다는 잦은 branch 수행으로 작은 단위로 나누는 것이 좋음

git branch newImage

git commit

 : 제어가 master에 있는 상태에서 commit을 수행하여 master branch가 수행됨

다시 돌아가서..

git checkout newImage; git commit

* checkout (이동)

git merge(합치기)

: 여러 브랜치에서 새로 개발한 내용을 합치는 작업

두 개의 부모를 가리키는 특별한 커밋을 만들어냄

=> 두 개의 부모를 가리킴? 한 부모의 모든 작업내역과 나머지 부모의 모든 작업내역, 

그리고 그 두 부모의 모든 부모들의 작업 내역을 포함한다는 의미

master가 제어를 가진 상태에서 

git merge bugFix master (bugFix에 master를 합쳐라/연결하라)

 : master가 두 부모가 있는 커밋을 가리키고 있음

여기서 master에 bugFix를 연결하라/합쳐라

git merge master bugFix

: 모든 커밋의 색이 같아졌으며, 이는 두 브랜치가 모두 저장소의 모든 작업을 포함하고 있음을 의미

bugFix가 이미 master의 부모쪽에 있었기 때문에, 

아주 간단하게 bugFix를 master가 붙어있는 커밋으로 이동시킬 수 있음

git branch bugFix

git checkout bugFix

git commit

git checkout master; git commit

git merge bugFix master

git rebase

: 브랜치끼리의 작업을 접목하는 두번째 방법으로, 기본적으로 커밋들을 모아서 복사한 뒤 다른 곳에 떨궈 놓는 것

커밋들의 흐름을 보기 좋게 한줄로 만들 수 있음. 커밋과 로그이력이 한결 깨끗해 짐

bufFix 브랜치에서의 작업을 master 브랜치 위로 직접 옮기기 (마치 순서대로 개발한 것 처럼)

bugFix가 선택된 상황에서, 

git rebase master

C3는 어딘가 그대로 남아있고 복사본이 생기게 됨

이때 master branch와의 병합을 원하므로, master로 이동 후 

git rebase bugFix

master가 bugFix의 부모로 위치해 있었기 때문에, 더 앞쪽의 커밋을 가리키게만 바꿔주면 손쉽게 위처럼 설정이 가능

git branch bugFix

git checkout bugFix; git commit

git checkout master; git commit

git checkout bugFix

git rebase master

git 작업돌리기

- 개별 파일이나 묶음을 스테이징하기

- 실제 변경을 복구

변경내용 되돌리기

git reset

git revert

git reset은 이전 커밋을 가리키도록 하여 작업을 되돌리는 방법으로 히스토리 변경이라고도 함

git reset HEAD~1

히스토리를 변경하는 git reset은 각자 작업하는 로컬 브랜치에서는 유용하지만,

여러사람이 공유하는 리모트 브랜치에는 적합하지 않음

변경분을 되돌리고, 되돌린 내용을 다른 사람과 공유하는 작업이 필요함

git revert

- Open Firmware

The Flattened Device Tree is...

The Flattened Device Tree (FDT) is a data structure. Nothing more.

It describes a machine hardware configuration. It is derived from the device tree format used by Open Firmware. The format is expressive and able to describe most board design aspects including:

• the number and type of CPUs,
• base addresses and size of RAM,
• busses and bridges,
• peripheral device connections, and
• interrupt controllers and IRQ line connections.

Just like initrd images, an FDT image can either be statically linked into the kernel or passed to the kernel at boot time.

(출처. http://elinux.org/Device_Tree)

참고. http://blog.dasomoli.org/491

# S5FS

- System V File System 

- 하나의 볼륨(하나의 disk drive, 하나의 partition)당 하나의 파일시스템을 갖음

- 하나의 파일시스템은 Stand alone 시스템 : 파일에 대한 모든 컨텐츠와 정보들이 하나의 볼륨안에 저장이 됨

-  하나의 partition에 존재하는 block의 크기는 512 bytes (512, 1024, 2048)

- Sector들의 linear array = block의 linear array

- Boot Area : 0번째 block에 위치하며, Boot Program을 저장하고 있음.

Boot Area에서 Boot Program을 메모리로 로드하여 하드웨어 디바이스를 부팅시킴

- Super Block : 볼륨에 대한 파일시스템의 모든 메타데이터.

- inode list 

=> 전통적인 초창기 모델이므로 성능과 안정상에 문제를 가지고 있음

- 파일의 inode와 data block간의 물리적인 거리가 멀기 때문에 파일에 접근 시 과도한 Seek Operation이 발생

- Data Block의 할당/해제를 반복할수록 free block이 산재하게 되어 sequential block을 읽을 때 과도한 Seek Operation이 발생

- super block이 한곳에만 저장되어 있으므로 손상될 경우 파일시스템을 사용할 수 없음

- 컴퓨터 시스템에서 빈번하게 사용하는 operation에 최적화 되어있지 않음. 중구난방으로 흩어져 있음

# FFS

- UFS : Unix File System

- self-contained file system

-  cylinder group이라는 개념을 도입

: 인접한 cylinder를 묶어서 그룹화, 지역적으로 비슷한 곳에 있는 정보는 같은 cylinder group에 저장

- cylinder group마다 super block을 가짐(super block을 여러개 두어 recoverry를 도모)

- block안에 fragment라는 더 작은 단위를 도입. fragment단위로 allocation

- 하나의 cylinder group에 저장하기 힘든 사이즈가 큰 파일들은 인전 cylinder group으로 넘어감. (48KB 이상이 되면)

<장점>

- seek optimization.  적절한 spreading으로 동일한 파일의 Block들이 멀리 떨어져 저장되는 것을 방지

- lotational Delay optimization.

: seek operation에서 sector를 읽으려면 disk driver에서 read request 만들어서 날려야 할 때, 2 sector가 지나가는 시간이 걸린다고 가정.

0번 sector를 읽고 1번 sector를 읽어야 할 때, 한번 resquest를 하면 2개의 sector가 지나가면 1번 sector를 읽기위해서는 다시 한바퀴를 돌아야 함.

=> 이런 문제를 방지하기 위해 lotational delay를 계산하여 sector에 저장하도록 함

- long file name의 지원. 256characters.

- symbolic links의 도입

- Disk quota 도입

<한계>

- sequential read의 한계

- crash recovery가 느려지는 문제 발생. disk storage의 block size가 굉장히 빠르게 증가. 

=> 적절한 부팅 시스템을 무시하고 시스템을 power off하면 rebooting할 때 파일시스템의 inconsistency를 확인.

=> "fsck", file system check라는 command를 수행하는데 굉장한 시간이 걸림

=> log structured file system을 사용하게 됨

# LFS

: Log-structured File System 

> Crash recovery의 필요

- 성능향상을 위해 inode cache를 가지는 구조에서 문제가 발생하면 disk의 inode의 값과 메모리의 inode값이 일치하지 않게 될 수 있음

- disk에 대한 operation은 transaction과 같아 synchronous write를 수행하게 됨 

> fsck의 수행동작

- 시스템에 존재하는 inode들을 체크하여 used block들을 확인

- used block들의 구조에서 각각의 directory 별로 file contents를 모두 확인하여 파일의 inode를 확인

- inode indexdp mapping된 데이터가 제대로 있는지 확인. 찾을수 없는 파일이나 연결이 안된 디렉토리들... 

- lost + found directory에 보내기

> LFS 구현

- 새로 생성될, 새로 추가될 정보만 파일의 정보 뒤에 붙이게 됨

- log : Operations나 values, redo/undo log, 

- garbage collection : 어느 시점이 되어서 로그가 너무 방대해지면 sequential read operation이 굉장히 느려지게 됨

- group commit

- retrieval

# Disk Scheduling

- Request Queue : disk에 대한 I/O request를 저장하는 queue

- device drivers와 devices 사이에 request Queue가 위치

- device driver에 I/O Scheduler가 스케쥴링을 수행

- Request Ordering을 수행하여 시간을 줄임

FIFO/FCFS (x)

SSTF (x)

Scan like Elevator (x)    => 양방향에 위치한 애들만 너무 불리해

Circular Scan (o)

> Flash memory 등의 경우에는 disk보다 더 복잡한 스케쥴링이 필요하게 됨

: bus share, multi processor, 공정의 여러 제약 등 

# Files and Directories

# File System

# File Structures

# Disk Space Management

# Unix File System

# Disk Scheduling

# Conclusion

# File 

: 이름을 가지는 디스크에 저장되는 바이트의 집합

> Views 

- OS가 보는 File : Block Sequence. Disk는 Block Storage 이므로 Block 단위로 저장 (내부)

- User가 보는 File : Bytes Sequence  (외부)

=> OS의 File System은 User가 보는Bytes 단위를 시스템 OS가 보는 Block 단위로 mapping 해야 함

* Naming 

: Disk 상에 존재하는 File은 addressing할 수 있어야 하는 이유로 인해 외부적으로는 Text Name을 가져야 함. 내부적으로는 File Identify를 가져야 함.

(*OS는 Naming을 File 뿐만아니라 I/O Devices 에도 적용시킴)

* File Descriptors 

: 파일의 내용에 접근하기 위해 필요한 메타데이터들을 저장하는 자료구조. 

* Operations on Files

- create and delete files

- open files for reading and writing 

- seek within a file

- read from and write to a file

- close files 

- create directories to hold groups of files

- List the contents of a directory

- Removes files from a directory

# File Descriptors

- unix에서는 index node라고도 부름

- 파일의 메타데이터를 저장하는 자료구조

- 파일의 크기, 소유자, 소유 그룹, 액세스 타임, 접근 권한, ...

- inode : unix의 file system에서 파일에 대한 메타데이터를 저장하는 자료구조

- i-node의 index :  i-number, file descriptor의 ID. 

> FIle Descriptors의  저장

과거: array의 형태로 만들어 disk에 특정 block을 할당하여 저장.    

=> 과거 disk는 bad block이 많고 취약했기 때문에, single copy로는 데이터 보호를 제대로 할 수 없음

=> File Descriptor들을 디스크의 특정 영역에 모아두면 성능저하가 발생

: 디스크 스토리지 상에서 File Contents와 File Descriptors를 나누면 물리적인 거리가 멀기때문에 Seek Time이 커짐

현재 : data contents 근처로 file descriptors를 가까이 두어 분산시키거나, data recovery를 위해 data의 copies를 여러개로 만듬

-  in memory cache : 성능의 향상을 위해 File Descriptor의 복사본을 Main memory에 유지

=> 부작용이 생길 수 있음. File Desciptor의 값을 수정할 때, Disk와 Main Memory에저장된 File Descriptor의 값이 달라질 수 있음

- 과거, Main Memory의 Cache에 복사한 file descriptor의 값을 안전하게 Disk에 옮기지 않고 시스템을 종료하면,
    시스템 재부팅 시에 OS는 해당 내용을 Disk의 file descriptor의 내용을 재구성해야함.

but,  현재는 디스크의 용량이 굉장히 커져 복구하기가 어렵고, 재부팅이 시스템을 정상화 하게 하는 경우가 많아짐(스마트 폰...)

=> log structured file system으로 진화

# Directories

- bytes sequence

- File 및 sub directories를 가지고있는 entity

- 내부적으로 File과 동일하게 관리

- File과는 다르게 data content로 contains(text file name, descriptor index) 값을 가짐. 

=> file의 text name을 file id로 mapping하기 위한 기본 데이터

> Unix File System의 구조

- tree 구조

- root directory, 하위 디렉토리는 각 leaf가 root로 부터 unique

- root directory의 inode number : 2

* why? http://stackoverflow.com/questions/12768371/why-root-directory-is-always-stored-in-inode-number-two

- name parsing 

# 부가사항

> Working Directory : 현재 위치한 디렉터리

> Link : 선택적으로 필요에따라 back-door path를 지정하는 기능

* inode의 i-number 값은 system wide하게, unique 하게 부여하는 것이 아니라, 볼륨 단위로 부여를 함

- Symbolic Link : 링크시킬 파일의 full path 값을 새로 링크시켜줄 디렉터리에 복사

원본 파일 A에 대해 심볼릭 링크를 생성하면, A라는 가리키는 파일을 생성

( "symbolic_link_file_B -> original_file_A" )

원본파일 A를 삭제하면 A를 가리키던 심볼릭링크파일도 삭제 됨됨(수정도 마찬가지)

- Hard Link : 링크시킬 파일의 contains pair 값을 새로 링크시켜줄 디렉토리에 그대로 복사. 

원본 파일 A에 대해 하드링크를 생성하면, A라는 파일을 가리키는 "이름"을 하나 더 만듬.

즉, 둘 중 하나의 파일을 삭제하더라도 이름 뿐인 녀석을 삭제하였으므로 내용은 그래도 남게 됨. 한 녀석은 그대로 존재하게 됨

=> symbolic link가 더 유연함. i-node의 number는 볼륨 단위로만 unique 하므로 Hard Link에 사용하는 contains pair값은 system wide하게 unique하지 않음.

즉, Hard Link는 같은 볼륨내에서만 사용이 가능

=> symbolic Link는 full path를 가지고 구현하기 때문에 모든 link는 system wide하게 unique 함

즉, 다른 볼륨간에도 사용할 수 있음

# Big Picture

> File System 기능

1. logical file name(logical resource name)을 physical address로 변환하기 위해 naming 기능을 제공

2. 사용자의 데이터를 저장장치로부터 read/write 하는 기능을 제공

> Views on Files

- User

file name + byte offset

: file pointer로 offset을 움직이며 파일 읽기

* file 단위의 sequence of bytes

* 주요 file access 패턴

- sequention access : file pointer를 한 칸씩(bytes) 움직이면서 파일의 내용을 읽기

- random access : file pointer를 임의로 이동하면서 파일의 내용을 읽기

- Kernel 

ino + logical block number

* file안에 존재하는 sequence of block

* bytes단위가 아닌 block 단위로 내용을 읽기

* kernel의 file system은 밑에 device driver와 interface 해야 함

* file descriptor, = index node

- Device Driver

Physical block number

* disk volume 단위로 관리, sector들의 linear sequence

* volume : 단일 file system으로 관리되는 저장 장치 상의 영역

* sector들의 number

- Device

cylinder number

head number

sector number

* drive number 이미 minor number로 사용 중

> File System in the Kernel (linux case)

user space            : file I/O    (system call : create, read, write, open, I/O contol)

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

kernel space         : Virtual File System (VFS)  -> individual한 파일 시스템을 유니폼하게 사용자에게 제공하기 위해 필요

Individual Filesystems(EXT3, EXT4, JFFS2, VFAT, ...)

Buffer Cache(Page Cache) -> 최근 접근한 file의 Data Block의 내용을 Main Memory에 저장해 두는 공간으로 

디스크로 부터 한번 읽어온 파일의 내용에 다시 접근할 때, 빠른 속도를 제공함

(buffer cache도 swapping함. LRU같은 Policy를 적용)

I/O Schedulers

*Request Queue / Response Queue

Block Drivers   ,     Block Driver(FTL)

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

Storage Media     : Disk ...... Flash

# File Structures

- Sequential access. ex. 방대한 코드를 컴파일 할 때,

- Random access.  ex. 데이터베이스에서 특정 데이터를 읽을 때, demanding paging에서 특정 page를 읽을 때, 

- keyed access. ex. 특정 key로 데이터를 읽을 때, (OS에서는 처리하지 않음)

* 과거 디스크는 fragmentation의 문제가 있음

=>  비연속적인 block단위로 allcation을 수행하여 fragmentation의 문제를 해결

1. Linked File 구조

: 해당 파일 디스크리터에 기록된 파일의 첫번째 블록의 주소를 통하여 파일에 접근

: fragmentation의 문제는 해결

: sequential access는 문제가 없으나, random access의 경우에는 seek time이 굉장히 오래 걸리게 됨

: 1970년대..

2. Indexed File 구조

: Unix의 기본 file 구조

: file descriptor에 파일이 가지고있는 block들에 대한 포인터를 index array로 저장

: sequential access, random access 둘다 용이함

: data block들은 file system의 sector array 중 임의의 block을 할당. 각 file의 file descriptor들이 해당 block들을 가리키는 구조

: file descriptor는 일정한 크기를 갖는 descriptor들의 array로 구성. 

=> 그안에 넣을수 있는 index의 갯수가 제한. 한 파일의 크기는 index의 갯수만큼 제한된다는 단점!

=> double indirect block 구조를 사용하여 큰 사이즈의 파일도 수용할 수 있음

 (but, 이중으로 처리하는 이러한 구조는 기존에 비해 데이터를 더 액세스해야하므로 seek time이 증가)

# Related Mechanisms

1. Block buffer cache

2. bit map operation  : 디스크 블락을 할당할 때, 꼭 sequential한 위치에 할당하지 않아도 되지만, seek time을 줄이기 위해 같은 실린더안에 있는 block을 할당하거나 하는 등의 인접한 위치의 block을 할당하는 방법

=>  OS의 File System에선 비어있는 연속된 block의 위치를 bit map을 통해서 알 수 있음

=> block들에게 1bit씩을 할당하여 1이면 이미 할당됨을, 0이면 할당되지 않고 비어있음을 나타내게 함함

=> 소프트웨어적으로도 구현이 가능하나 대부분의 마이크로 프로세서가 해당 기능을 제공

* Bit Map을 사용한 디스크의 free block 관리

: 각 bit가 디스크의 block이 사용 중인지 아닌지를 나타내는 Array. 

 HW/SW String Search 기법을 사용해 연속적인 사용 가능한 block을 쉽게 찾을 수 있음

> File의 구조를 결정하는 요소

: sequention access, random access를 효율적으로 지원해야함

작은 file, 큰 file 모두 효율적으로 지원해야 함

> must have items

1. Naming

2. Protection

3. Reliability

4. Disk Space Management 

# Disk Space Management

: File이 생성되거나 확장될 때, 어떻게 disk sector들을 file에 할당해 줄것인가를 결정

- 오버헤드가 적게

- 파일에 빠른 액세스가 가능하게 등등

- 파일의 각 block들

- matadata : user에게는 보이지는 않지만 커널이 각 파일별로 관리. 

in-memory cache를 유지하고, system이 shutdown될 때는 consistency를 잘 유지해야 함

- crash policies

> Disk space allocation policies

1. contiguous allocation

2. Block-based allocation

3. Extent-based allocation : block들을 그룹으로 묶고 각 그룹에 semantics를 부여함으로써 최적화를 달성하는 정책

=> block 단위로 allocation을 하면 sequential read를 할 때 seek가 많이 발생하므로 큰 단위로 할당해야하는 필요가 있음

# Unix File Systems

- System V file system : s5fs

: 완전 기본적 전통적인 파일시스템

- Berkeley fast file system (FFS) - often called UFS, 1980 년대 s5fs를 개선

- Sun's network file system (NFS) - 분산 operation과 file system을 접목

- Sun's virtual file system (VFS) - 다양한 파일시스템을 지원하기 위한

- Log-structured file system (LFS) 

# I/O Hardware

# Device Drivers

# Colision

# I/O Hardware

CPU, Memory, HardDisk, Network card, ...

<Bus>

- System Bus, I/O Bus, 

- Address Bus, Data Bus, Control Bus 

- ISA, PCI, EISA, SCSI ...

> I/O Device 

- Controller, logic

- Register set

> I/O Device 내부의 Registers

- Status Register : 장치의 상태를 보여주는 Register

- Control Register : 장치의 동작을 결정하는 Register

- Data Register : 입출력할 데이터를 잠시 보관하는 Register

- Instruction Register ...

> I/O Device의 Register에 접근하는 두가지 방법

- Memory-Mapped I/O : 별도의 I/O address space를 갖지 않고, Physical address space의 일부를 할당하여 사용

* register를 access 하기위해 load/store 명령어를 사용 (모토롤라...),

- Port-Mapped I/O : 메모리의 주소와는 다른 방식의 주소를 할당하여 사용

* register를 access 하기위해 in/out 명령어를 사용 (Intel processor...), 

> Device Control

- device control = device의 register들을 프로그래밍

- OS는 I/O Bus의 address line에 특정 register의 address를 보낸 후 read/write같은 명령을 보내 수행하게 함

# I/O Devices의 분류

: unix OS는 굉장히 단순화 시키려고 노력하였으며 이런 환경에서 I/O Devices를 특성에따라 모델을 나누게 됨

- Character Devices : 입출력을 Character 단위로 수행. mouse, terminal, ...

- Block Devices : 입출력을 block이라는 임의의 단위로 수행. Disk Drive, Flash Drive, ...

- Network Devices : NIC, ...

> Character Devies

* ex. 

<Mouse driver의 역할 요약>

- Mouse Interrupt 발생 시, Mouse의 Data Register에서 값을 읽어오는 역할

- interrupt를 Event로 바꾸어 주는 역할

<Keyboard Driver의 역할>

- 키보드로부터 들오오는 각 캐릭터들을 Line buffer에게 순서대로 저장

- End-of-Line Character가 들어오면 전체 Line Buffer에 있는 데이터를  OS에게 전달

> Block Devices

- spindle

- arm assembly, arm, read-write head

- Track : 한 디스크 표면에서 스핀들로부터의 거리가 동일한 환형의 저장 공간

- cylinder : 여러장의 디스크를 수직으로 쌓여있는 동일한 반지름의 Track들의 집합

* cylinder 단위의 데이터 접근이 중요한 이유 (왜 cylinder라는 개념이 있는건가?)

: Arm Assembly가 고정된 상태에서 여러 platter에 걸쳐있는 한, 실린더의 트랙들을 동시에 읽을 수 있기 때문

- sector : 각각의 track을 분할하는 디스크 read/write 단위의 영역

> Disk Operation

* Sector : 디스크를 읽을 때 data transfer가 일어나는 최소 unit.

Sector에 접근하기 : cylinder number, track number in the cylinder, sector number in the cylinder

1. read/write head 선택

2. "seek", arm assembly를 해당 cylinder로 이동. (Move heads to the correct track)

* seek time : arm을 목표한 지점(해당 cyliner)까지 이동하는데 걸리는 시간

3. 해당 sector가 돌아올때까지 기다림 (spindle의 회전수에 비례, RPM-Rotation Per Minute)

* Rotational Delay : 디스크가 회전하여 목표한 지점(해당 섹터)이 head에 도착하는 시간

> Disk Performance

- seek time : 0-50 ms (avg 10-20 ms)

- rotational delay : 0-16ms

- typical drive spins at 3600-5400 RPM

> Flash Drive

- NAND flash memory : RAM과 Access pattern이 굉장히 다름. data tranper가 bytes단위가 아닌 block 단위로 일어남

- Page : Read/Write를 수행할 때 대상이되는 Data block. 2KB, 4KB, 8KB

* Page의 일부분은 Data를 저장하는 공간과 Spare Area라는 패리티, 에러처리 등 부수적인 정보 등을 저장하는 공간으로 나뉨

- Block : 64 pages, 128 pages

* Flash Memory > Blocks in a Flash Memory > pages in a Block > Spare areas in a page

* Flash Operations

- read : 하나의 페이지를 통째로 읽어옴

- write/program : flash의 해당 영역을 굽기

- erase : block 지우기. flash는 rom이므로 rewrite할 수 없음. 우선 지우고 다시 써야함.

<특성, 제약사항>

* Erase-before-write : NAND Flash 메모리는 데이터의 덮어쓰기가 불가능 하기 때문에 먼저 Erase로 초기화 한 후 write 해야 함.

* Worn-out : Erase 가능한 횟수가 제한적임

* Wear-leveling : NAND Flash의 한 영역에 Erase가 집중되어 worn-out이 발생하는 것을 막기위해 전체 영역을 고루 사용하도록 조절하는 기술

* read/write의 단위는 page, erase의 단위는  block

- Flash Memory를 Storage로 사용해 file system 구성하려면, Erase-before-write라는 제약조건 때문에 

반드시 Log Structure Architecture가 필요함

> Page단위로 write를 수행하다가 Erase를 수행할 때, 단위가 block으로 page보다 크므로 지우려는 page 외에도 다른 page의 데이터가 모두 지워짐

> 로그를 남겨 관리를 해야함. page remapping after update.

=> Log-structured file system

# Device Drivers

:  I/O Devices의 Control. 다른 프로그램들이 어떤 하드웨어 디바이스를 잘 사용할 수 있게 컨트롤 해주는 컴퓨터 프로그램

- 하드웨어 적인 측면을 관리하며, 기능을 사용자에게 추상화 시켜 사용하기 편하게 도와주는 역할을 함

- Application과 Device, OS와 Device  사이에 위치하며, User들이 Device를 사용하기위해 함수들을 제공

* SW System의 구성

- 정적인 구성요소 : structure(process)

- 동적인 구성요소 : behavior(program)

- Device Drives의 요소

정적 구성요소 : Device Drives를 User Program이 사용하기 위해 호출하는 APIs, Operations...

동적 구성요소 : Interrupt Service Routin. 

=> 즉, Device Drives는 라이브러리이며 어떤 구성요소는 Interrupt에 의해 호출되며, 어떤 구성요소는 User Programs에 의해 호출됨

- UNIX 계열의 Device Drivers

* Unix 

- 시스템의 단순화, portability 높이기.

- portability를 높이기
 : machine dependent 한 부분을 정형화 시켜서 정리해야 함

 : micro processor에 micro architecture specipy한 부분(MMU, context)이나, Memory layout, system bus architecture, Device관련 부분 들

* Unix Device Drivers의 대표적인 5가지 함수

- Open : 디바이스를 initialization. OS관점에서 레지스터와 디바이스 드라이버가 필요한 데이터 스트럭쳐를 잡아주는 역할 등

- Close : release

- read/write

- I/O CTL : I/O Contol

* Type of Unix/Linux Device

- Character Devices : data transfer unit이 캐릭터 단위. 시퀀셜 엑세스에 사용

일반적으로 사람과 상호작용 하므로 보통 slow device.

- Block Devices : 데이터 트랜스퍼 유닛이 블럭단위. 랜덤 엑세스에 사용

* block buffer cache : Large scale의 볼륨을 단위로 high speed가 필요함. 캐시로 CPU에 비해 상대적으로 속도가 느린 block device의 성능을 보완한 것.

- Network Devices

> File System의 역할

1. 디스크에에 있는 데이터를 읽거나 쓸 쑤 있는 여러 기능을 제공

2. File이나 Device 같은 시스템에 존재하는 자원에게 Name Space(simbolic name)를 제공(Unix/Linux에서는 path와 같은 형태..)

> Device File : 일종의 스페셜 파일을 생성하여 파일과 디바이스를 연결시키기

- 일반 데이터 파일로 관리

- /dev 밑에 file의 형태로 존재

- 하나의 디바이스에 여러 이름의 파일을 붙일 수 있음

ex. /dev/psaux, /deb/psmouse = serial mouse

* File의 데이터

- Real Data

- Metadata : file의 특성을 표현하는 부가적인 데이터

: 생성일, 수정일, 엑세스 권한 등

- Device File의 metadata

- Device Type : block, charactor

- Major Number : 어떤 타입의 디바이스인지 나타내는 필드. tty, 

- Minor Number : 대상이 되는 디바이스를 구별하기 위해 디바이스 드라이버에게로 보내는 argument. (Kernel don't care)

# Trashing 

> Trashing이 발생하는 과정

1. 시스템에 충분히 많은 Process가 동작 중

2. 동작중인 프로세스가 요구하는 메모리가 가용한 물리 메모리보다 많아서 Page Fault 발생

3. page fault를 처리하는 동안 프로세스는 block 당하고 CPU Utilization이 낮아짐

4. CPU Scheduler는 시스템이 한가한 것으로 판단하고 더 많은 프로세스를 실행하려고 함

5. Memory는 점점 부족하게 됨

=> Trashing은 모든 프로세스가 하나의 physical memory pool을 공유(global page replacement)하기 떄문에 발생하게 됨 

=> Local Allocation(per-process, per-job)을 통해 Thrashing을 해결할 수 있는가?

: 해결할 수 없음. 특정 프로세스가 과도하게 메모리를 사용하여 다른 프로세스가 영향을 받는 현상은 막을 수 없음.

하지만, 시스템의 메모리가 부족한 상황인 경우 어떤 프로세스가 충분한 메모리를 확보하고 있더라도 메모리가 부족한 다른 프로세스에 의해 페이지 폴트 처리가 지연됨에 따라라 성능이 급격히 나빠지는 현상이 발생

> Trashing이 발생하는 본질적인 이유?

현재 active하게 사용되는 메모리보다, physical memory가 부족하기 때문에 발생

* 결국 해결법은, 불필요한 프로세스를 suspend(swapping)나 terminate시키기. (degree of multiprogramming을 낮추기)

* Smartphone 처럼 Swap Device가 없는 경우 많은 프로세스로 인해 메모리가 부족하게된다면?

: suspend(swapping)을 할 수 없으므로, Android의 Low Memory Killer등을 사용하여 프로세스를 Terminate.

* Trashing을 체계적으로 극복하는 방법은?!

# Working Set

: 어느 시점에 특정 프로세스가 Access하는 page들의 집합(프로세스의 locality)

- 1960년대, Peter Demming이라는 사람이 생각해낸 아이디어

- 특정 프로세스이 수행되는 전체 life time동안 working set은 변함 (sub-routin call, jump)

=> locality도 변하게 됨

* Prepaging(Prefetching) : 실제 page 요청이 있기 전에 향후 Access 될 것으로 예상되는 페이지를 미리 메모리에 로드하는 것

> Working Set을 이용한 Prepaging

* Longterm Scheduler : degree of multiprogramming을 낮추기 위해 프로세스를 계속 모니터링하여 메모리의 사용이 없는 프로세스를 선정하는 스케줄러

  Shorterm Scheduler : 다음에 돌아야하는 프로세스를 선정하는 스케줄러

- How ?? Working Set Parameter - 현재부터 과거동안 access된 page 들

- working set param들의 갯수가 너무 적으면 충분한 working set을 확보하기 어렵고,

working set의 windows 사이즈가 너무 크면 불필요한 page들도 포함하게 됨

=> 적합한 working set을 찾아내야 하는 필요가 있음

> Working Set의 단위

- 시간? 어떤 프로세스가 항상 동작하는 것이 아니므로 시간으로 단위를 잡기는 어려움

-  Page Reference 패턴? Page Reference 횟수?  어떤 페이지는 여러 프로세스에서 엑세스 되므로 불필요하게 Working Set으로 잡힐 수 있음

=> working set을 잡는건 어려운 일임

# Working Set의 approximation

- 가정 : 현재 수행중인 프로세스에서 Trashing이 일어나지 않고 잘 수행중이면, 현재 할당된 page들은 그 프로세스의 working set일 가능성이 높음

-  OS는 프로세스의 Page fault를 가지고 현재 프로세스의 수행 상태를 알 수 있음

=> key point !!

> Resident Set

: 어떤 프로세스가 어느 시점에 메인메모리에 가지고있는 페이지 들

* Resident Set이 의미를 가지려면!?

- 프로세스가 fork되는 시점에 프로세스에서 일정한 양의 page frame을 allocation 

- system wide하게 upper bound를 설정.  page fault가 upper bound를 넘어서 발생된다면 해당 프로세스에게 좀 더 많은 frame을 할당(high watermark)

- low bound를 설정. page fault가 low bound보다 낮게 발생된다면 working set windows가 불필요하게 많이 할당되었다는 의미. (low watermark)

<Page Fault 발생 횟수에 따른 운영체제의 Memory 할당 정책>

- Threshold 보다 많이 발생하는 경우 : 해당 프로세스에게 더 많은 메모리를 할당

- Threshold 보다 적게 발생하는 경우 : 해당 프로세스에게 할당된 메모리를 회수

# Memory Management의 Trends

<이슈>

1. Physical Memory의 크기가 커짐

- Page Frame이 넉넉해짐

- Page replacement의 중요도가 줄어들고

- 하드웨어적 서포트가 줄고, 소프트웨어적으로 처리하게 됨

- page의 크기가 커지며,  커버하는 instruction의 크기도 늘어나며 hit rate이 높아지게 됨

2. Virtual Memory의 크기가 커짐

- 64bits with 4K page

-  Large Virtual Memory Management의 중요도가 높아짐

3. Memory Management가 OS의 다른 요소들과 결합

- 과거에 없던 색다른 서비스를 제공 : File System과 접목...

4. Large Page Table의 Handling

- 문제 :

1. page table을 유지하기위해 필요한 공간이 너무 큼

2. page table의 물리 메모리에 연속적인 공간에 존재해야 함 

=> 조각의 단위로 쪼개어 관리하는 기술이 필요

<해결방법>

1. Hierarchical page table ; table space를 줄이진 못하지만 , physical memory상에 조각으로 나누어 적재될 수 있도록

<Two-Level Page Table>

- 32bit 환경에서,

Page Number(22bits), offset(10bits)

=> Page Number = First Level Index(14bits) + Second Level Index(8bits)

* First Level Index == Outer Level Index

- Page Table Entry : 1 word size, 4bytes

- Page Table Size : 2^22 X 4 bytes = 16MB

- 한 page에 존재하는 Page Table Entry의 수 : 256 entries (8 bit)

- 한 Page Table에 존재하는 Page들의 수 : 16K (14 bit)

- First Level Page Table의 크기 : 16K x 4bytes = 64KB

- 공간상의 문제에서 장점을 보이나, 속도면에서의 단점이 있음

2. Hashed page table : page table space의 사이즈를 엄청나게 줄일수 있도록

: hashing기법을 사용하여 page table을 구성

page number를 hash table에서 얻어오기.

3. Inverted page table : page table space의 사이즈를 엄청나게 줄일수 있도록

: 모든 user Process는 독립적인 공간을 같기 떄문에 관리를 위해 별도로 큰 page table을 갖음

- address space 만큼 page table을 갖는게아니라 physical memory만큼 page table을 갖자.

* virtual address space사이즈가 아닌, 실제 시스템에 존재하는 page frame의 갯수만큼 page table을 갖는다.

# Page Replacement Policies

> Page replacement Algorithms

1. Random - 주로 하드웨어 적으로 구현할 때 사용

2. FIFO

- Linked List로 구현

3. Optimal - 가장 먼 미래까지 전혀 사용되지 않을 페이지를 교체. 

* Reference String : Sequenced of Referenced Pages. 어떤 프로세스가 수행하는데 프로세스가 ref했던 시퀀스.

4. LRU - Least Recently Used. 최근에 가장 사용되지 않은 페이지들을 교체. 

Temporal Locality에 기반한 Page Replacement 정책.

Timestamp 사용하여 page frame 하나하나마다 count 정보를 저장해야 하지만 굉장히 오버헤드 크기때문에 Counter 대신 Reference Bit를 사용하기로 함

<Memory Management에서 사용되는 flag bit 종류>

* Reference Bit : Use Bit, Main Memory에 로드된 페이지가 엑세스 되면 Set되는 Bit Flag.

* Resident Bit : 내가 사용려는 page가 1이면 현재 Ram에 존재하고 있을때, 0이면 swap device에 있을 때

* Dirty Bit

> Belay's anomaly : FIFO의 문제점을 명시. 메모리를 늘렸음에도 불구하고 페이지폴트가 더 많이 발생하는 현상

* Stack Algorithm : N개의 Frame으로 구성된 메모리에 로드된 Page들이 항상 N+1개의 Frame으로 구성된 메모리에 로드된 page들의 부분집합이 되는 알고리즘.

절대 Belay's anomaly를 나타나지 않음

ex. LRU ...

(이름이 stack algorithm인 이유는 항상 나가고들어오는 부분이 stack처럼 어느 부분에서만 일어나기 때문에 stack에 비유)

* Page Replacement를 수행할 때, 미래를 예측하여 수행하면 굉장히 효율적일 것이나, 현실적으로는 불가능.

하지만 프로그램은 Locality라는 속성을 가지므로 과거를 통해 미래를 어느정도 예측할 수 있음.

=> LRU algorithm

> LRU

1. reference bits algorithm(8bits)

: reference bits를 하나 두고 8개의 8bits 짜리 register를 붙인 후, 일정한 간격으로 reference bits을 shift right하여 가장 사용이 안된 것을 고름. 

=>  사용여부 체크(00000000이 0이므로 가장 작겠지)

액세스의 여부만으로는 정확한 우선순위를 정하기 어렵기 떄문에, OS는 시간을 일정 간격으로 시간을 나눈 후 해당 interval에서 사용이 되었는지의 여부를 체크

2. Clock Algorithm

: linear한 frame들을 clock처럼 wrap around 형태로 연결 시킨 후, 현재 가리키고있는 임의의 페이지를 가리키는 clock hand로 페이지를 교체할 시점엔 어느페이지를 선택할 지 결정해야 함

* Clock Algorithm에서 교체할 Page를 선택하는 방법 

: Clock Hand가 가리키는 page의 reference bit이 1인경우, 0으로 바꾸고 Clock Hand가 다음 page를 가리키도록 함(최근에 사용되었다는 의미이므로 skip). 이 과정을 반복하다가 reference bit이 0인 page를 만나면 최근에 사용되지 않은 page이므로 해당 page를 교체체.

(UNIX OS 에서 많이 사용되는 알고리즘)

- 모든 reference bit이 1이면 모든 page가 reference 되고 있다는 의미이므로 main memory가 현재 overcommit되고 있다는 의미이며, 모든 페이지가 빈번하게 access되고 있으며 skip구간이 굉장히 많이 되므로 clock hand도 빠르게 회전하게 됨

=> clock algorithm은 LRU algorithm을 기반으로 업그레이드 한 것이지만, 메모리 Over Commit이 일어나게되면 FIFO algorithm으로 전환됨

3. Enhanced clock algorithm

- reference 안됐고 clean한 page

- reference 안됐고 dirty한 page

- reference 됐고 clean한 page

- reference 됐고 dirty한 page

* 기본적으로 clean한 페이지를 dirty한 페이지보다 우선적으로 처리한다. clean하면 swapping시 따로 지워주지 않아도 되므로 비교적 처리가 쉬움.

=> but, clean page라고해서 무조건 내보내는게 좋은 건 아니다. code page일 수 있다?

* Micro Architecture의 MMU기능의 단순화로 reference bit을 지원하지 않는다면?

> FIFO 사용

> Frame Buffering : 단순 FIFO를 기반으로 빈번하게 사용되는 frame을 다이나믹하게 관리하여 유용하게 사용하기 위해 free list를 사용

- used page frame list (linked list)

- free page frame list (linked list)

* Optimization : clean page와 dirty page가 섞여있는 free list에서, swap device와 DMA Controller가 IDLE 하다면, dirty page를 Swap-out하여 clean하게 해주기!

# Page Replacement Style

: allocation style

1. Global replacement

: 시스템 단위로 replacement

- 단점 : 메모리를 지나치게 사용하는 동작이 있다면 메모리를 효율적으로 사용하기 어렵다.

- 장점 : 메모리를 모두 고르게 분배하여 사용하면 메모리를 낭비없이 효율적으로 사용할 수 있다.

2. Per-process replacement

3. Per-job replacement(per-user replacement)

* 2,3번의 경우에는 Process나 Job단위로 나누어 replacement되므로 

간섭을 받지 않는다는 장점이 있지만, 어떤 부분은 메모리가 모자를수도, 어떤 부분은 메모리가 남아돌수도 있는 단점이 나타날 수 있음.

=> 할당되는 메모리를 dynamic하게 조절해 줄 수 있는 기능이 추가적으로 필요

: 단위시간동안 Page Fault횟수를 확인하여 메모리가 남는지 부족한지를 판단하여 이용한다.

# Demanding Paging

: 메모리 관리 매커니즘(MMU 매커니즘)을 사용해서 여러 프로세스가 시스템 메모리를 효율적으로 공유할 수 있도록 하는 기술

: 어떤 프로세스가 수행될 때, 집중되는 page들을 필요할 때 읽어들이기.

: 페이지가 요구될 때, 메모리에 불러오는 정책

* Principle of Locality(Locality of Reference)

: 프로그램이 가장 최근에 접근했던 데이터를 다시 접근하거나(Temporal Locality), 

최근에 참조했던 데이터 근처의 주소를 참조하는 경향이 있음(Spatial Locality)

* 90/10 Rule

: 불과 10%의 코드가 프로그램 총 수행시간의 90%를 차지함. (loop)

* Swap Device

: Physical Memory에 저장되지 못한 Page들을 저장하는 디스크의 공간

: 저장 단위인 file은 I/O시에 OS의 여러 기능이 동작해야하므로 굉장히 느리기 떄문에 File과 별도로 direct access가 가능한 low disk block.

: swap device가 가득찬 경우는 file을 swap 영역으로 사용할 수 있음

> Demand Paging의 Policy

: Physical Memory와 Swap Device 사이의 데이터 전송을 최소한으로 발생하도록 함

* Memory Access Latency

레지스터(1 사이클) < L1 캐시(수 사이클) < L2 캐시(수십 사이클) < Main Memory(수백 사이클) < Disk (수백만 사이클)

* Thrashing 

: 프로세스들이 사용하는 페이지들의 크기보다 사용이 가능한 물리 메모리의 크기가 작을 때, 사용하려고 swap-in하는 페이지들에 의해 앞으로 사용할 페이지가 swap-out되면서 반복적으로 Page Fault가 발생하는 현상

> page table entry가 virtual memory management를 지원하려면,

target 주소가 ram이 아닐때를 구분할 수 있는 flag가 필요. 

* Resident Bit 

: 대상 페이지가 물리 메모리에 있는지, 스왑디바이스에 있는지 구별해주는 플래그

> Virtual Memory 사용의 key!

: 값싼 Disk를 사용하여 비싼 메모리를 사용하는 것처럼 구현하여 사용하자.

> Demanding Paging 구현의 기술적 이슈

- Page Fault :  virtual address가 가리키는 page가 physical memory에 없어서 프로세그가 더 이상 진행할 수 없는 상태를 OS에게 알려주는 일종의 소프트웨어 인터럽트

* page fault handler : 인터럽트 서비스 루틴을 수행

<Page Fault Handling>

1. DMA Controller에게 해당 페이지의 주소를 전달

2. DMA Controller는 해당 페이지를 physical memory로 로드

3. DMA Controller의 작업이 끝나면 인터럽트 발생

4. OS는 page fault를 일으킨 프로세스의 수행을 재개

> Page Fault Handling이 다른 인터럽트 처리보다 어려운 경우

: 인터럽트는 수행중인 instruction에 의해 변화된 상태를 되돌렸다가 page fault 처리가 끝난 후 해당 instruction을 재개해야하기 때문

=> page fault 모든 수행에 일어날 수 있으므로 instruction 재개가 굉장히 어렵기 때문에 에외적으로 처리하게 됨 (virtual memory를 지원하기가 어려움)

* MOVE (SP)+, -(R2)

: SP가 가리키는 메모리 location의 값을 R2의 값을 하나 감소시킨후 copy하라.

* VAX의 경우는 애초부터 virtual memory를 지원하도록 설계하였는데 

CISC Instructiond은 restart가 어렵기 때문에 마이크로 코드로 다시 프로그램되어있으므로 마이크로 코드로 리버스 시킴(페이지폴트 발생시 인스트럭션 수행중의 변화시켰던 모든 레지스터 state를 복구하고 핸들링이 끝나면 다시 이전의 instruction이 restart되도록)

* 요즘은 RISC 방식으로 구현되며, RISC는 restartable하게 구현

> 정리

과거에는 프로그램이 수행될 떄, 프로그램과 관련한 모든 메모리가 전부 물리메모리에 있어야 하므로 비싼 메모리의 가격이 문제가 되었음.

비싼 메모리를 줄이고 싼 디스크를 swap device로 사용하는 virtual memory management라는 기술이 발전하였음.

Virual Memory Management는 virtual memory address를 physical memory address로 전환해주는 하드웨어인 MMU의 지원이 꼭 필요함

> HW 트렌드가 변화되면서 여러가지 대응해야 할 이슈

swap device를 쓸 수 없는 과거상황으로 돌아가는 경우

"스마트폰" 디스크가 없고  solid state disk(flash memory)를 secondary disk로 사용

flash memory는 ROM으로 Erase횟수가 제한이 있으므로 swap device로 사용할 경우 수명이 급격히 줄어들게 됨

> Demanding Paging은 페이지가 요구될 때 메모리에서 불러오므로 페이지가 요구되는 시점에 ram regident하지 않고 그 때 요청을 하게되면 page fault가 발생할 수 있으며 속도가 매우 느려질 수 있음 => 미리 예측하는 policy를 갖도록 하자!

* 이상적인 Page Selection Policies

:  앞으로 사용될 페이지를 미리 메인메모리로 가져와서 페이지 폴트가 발생하지 않도록 하는 방법

1. Demand paging : 

- pure demanding paging

- 프로세스가 시작할 때 메모리에 0개의 페이지로 시작하며, 엔트리 포인트에 들어갈 때 처음 인스트럭션부터 page fault가 발생하여 초반부에 엄청난 page fault가 일어나게 됨. 이후 충분한 페이지를 잡으면 원활하게 프로세스가 동작하게 됨.

- 가장 단순하지만, 프로세스가 생성되서 시작을 할 때 너무 오랜 시간이 소요됨.

2. Prepaging : 앞으로 사용될 페이지를 예측해서 미리 Main Memory로 로드하는 방법

- 한페이가 요청되면 인접한 페이지까지 로드

   => 효과적인 prepaging 방안 : Spatial Locality에 기반하여 page fault가 발생한 근처에 있는 페이지들을 Main Memory에 로드

3. Request Paging : 논리적으로 연관성이 있는 페이지들을 미리 Main Memory에 로드

- 과거에 사용했던 기법

- 예. Overay

=> 사용자가 결정해서 사용해야하는 불편함이 있음.

=> Working Set 대두!

> 여러가지 관점

1. 어떤 페이지를 언제 물리메모리로 불러올 것인지. Page selection policy

2. 스와핑 대상을 고르기. Page replacement policy

3. replacement를 수행할 때, 전체 프로세스들 중에서 고를지, 특정 그룹의 프로세스들에서 고를지. Page replacement style

4. page들을 어떤프로세스에게 page frame을 할당할때. Page placement style

# Paged Segmentation

: paging + segmentation

: 먼저 Segmentation 한 후, 그 다음 Paging을 수행

* why ?

: paging을 통해서 segment의 fragmentation의 문제는 해결할 수 있으나, 프로세스에게 multiple segment를 제공하고자하는 부분은 놓치게 됨. 

* 2번의 메모리 access로 인한 속도저하의 문제

: TLB(Transration Look Aside Buffer)를 사용하여 극복  => Cache 사용

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

|CPU Register | Cache | Memory | Disk |

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

* Paged Segmentation의 table 관리

- 기존의 segment table의 정보 : Segment number(Index, 상위비트), base address, bound address, 

- 기존의 page table의 정보 : Page number(index), frame number(page가 어느 physical공간에 있는지의 정보), 

: Paged Segmentation table에는 기존 Base address 대신, Segment의 Page table의 위치를 저장

: Paged Segmentation table에는 기존 Bound address 대신, 해당 세그먼트의 페이지 갯수를 저장

* Paged Segmentation 단점

; 1 memory access reference 당, extra memory reference가 3번 일어남

* 예제 - 24bit virtual address space에서 physical address 찾기

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

| Seg # (4bits) | Page # (8bits) | Page Offset (12bits) |

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

> logical address 0x    00        20         70

  1bytes  1bytes    1bytes    => 3bytes

> <segment table>

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

Base        |        Bound        |    prot

0x2000  |        0x14           |      R

0x0000  |        0x00          |    

0x1000   |        0x0D          |    RW

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

> <memory>

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

0x001F

0x0011                    -> 0x2020

...

0x0003

0x002A

0x0013                   -> 0x2000

0x000C

0x0007                  -> 0x1020

...

0x0004

0x000B

0x0006                 -> 0x1000

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

> 0x0(4bits)     |        02   (8bits)         |     0 70(12bits)

   1. seg table no.          Page Num                    offset

> 1. seg table no : 0

메모리에서 no가 0인 segment table을 찾음.  즉 base address는 0x2000이므로 메모리에서 0x2000을 찾아감

   2. Page Number : 02

binary 2. 즉 3번째 엔트리 값. 메모리상의 0x2000주소에서부터 2번째의 값을 찾음, 0x0003 이므로 찾은 값은 03.

   3. concatenation : Page Number의 값 03 + Offset 070 => 0x003070

> 결론

   virtual address : 0x002070

   physical address : 0x003070

* Segment Table과 Page Table을 사용한 주소 변환

> MMU에 의하여 하드웨어 적으로 수행됨

> 그러나 프로세스 문맥전환이나 새로운 프로세스의 생성등이 일어날 때, 

  운영체제가 Base/Bound Register 및 Segment/Page Table을 관리해야 하므로 운영체제에게 Transparent 하지 않음

* Paged Segmentation

- 프로세스의 logical unit들의 메모리 액세스 컨트롤을 용이하게하며, 

- 프로세스들 간의 세그먼트 공유를 용이하게하고,

- paging을하므로  external fragmentation의 문제를 해결

* address translation에 의한 메모리 관리의 2가지 주의점

- performance overhead

- space overhead

* Paged Segmentation 장단점

장 : page table space를 줄일 수 있음. segmentation을 사용하므로 pure paging에 비해 hole을 줄일 수 있으므로 공간 절약이 가능

단 : address translation 할 때, 메모리 엑세스 수가 많음

* but, 많이 사용되는 리눅스 OS에서는 pure paging 기법을 사용하여 메모리 관리함

> 과거 segment단위로 메모리 액세스 컨트롤을 page table로 다 내림. page 단위로 컨트롤

> sharing도 page 단위로 수행

=> OS에서 page를 segment영역(data, stack, text..)별로 선정하여 정보를 가지고 관리하게 됨. Machine independent. 

* Machine(HW) Independent, dependent의 차이

- Micro Architecture (CPU ...)

- System Architecture (메모리 구조, bus ...)

- I/O devices

* 대표적인 machine-Dependent한 코드

: context switching, Proccess 생성,  I/O 관리, Memory 관리, ...

> 모든 하드웨어가 segmentation를 지원하지 않기때문데 모든 하드웨어에서 사용되기 위해 pure paging을 사용하여 소프트웨어적으로 segmentation에 해당하는 부분을 OS가 지원하여 portability를 구현.

* Page Frame의 특성

- mapped page : translation을 거쳐 메모리 영역을 액세스하여 paging 기법

- unmapped page : translation 없이 물리 메모리에 directly하게 액세스 할 수 있게할 때 사용(page table,...)

- cached page : L1, L2 캐시를 사용 시, 성능 향상을 위해 한번 특정 워드가 액세스 되면 일반 페이지들은 모두 캐시를 시켜 hit을 시킴

- uncached page :  DMA의 대상 Page처럼 여러 프로세스에 의해 동시에 I/O가 sharing되면서 일어나면 경우 caching을 안되므로 uncached page로 만들어 사용

     (DMA : CPU Bus에 Master가 여러개가 존재하여 I/O를 동시에 가능)

* Large Page Table이 가지는 문제의 해결 조건

- Page Taable의 크기를 줄임

- 연속적인 메모리 공간 요구량을 줄임

# VAX 

: 1980년대, Large Page Table의 문제를 해결하기 위해 나온 컴퓨터 하드웨어

:  VMS Operating System 

: full name은 Virtual Address eXtension으로, 아키텍처를 디자인 할 떄 부터 virtual memory를 잘 다루기위해 설계

> 전체 virtual space를 4개의 segment로 나눔

- System Segment(os영역)

- P0 Segment(user영영1)

- P1 Segment(user영역2)

- unused Segment

<전체 Virtual Memory Space>   -------> virtual memory space이므로 mapped page 영역

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

System Virtual Memory                    -> System 영역 메모리 공간

User Page Table (System 영역도 virtual memory space에 있으므로 모두 가상주소로 표현됨.
                             가상메모리 공간에는 연속적으로 위치하지만 실제 물리메모리에는 연속적으로 위치하지 않음)

...

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

    -> User 영역 메모리 공간

User Virtual Memory                        

(P0, P1)

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

* physical address를 얻기

: User Page Table 테이블에서 얻은 값을 physical address로 얻기위해 OS는 Operating System의 주소를 가지는 physical memory의 page table에 접근해야함.

즉, physical memory  상에 연속적으로 OS의 주소를 변역하기 위한 page table을 저장하고 있어야 함.

1. User generates address.

2. Lookup in User Page Table.

3. Lookup in System Page Table. (Physical Memory)

4. Access physical address 

=> Address Translation 시, Overhead는 증가하지만, Large Page Table의 문제를 해결할 수 있음

# TLB 

: Translation Look aside Buffer

: 캐시를 사용하여 성능의 개선을 목적으로 개발

> Hit rate을 높이기 위해선 

1. 크게만들자? 그런데 64개~ 128개만 되어도 98%의 적중률을 달성할 수 있게됨  

why? Locality라는 특성을 가지기 때문에 적은수만 가져도 적중률을 크게 향상시킬 수 있음

- Spatial Locality : 수행된 부분의 위나 아래에 위치한 부분이 수행되는 것.

- Temparal Locality : 매우 짧은 시간안에 재수행되는 것. 

=> loop의 영향

2. page의 사이즈를 키우면 한 페이지 엔트리가 커버하는 어드레스 스페이스가 커지므로 hit rate를 높일 수 있음

> TLB의 구성 (컴퓨터 조직론)

: cache를 구성하는 세가지 방법처럼 구성

1. 순차적으로 모두 검색

2.page table entry를 특정영역에 mapped하여 찾기. Direct mapped cache. 저렴하지만 collision이 발생하면 hit rate이 떨어질 수 있음.

-> Set associative cache로 극복

3. Fully associative cache. 빠르지만 비쌈.

# 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

=> 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