skyjump's blog

실린더, 트랙, 섹터
섹터단위로 데이터 저장.
가장 바깥쪽 실린더에 첫번째 트랙의 첫번째 섹터부터 데이터 저장.
track을 따라 저장되다가 같은 실린더의 다른 track을 따라 저장되다가 실린더 바깥쪽에서 안쪽으로 간다.

logical block의 1차원 배열이 디스크의 섹터로 순서대로 매핑된다.

매핑하는데 어려운 점들
 

디스크에 불량섹터가 있을 경우
트랙당 섹터 수가 균일하지 않은 문제 
트랙당 섹터 밀도수가 다를 때
같은 데이터 전송률을 유지하기 위해서는  바깥쪽에서 안쪽으로 갈 때 회전 속도를 증가시킨다.

 
Disk scheduling

운영체제는 Disk scheduling를 통해 빠른 access time, 큰 disk bandwidth가 되도록 한다.
access time를 결정하는 두가지 주요요소 
seek time(디스크 헤더를 원하는 섹터가 있는 실린더로 옮길 때 드는 시간)
rotational latency( disk가 원하는 섹터를 헤더에 오도록 판을 돌리는 데 걸리는 시간)
disk bandwidth 전체 전송된 바이트 수/서비스 요청에서 마지막 전송까지 걸린 시간
Disk scheduling으로 access time과 disk bandwidth를 향상 가능하다.

FCFS(first come first service)
선착순 방법. 요청큐에 들어온 순으로 처리.

SSTF(shortest seek time first)
현재 head 위치에서 seek time을 가장 최소로 하는 요청을 처리.
starvation문제 가능성.

SCAN
디스크암이 디스크 끝에서 다른 끝으로 움직인다. 움직이면서 각 실린더에 도달할 때마다 요청된 것을 처리한다. 디스크 끝에 도달하면 방향을 반대로 바꾼다.

C-SCAN
Circular scan
헤드가 디스크 처음부터 끝까지 요청들을 처리하면서 움직이는데 돌아올때는 요청들을 처리하지 않고 바로 처음으로 돌아간다.
더 균일한 wait time을 제공한다.
 
LOOK, C-LOOK
disk의 맨 끝까지 가지 않고 요청된 곳까지만 간다.

어떤 알고리즘을 써야 하나?

sstf나 look이 기본적인 알고리즘으로 괜찮은 선택.
디스크가 헤비로드일때 scan이나 c-scan이 괜찮음. 이 두개가 starvation에 영향을 덜 받기 때문에.
file allocation 방식에 영향을 많이 받을 수 있다. contiguously allocated file은 헤드 움직임이 적고, linked나 indexed file은 head가 많이 움직임.
directory와 index block의 위치도 영향을 미친다. 자주 읽히기 때문이다. 
os가 rotational latency를 줄일 수 있는 방법은 없다. 위 방식들은 seek time을 줄인다.

디스크 관리
disk formatting

low-level-formatting(physical formatting)
디스크를 디스크 컨트롤러가 읽고 쓸 수 있도록 섹터로 나누는 것.
하나 이상의 실린더 그룹으로 파티션을 나눈다.

logical formatting 
파티션을 나눈 후 파티션에 파일 시스템을 넣는 과정
FAT 또는 inodes. 비어있는 directory.

Boot block

bootstrap program
시스템을 초기화 (CPU 레지스터, 디바이스 컨트롤러, 메인 메모리 내용)
초기화 후 운영체제 실행
bootstrap은 디스크에서 시스템커널을 찾고, 커널을 메모리에 올리고, 운영체제 실행 처음 주소로 점프한다.
bootstrap은 ROM(read-only memory)에 저장된다.
대부분 시스템은 bootstrap 프로그램이 디스크로부터 full bootstrap program을 불러오는 기능만 ROM에 있어서 full bootstrap program을 쉽게 변경할 수 있또록 한다.
full bootstrap program은 boot blocks에 저장된다.
boot partition을 가지고 있는 디스크를 boot disk 또는 system disk라고 한다.

Swap-space management

Virtual memory 시스템에게 최고의 throughput을 제공하기 위한 것.
Virtual memory가 디스크 공간을 메인 메모리의 확장영역으로 사용하는 것.

두가지 swap-space 사용방법
프로그램 전체(프로세스 이미지 전체)를 swap.
page 단위로 swap
물리 메모리 크기에 따라 swap space 크기가 다양함.

두가지 swap-space 위치

1) 파일 시스템에서 하나의 큰 파일로 보는 경우
일반 파일처럼 파일 시스템 과정(디렉토리, 디스크 공간할당)을 거치기 때문에 느리다.

2) 분리된 디스크 파티션으로 보는 경우
file system이나 디렉토리 구조가 없다. 
swap-space storage manager가 블락 할당 관리.
swap은 빨라야 하기 때문에 공간 효율보다는 속도가 빠른 알고리즘을 사용한다.

RAID Structure

Redundant Arrays of Inexpensive Disks
여러개의 디스크를 사용함으로써 성능향상과 데이터의 신뢰도 향상에 쓰인다.

신뢰도 향상에 쓰이는 RAID
Mirroing(Shadowing)
같은 data를 모든 디스크에 중복해서 쓴다.

성능향상에 쓰이는 RAID
여러개 디스크에 병렬로 접근 - 데이터 전송률이 올라간다.
Data striping
bit-level striping
여러 disks에 각 byte의 몇 bits씩 쪼개어 저장한다.
Block-level striping
file의 몇 블락씩 여러 disks에 쪼개어 저장한다.

 

어플리케이션 프로그램 - 로지컬 파일 시스템 - file-organization module -  basic file system - I/O control - devices

Device drivers
메인 메모리와 디스크 사이의 정보 전송
효율을 위해 block단위로 전송된다. (하나의 block은 하나 이상의 sector)

Basic file system
디바이스 드라이버에게 명령을 보낸다.
device driver가 제공하는 함수를 사용한다.
각각의 physical block은 disk의 주소로 구분된다.

File organization module
logical block address를 physical address로 바꾼다.
Free space manager가 할당되지 않은 block들을 관리하고 있다가 요청이 들어오면 File organization module에게 block들을 제공한다.

Logical file system
metadata 정보를 다룬다. (실제 데이터를 제외한 모든 파일에 대한 정보)
FCB(file control block)을 통해 디렉토리 구조를 관리한다.

File system structure를 메모리에 올려놓고 쓰기

파일 디렉토리 구조를 만드는데 사용될 수 있는 자료구조들
Directory Implementation:Linear List

data block을 가리키고 있는 파일이름 리스트
 
삭제된 디렉토리 엔트리를 재사용하기 위한 방법
unused라고 표시를 해놓고, 그것을 free directory entries의 리스트에 붙이고, directory list의 마지막 entry를 unused라고 표시된 곳에 복사한다. 그러면 디렉토리 리스트 길이도 짧아지고, 삭제하는 시간도 줄어들 것이다.

Directory Implementation: Hash Table

hash를 이용한 linear list
찾기, 삽입, 삭제가 빨라진다.
collision문제, chained-overflow hash table로 해결할 수 있다.

Allocation Methods

file에 disk block을 어떻게 할당할 것인가.
공간효율성, 빠른 접근

Contiguous Allocation

각 파일은 디스크에 연속적인 block으로 할당되는 방식
단순하고 seek time이 빨라지는 장점이 있으나
새로운 파일을 위한 공간을 찾기가 어렵다거나, 원래 있던 파일이 증가될 수 없다는 단점이 있다.

Linked Allocation

각 파일은 disk blocks의 linked list이다.
directory는 list의 처음과 끝을 가리키는 포인터를 가지고 있다.
장점
external fragmentation이 없다.
파일 크기가 가변적이어도 상관없다.
단점
순차 접근만 가능하다. 찾을때 파일의 처음부터 시작해야 한다.
block마다 pointer를 위한 공간이 필요하다.
pointer가 깨졌을 경우 문제

File Allocation Table(FAT)

Linked allocation의 개선
FAT의 경우에
각 디스크파티션의 시작 섹션에 table을 둔다.
이 테이블은 파티션 내 모든 disk block 수만큼의 엔트리가 있고 각 엔트리는 파일의 다음 block number값을 갖는다.
디렉토리 entry는 파일의 첫번째 블락 넘버를 가지고 있다.
Random access time이 개선된다. FAT에서 일단 먼저 찾아보면 되니까.

Indexed allocation

모든 포인터를 index block에다가 넣기
각각의 파일들은 자신의 index block을 가지고 있다.
디렉토리는 index block의 위치를 가지고 있다.
포인터가 한두개밖에 없더라도 하나의 block이 할당되어야 하므로 공간낭비문제가 있다.
external fragmentation 없이 direct access를 지원할 수 있다. block이 더 필요하면 free-space manager에게 요청하면 block하나 받아서 index block에 번호 추가시키면 됨. 그리고 index block을 읽으면 어느 block에 순차적으로 탐색안하고 접근할 수 있음.

Index block이 얼마나 커야 하는가
index block이 너무 작으면, 큰 파일을 어떻게 다룰지에 대한 문제가 있다.
Linked scheme - index blocks의 list
Multilevel index - 첫번째 인덱스 블락은 두번째레벨 인덱스 블락을 가리킨다.
Combined scheme(UFS) - inode(FCB)가 가진 15개 index blocks 중에서 12개는 파일의 데이터와 직접 연결하는 index이고(direct blocks), 1개는 하나의 index block을 가리키는 index(single indirect block), 1개는 2개의 index block을 가리키는 index block의 index(double indirect), 나머지 하나는 triple indirect.

Disk Drive, Partitions, and a File System

디스크는 파티션으로 나누어 지고
파티션에는 boot block, super block, inode list, data block으로 이루어져 있다.
boot block은 OS를 로드하고 초기화하는데 필요한 코드들이 들어있고
super block에는 파일 시스템의 메타정보들이 들어있다.
Inode list에는 inode들이 들어있다. 유닉스에서는 directory를 하나의 파일처럼 간주한다.

Free-Space Management

시스템은 free space list를 유지한다.
free disk blocks들이 list에 있다.
리스트 구현 : bit vector, linked list, grouping, counting
bit vector
block i가 free면 0, 아니면 1
디스크 용량이 큰 경우 전체 벡터를 메인메모리에 다 못담는다.
연속적인 공간을 얻기는 쉽다.

linked list
첫번째 블락의 포인터만 가지고 있으면 된다.
연속적인 공간을 얻기 어렵다.
공간이 필요하면 리스트의 첫번째 블락부터 주면 된다.
리스트 탐색이 자주 필요하지 않아서 탐색문제는 크게 문제되지 않는다.

grouping
첫번째 free block에 n개의 free block 주소를 저장한다.
n-1개는 정말 비어있는 block이고 마지막 1개는 또 다른 n개의 free block 주소가 저장되어 있다.
free block을 한번에 많이 찾을 수 있다.

counting
연속적인 할당을 이용한다.
첫번째 free block의 주소와 그 블락 뒤에 몇 개의 free block이 있는지에 대한 정보를 가지고 있는다.

Page Cache and Buffer Cache
 

또다른 성능 향상 방법.
디스크 컨트롤러 내에 local memory가 있는데 cache라고 한다. 한 트랙을 담을 정도의 크기를 가지고 있어서
cpu가 cache에서 읽으면 빠르다.
어떤 시스템은 Buffer cache 이용하고 어떤 시스템은 Page cache이용.
buffer cache는 다시 쓰일 것 같은 block유지.
page cache는 virtual memory 기법이 사용된 것으로 파일 데이터를 block단위가 아니라 page단위로 사용하는 것.

I/O without a unified buffer cache

memory mapped file을 읽을 때, 
virtual memory가 buffer cache랑 데이터를 주고 받을 수 없어서 buffer cache의 내용을 page cache로 복사해야 함.(double caching)

대신에 unified buffer cache를 사용하면 memory mapping과 read, write 시스템콜이 같은 페이지 캐쉬를 사용한다.

Recovery

파일과 디렉토리가 main memory와 disk에 있을 때 시스템이 맛이 가도 data 손실이나 불일치를 막아야 한다.

Log-Structured file system
파일을 디스크에 쓰는 과정이 새로운 블락이 할당되고 inode에 새로운 블락정보와 파일정보를 업데이트 하고, block들이 디스크에 쓰여지는 등 과정이 atomic하지 않기 때문에 중간에 시스템에서 interrupt가 나는 경우 일관성 문제와 정보 손실 문제 등 발생. meta data가 손상될 수도 있고.
Journaling(로그기반 처리)은 database의 transaction 같은 것. 변경 과정을 파일에다가 기록.
파일의 일관성을 유지하기 위해 transaction이 제대로 잘 수행되거나 아님 아예 수행이 안되거나 둘 중하나를 보장한다.
메타데이터에만 적용될 수도 있고 파일에 적용될 수도 있다.

NFS(Network file system)
원격의 다른 컴퓨터 파일 시스템을 쓰는 기술.
패킷에 담아 read, write 같은 명령을 전달.

 

추상적인 데이터 타입
OS가 파일에 대한 시스템콜 제공 
파일을 open하면 디스크의 directory 구조에서 내용을 찾고, 메모리에 그 내용을 옮긴다.
close하면 메모리 있는 내용을 디스크에 쓴다.
OS는 open-file table을 가지고 있다.

멀티유저 시스템은 두가지 file table을 가지고 있다.

Per-process table
프로세스 별로 file정보를 가지고 있다.
프로세스 의존적인 정보(현재 파일 포인터, 접근 권한 등)

System-wide table

모든 프로세스와 관련된 파일 정보를 가지고 있다.(디스크에서 위치, 접근 날짜, 파일 크기 등)
Open count- 파일이 open되면 1씩 증가, close되면 감소 

File Type

file type으로 그 파일의 내부 구조를 알 수 있다.
OS가 많은 파일 타입을 지원하면 안좋다.
각각의 파일 타입을 지원하는 코드가 필요한데, 그 구현과 OS크기가 복잡하고 커진다.

모든 OS는 실행파일은 지원해야 한다.

Disk 할당

Logical record unit
Unix는 모든 파일을 바이트의 연속이라 정의했다. 1byte가 단위이다.
Physical record unit
모든 disk 장치들은 block 단위로 수행된다. 예) 512byte가 한블락

Access Method

Sequential Access
파일의 정보가 순서대로 처리된다.
read, write 시스템콜 사용하는 것처럼.

Direct Access
순서없이 record를 읽고 쓸 수 있는 것.
어떤 블락에도 random access가 가능하다.

Directory Structure

파일의 숫자가 많아지다보니 생겼다.

파티션
디스크를 여러개의 파티션으로 나눌 수 있다.
각각의 파티션마다 directory(파일에 대한 정보)가 있다.
여러개 dish를 하나의 partition으로 할 수도 있다.

Single-level directory
모든 파일이 같은 디렉토리에 있는것.
모든 파일은 유일한 이름을 가지고 있어야 한다.

Two-level Directory
사용자 마다 자신의 디렉토리가 있다.
master file directory와 user file directory 두 단계.

Tree-Structured Directories
디렉토리가 파일도 포함하고 서브디렉토리도 포함한다.
디렉토리를 하나의 파일로 본다. (처리방식은 다르다.)

Acyclic-Graph Directories

파일과 디렉토리를 공유할수 있다.
문제점
여러개의 이름을 가진다. shared structure를 한번이상 탐색하지 않게 하고 싶을 때 문제.
파일을 삭제하면 원본없이 포인터만 있게 되는 문제.(그냥 내버려둬서 잘못된파일이름으로 처리하거나, 파일을 삭제하지 않고 유지하는 해결방법이 있다.)

Soft link and Hard link

soft link - soft link는 original 파일 이름을 가리킨다. original 파일 이름이 바뀌면 soft link는 쓸모가 없게 된다. 다른 파일 시스템의 파일을 가리킬수 있다.
hard link - 파일을 가리킨다.(inode) 원본 이름이 바뀌어도 안깨진다. 다른 파일 시스템을 가리키지는 못한다.

File system mounting

파일 시스템에 새로운 파일 시스템을 붙이는 것.

 

초기에는 프로세스의 명령어와 데이터가 실행되려면 프로세스 전체가 물리메모리에 있어야 했었다. 
프로세스 사이즈가 커지면서 메모리 활용에 문제가 생겼고, 이를 해결하려는 방법들이 나왔다.

1) Dynamic loading
시작에는 main routine만 메모리에 로드되어, 다른 routine들은 호출될 때만 메모리로 로드된다.
사용되지 않는 루틴들은 메모리로 로드되지 않아서 메모리 활용이 높아진다.
루틴을 로드할 때의 overhead 문제가 있다.

2) Dynamic linking
library의 linking을 load타임때 하지 않고 runtime 때 사용되면 stub가 library를 메모리로 로드하거나 이미 다른 프로세스에서 사용되어서 로드 되었으면 연결을 시켜준다.
여러 프로세스가 한 library를 공유할 수 있다.

3) Overlays
Dynamic loading과 비슷함. 
프로그래머가 overlay driver를 작성하여, overlay driver는 필요할 때 루틴을 메모리로 로드한다.

4) Swapping
메모리에 있던 프로세스를 디스크로 보내는 것.
나중에 다시 필요할 때 디스크로부터 불러온다.
swap하는 데 걸리는 시간은 전송시간이 큰 부분을 차지한다.

Virtual Memory

logical memory를 physical memory로부터 분리
실행중일 때, 메모리에 필요한 건 프로그램의 일부분이다.
그래서 일부분만 메모리에 올린다면  logical memory는 physical memory보다 훨씬 크게 할 수 있다.
프로그래머는 physical memory size를 걱정할 필요가 없다.

Demand Page

Virtual memory 구현하기위해 필요한 것.
Swapping은 전체 프로세스를 디스크로 옮기는 것인 반면
Demand paging은 프로세스를 page 단위로 나누고 필요한 page만 메모리로 옮겨서 처리하는 것.
Lazy swapper라고 불린다.
Pager는 필요한 페이지만 메모리에 불러온다.
page table 참조해서 페이지가 현재 메모리에 없으면 디스크에서 불러온다.
page table의 valid-invalid bit을 이용해서 해당 page가 메모리에 존재하는지 디스크에 존재하는지 알 수 있다.
valid-invalid bit가 0이라면, 메모리에 없을 가능성이 있어서 page fault 인터럽트 발생

page fault handling

page fault에는 2가지 경우가 있다.
OS가 PCB를 참조하여
1) 그 페이지 주소가 정상적인 범위가 아니어서 invalid 였다면 그 프로세스를 종료시킬 것이고
2)  단지 메모리에 없어서 그런거라면 메모리에 올려주고 vaild bit를 1로 바꿔준다. 그리고 다시 인터럽트된 명령어로 돌아가서 실행한다.

비어 있는 frame이 없을 때
메모리에서 안 쓰는 page를 찾아 디스크로 저장한다.

pure demand paging

실제로 그 페이지가 사용될 때까지 메모리에 올리지 않는다.
이 경우에 만약 명령어마다 한 페이지씩 요구하는 프로그램이 있다면
page fault가 많이 발생해서 성능이 엄청 안좋을 것이다.
locality of reference
다행히 프로그램은 메모리에서 일정 범위안에서만 참조하는 경향이 있다.

실제로 초기화할때 몇 개의 page를 미리 올려놓는다고 한다.

하여튼 성능을 높이려면 page fault의 최소화가 중요하다.

Copy-on-Write

fork()함수는 자식 프로세스를 생성한다.
부모의 주소공간을 카피한다.
부모와 동일한 코드를 실행하기 때문에 메모리를 또 할당할 필요없이 공유할 수 있다.
같은 page를 공유하게 된다.
만약 한 page에 쓰기를 한다면 그 page만 카피해서 새로 만들어준다. copy-on-write
수정이 필요한 page만 새로 만듦으로써 효율적인 메모리 사용이 가능하다.

새로운 page가 필요할 때 메모리에 어떻게 할당할 것인가?

Pool

보통 운영체제는 free pages를 담은 pool을 유지한다.
그래서 자식프로세스가 새로운 page가 필요할 때나 프로세스의 stack이나 heap 공간이 더 필요할 때 pool에서 꺼내 할당할 수있도록 한다.  zero-fill-on-demand 기법을 사용하여 할당되기 전에 그 page에 있던 내용을 다 지워준다.

Page Replacement

over-allocating
demand paging을 이용해서 메모리가 수용할 수 있는 양보다 많은 프로세스를 돌릴 수 있게 되었다.
하지만 어느순간 메모리가 수용할 수 있는 양보다 많은 페이지 요구가 일어날 수 있다.
페이지가 메모리에 없어서 page fault를 했는데 free frame이 없을 경우 어떻게 해야 할까?
프로세스를 하나 죽이는 것은 비효율적이다.
page replacement를 한다.

Basic page replacement

1. 디스크에서 필요한 page의 위치를 찾고
2. free frame 찾기
    2.a 있으면 할당
    2.b 메모리에서 희생될 프레임(victim frame)을 선택한다.
    2.c 디스크에 victim frame을 쓰고 page와 frame table을 변경한다.
3. 디스크에서 그 page를 freed frame에 올린다. page와 frame table을 변경한다.
4. user program을 다시 시작한다.

2번의 page 전송이 일어난다. victim page를 디스크에 저장하는 것, 원하는 페이지를 디스크에서 꺼내오는 것.
이걸 줄여볼 수없을까?

Modify bit(or dirty bit)

page가 수정되었으면 modify bit가 1이 된다.
page replacement할 때 modify bit가 0이면
디스크에 쓸 필요가 없다. page 전송이 한번으로 줄게된다.

disk I/O는 시간이 많이 걸린다.
modify bit로는 불충분하다.
disk I/O를 줄일 수 있는 방법이 필요하다. 즉, page fault가 덜 발생하도록 하는 algorithm이 필요하다. 각각의 프로세스에 얼마나 많은 frame을 할당할 것인지(frame-allocation algorithm)와 page replacement가 필요할 때 어떤 frame을 선택할 것인지(page-replacement algorithm)에 대해 효과적인 방법을 찾아야 한다.

Page replacement algorithms

First-In-First-Out(FIFO) algorithm
page가 교체될 때 가장 메모리에 먼저 들어갔던 page가 교체되는 것.

Belady's Anomaly

그 프로세스에 할당된 메모리가 늘어 났는데 page fault가 더 많이 발생하는 현상.
메모리가 늘어났다고 해서 꼭 좋아지는 것은 아님을 알 수 있다. 

Optimal page-replacement algorithm

향후에 참조될 확률이 제일 적은 page가 교체된다.
컴파일러가 도와주면 가능은 하겠지만
reference string을 미리 알아야 하므로 구현하기 어렵다.

Least Recently Used (LRU) algorithm

가장 오래전에 참조되었던 페이지가 교체된다.
프로그램의 지역성(locality) 때문에 효과적인 알고리즘이다. (프로그램이 참조하는 page가 몰려있다. 한번 참조했던 page는 또 참조될 가능성이 크다.)
구현은 어떻게 할까?
Counter나 Stack을 이용한다.
Counter
page table의 entry마다 counter를 가지고 있다.
페이지가 참조될 때 counter에는 참조된 시각을 기록한다.
가장 오래된 시각을 가지고 있는 페이지를 교체한다.
Stack
page number를 가진 스택이 있다.
page가 참조될 때마다, 스택에 있는 그 page number를 맨 위로 올린다. 
가장 아래 있는 page number가 LRU이다.
doubly linked list로 구현하면 성능향상에 도움이 된다.

OPT나 LRU는 Belady's anomaly 현상이 일어나지 않는다.
메모리 할당이 하나 늘어났을 때 들어있는 page number set이 늘어나기 전의 page number set을 포함하기 때문이다.

하지만 Stack이나 Counter방식은 하드웨어 지원이 필요하고, 매번 메모리 참조가 일어날때마다 clock field나 stack을 업데이트해야 하기 때문에 성능이 느려진다. 

LRU Approximation algorithm

많은 시스템이 reference bit 을 이용해 LRU 비슷한 알고리즘을 하드웨어로 지원해준다.

Additional-Reference-Bits Algorithm

각 페이지당 reference-bits로 8bit 를 가지고 있다. 이 8bit는 일정시간간격으로 오른쪽으로 한칸 시프트 된다. 맨 오른쪽 비트는 버려진다.
그 페이지가 참조되면 맨왼쪽 bit를 0에서 1로 바꿔준다.
가장 적게 사용된 page는 page중에 가장 작은 reference-bits를 가지고 있는 페이지다.
일정시간간격이 좁을 수록 LRU에 가까워진다.

Second-Chance Algorithm
 

reference-bit이 한개이다.
FIFO algorithm에 기반을 두었다.
꺼낸 페이지의 reference-bit이 0면 그 페이지가 교체된다.
reference-bit가 1이면, 이번엔 그냥 넘어간다. 대신에 0으로 바꿔주고 맨 뒤로 보낸다.
최악의 경우에는 모든 page의 reference-bit가 1이 될 경우이다. 이 때는 FIFO 알고리즘이 된다.

Counting Algorithm

각각의 페이지 참조수를 센다.

LFU (Least Frequently Used) Algorithm
가장 작은 count를 가진 page를 교체한다.
하지만 그 페이지가 초기에만 엄청 사용되고 그 뒤에는 전혀 사용되지 않는다면?

MFU (Most Frequently Used) Algorithm
가장 큰 count를 가진 페이지를 교체한다.
작은 count를 가진 page들이 아직 할 일이 있을 것이다라는 생각에.

Allocation of Frames
 

각각의 프로세스는 최소로 필요한 page수가 있어야 한다.
첫번째 이유는 performance 때문. 할당된 frame 수가 줄어들수록 page fault가 자주 발생하게 된다. 그리고 page fault가 발생하면 처리된 후에 실행중이었던 명령어가 다시 실행되어야 한다. 그래서 최소한 page fault 없이 한 명령어를 실행할 수 있는 프레임이 할당되어야 한다.
프로세스당 최소 프레임 수는 architecture에 의해 정해지고, 최대 프레임 수는 이용가능한 물리 메모리에 의해 정해진다.

할당 알고리즘
 

1. equal allocation
100개 frame과 5개 프로세스가 있으면 한 프로세스에게 20개씩 똑같이 주는 것.
2. proportional allocation
프로세스 사이즈에 비례하여 frame을 준다.
3. priority allocation
프로세스 우선순위에 비례하여 frame을 준다. 아니면 우선순위랑 사이즈 모두 고려해서 줄 수도 있고.

global vs. local allocation
 

여러개의 프로세스가 프레임들을 차지하고 있는 상황에서
페이지 교체할 때
global replacement은 모든 프레임에서 교체할 프레임을 선택하는 것.
local replacement은 자기 프로세스에서 교체할 프레임을 선택하는 것이다.
global replacement의 한가지 문제는 자신의 page-fault rate를 조절 할 수 없다는 점. 왜냐하면 자신의 paging 방식뿐만 아니라 다른 프로세스의 paging 방식에 영향을 받기 때문. 따라서 같은 프로세스의 수행시간이 때에 따라 다르게 나올 수 있다.
local allocation은 한 프로세스가 자신에게 할당된 pages를 잘 활용하지 못할 때, 다른 프로세스가 페이지를 얻는 것을 방해하는 셈이 된다. 그래서 global replacement가 시스템 처리율에 있어서 더 좋아서 더 많이 쓴다.

Thrashing
 

낮은 우선순위를 가진 프로세스의 프레임이 컴퓨터아키텍쳐에가 요구하는 최소 프레임수 아래로 떨어지면 그 프로세스가 가진 남아있는 페이지들을 디스크에 저장하고 (Swapped out) 할당된 프레임을 해제시켜야 한다.
충분한 프레임을 갖지 못한 프로세스는 page fault가 발생할 가능성이 높다.
process가 thrashing 하다는 것은 프로세스가 실행하는 것보다 paging에 더 많은 시간을 쓸 때를 말한다.

Thrashing이면 CPU utilization이 떨어진다.
Global replacement일 때, 프로세스가 다른 프로세스 프레임 뺏고, 다른 프로세스가 그 프레임 읽으려고 했는데 없어졌으니까 또 다른 프로세스 프레임 뺏고 하는 상황이 생길 수 있다. paging 해주는 장치가 바빠져서 프로세스들은 waiting 큐 대기해서 paging 장치를 사용하기를 오랫동안 기다려야 한다. waiting큐에 쌓일 수록 ready 큐에는 아무것도 없는 상황 발생. 그래서 CPU 활용률은 떨어지게 되는 셈.
CPU 스케쥴러가 cpu utilization이 떨어지는 것을 보고 멀티프로그래밍정도를 증가시킨다. 그러면 상황이 더 악화.
처리되는 프로세스 수가 많아질 수록 CPU utilization은 올라가다가 어느 순간 떨어진다. 이때가 Thrashing 상태이다.
Thrashing을 막기 위해서는 멀티프로그래밍 정도를 낮춰야 한다.
local replacement 알고리즘을 사용한다면 막을 수 있을까? 이 알고리즘 쓰면 한 프로세스가 thrashing 하더라도 다른 프로세스의 프레임을 뺏지 못할텐데..
그래도 완전한 해결책이 되지 못한다. 프로세스들이 thrashing에 빠지면, paging device를 위한 큐에서 대기하는 시간이 길어질거고 page fault 처리하는 시간도 길어진다. 그 결과 thrashing이 아닌 다른 프로세스들에 접근하는 시간도 길어지게 된다.

Thrashing을 막기위해서는 가능한 많은 프레임을 프로세스에게 주어야 한다. 하지만 얼마나 많은 프레임이 필요한지 어떻게 알까?
Working-set strategy방법을 쓴다. 이 방법은 프로세스 수행이 locality하게 된다는 것이 전제로 한다.
Locality model은 프로세스가 수행될 때 한 지역에서 다른지역으로 움직인다는 것이다. 한 지역은 함께 자주 사용되는 페이지들의 영역이다. 한 프로그램은 몇개의 localities가 있다.
Locality model에 의해 Thrashing을 해결하려면 한 프로세스에게 최소한 현재의 locality를 수용할 수 있는만큼 frame을 할당한다.

Working-set model

locality에 기반한 방법.
Δ : working-set window, 일정한 갯수의 페이지를 담는 창. 
창에 참조되는 새로운 page 번호가 계속 들어오고, 창 범위를 넘어간 오래된 page는 나간다.
윈도우 사이즈가 너무 작으면 locality를 반영할 수 없고, 클 수록 일부 locality를 반영할 수 있다. 창 사이즈가 무한대면 모든 locality 반영.
working set :가장 최근의 Δ에 있는 페이지들 집합.
한 프로세스의 working set의 크기를 D라고 하면 D는 그 프로세스가 필요한 프레임의 크기이다.

D가 현재 이용가능한 프레임보다 크면 Thrashing이고, 이 때는 페이지를 확보하기 위해 돌아가고 있는 프로세스 중에 하나를 중지시켜야 한다. 그래서 최소한 D만큼의 프레임은 있도록 한다.

D가 계속 변하기 때문에 메모리 할당 크기는 시간에 따라 달라지게 된다.

매번 참조되는 페이지랑 working-set이랑 비교하는 것은 비용이 많이 든다.
따라서 대략적인 방법을 이용한다.
일정 시간마다 타이머 인터럽트를 발생시킨다. 그래서 그 때의 Δ를 이용한다.
각각의 페이지마다 2bit의 과거의 참조 정보를 가지고 있다.
2bit의 과거참조정보는 인터럽트가 발생하면 왼쪽 시프트해서 오른쪽 bit가 0이 되고 
Δ에 해당 페이지가 있으면 그 페이지의 오른쪽 bit에 1을 넣는다.
2bit 중에 어느 하나라도 1이면 page는 working-set에 포함된다.
일정 시간 내에서 정확한 참조 발생 위치, 시간을 알 수 없기 때문에 정확하지는 않다.
과거정보를 기억하는 bit를 늘려주고 타이머 인터럽트 시간을 더 주기적으로 해주면 더 정확해지지만 비용이 많이 든다.

 

Page-fault frequency방법

한 프로세스의 page-fault 비율을 모니터링
page-fault 비율이 너무 높으면 프레임을 더 주고, 너무 낮으면 프레임을 뺏는다.

Memory Mapped Files

virtual address를 이용해서 file i/o를 메모리 접근 루틴으로 하는 방법.
파일을 메모리로 읽어와서 read(), write() 대신에 virtual address를 호출하는 방식으로 파일처리.

디스크에 있는 파일이랑 동기화가 바로 안된다.
close()하면 memomy-mapped data가 disk에 쓰여지고 virtual memory로부터 제거된다.

여러 프로세스가 같은 mapped 된 파일을 동시에 접근할 수 있다.
copy-on-write기능을 지원해야.
여러 프로셋가 쓸 경우 동기화문제도 다루어야 한다. 

Memory Mapped I/O

더 편리하게 I/O장치에 접근하기 위해 많은 컴퓨터아키텍쳐들은 memory mapped i/o를 제공한다.
각각의 I/O 컨트롤러는 CPU로부터 전송된 명령이나 데이터를 저장하는 레지스터를 가지고 있다.
이 레지스터들을 메모리로 매핑한다. 따라서 메모리 주소로 레지스터 값을 읽고 쓸 수 있다.
device register는 I/O port라고 불린다.
CPU는 이 I/O port를 통해 데이터를 전송하고 받는데,  
CPU가 memory mapped 된 i/o port로 데이터를 보내고 control register에 데이터 보냈다고 bit을 입력하면
device는 그 데이터(byte)를 받고 다음 데이터 보내라고 control register의 그 bit을 clear한다.
Programmed I/O 
CPU가 control register의 그 bit를 계속 감시하고 있는 것. device가 준비가 되었나 안되었나 계속 주시.
interrupt driven
CPU가 bit 감시안하고 그 시간에 다른 일하다가 인터럽트로 보고 받는 것.

중간정리
page management 큰그림

Preparing
많이 참조될 만한 것을 미리 한번에 메모리로 다 가져온다.
pure demanding-paging은 시작할 때 많은 page fault 발생
프로세스가 중지되었을 때 working-set을 저장했다가 다시 시작할 때 working set을 불러오는 방법.

Page size selection
page size가 작으면 i/o 시간이 적게들고, internal fragmentation이 적다. page table size는 커진다.(table fragmentaion 문제)
page size가 크면 page fault 빈도가 줄어든다. 

TLB Reach
TLB의 hit-rate는 엔트리 수하고 관련되어 있다.
hit-rate를 높이려면 엔트리 수를 키워야 하는데, TLB를 구성하는데 이용되는 메모리가 비싸다.

hit-rate와 비슷한 평가요소인 TLB Reach
TLB로부터 접근할 수 있는 메모리 양(앤트리 수 * 페이지 사이즈)
성능이 가장 좋은 이상적인경우는 working set을 모두 cover할 수 있을 정도의 TLB Reach가 되는 것.
TLB Reach 크기를 늘일 수 있는 경우는 두가지.
page size가 크게 또는 다양한 size의 page를 제공
페이지 크기 크게 하면 in fragmentation이 생길 수 있다.
페이지 사이즈를 다양하게 하면 OS가 TLB를 관리 해야 한다.

I/O Interlock
메모리에서 쫓겨나면 안되는 페이지들을 locked한다.

Consider I/O
디바이스에서 파일을 카피하는데 이용되는 페이지들은 page replacement algorithm에 의해 선택되면 안된다.locked한다. 

참고사이트
http://oslab.snu.ac.kr/course/2010_fall/os/lecture_note/2010-os-ch10nn.pdf
http://bug7015.tistory.com/entry/Virtual-Memory-5-Working-Set-Model

vertax u에서 v로 최소 weight로 가는 path
shortest path의 sub path도 shortest path이다.

Triangle inequality
δ(u, v) ≤δ(u, x) + δ(x, v).
거쳐서 가면 길어진다.

그래프가 음수 weight를 갖는 cycle이 있다면 some shortest paths는 존재하지 않을지도 모른다.
사이클 돌면서 weight가 계속 작아질 수 있으니까 말이다.

Single-source shortest paths

하나의 vertex s∈V가 모든 vertex v ∈ V에 대해 shortest path를 찾기.
만약 모든 edge가 음수가 아니라면 모든 shortest-path weight는 존재한다.
Greedy로 보여줄게.
vertex s부터 시작해서 각 단계마다 s에서 최소로 갈 수 있는 vertex v를 선택해서 s가 속한 집합에 넣는다.
v에 인접한 vertex들의 거리를 수정한다.

Dijkstra’s algorithm

우선순위큐를 가지고 있다. 큐안에는 아직 s로부터 가장 짧은 거리가 정해지지 않은 vertex들이 있다.
큐에 있는 모든 vertex가 시작 vertex s가 속한 집합 S에 포함될 때까지
큐에서 최소값(u)을 뽑아서 S에 포함시킨다.
u의 인접 vertex(v)들에 대해서 u를 통해서 v로 가는 게 원래 가는 방법보다 더 가깝다면 바꿔준다.
우선순위큐의 값이 바뀌게되어서 다시 min heap을 만들어 준다.

Correctness

Greedy라서 맞는지 검증을 해야 한다.
증명 생략

Analysis

 출처 : Introduction to Algorithm
 

모든 edge의 weight가 1이라면 어떻게 될까?
우선순위 큐 대신에 FIFO 큐를 쓸 수 있다.
Breadth-first search와 같다.
O(V+E)

Bellman-Ford algorithm

vertex s∈V 로부터 모든 v∈V에 대한 shortest-path lengths를 찾거나 아니면 negative-weight cycle이 존재하는지 알아내는 방법.

알고리즘
초기화하고, |V|-1 번 모든 edge들을 relax한다. (모든 edge를 relax하고 나면 vertex 하나씩 최소 거리가 정해진다. 가장 긴 simple path는 최대 |V|-1번이다.) 
다 하고 나서 다시 모든 edge (u,v)에 대해서 d[v] > d[u] + w(u,v)가 있는지 찾는다. 음수 사이클이 없으면 d[u]가 최소값이 되어야 된다.
O(VE)

그래프에서 그래프의 모든 정점을 다 포함하는 트리.
부분 그래프이다. 트리라서 사이클이 없다.

Minimum spanning tree (MST)
 

spanning tree 중에서 가중치 합이 최소가 되는 spanning tree.
N개 vertex가 있으면 edge는 N-1개 있다.

일반적인 MST
처음에 A를 0으로 놓고 safe edge를 계속 추가해 나간다. 더 이상 안나올때까지 반복.
safe edge : 단계마다 하나의 edge를 선택할 때, minimum spanning tree를 유지하도록 하는 edge.
respect a set A : 그래프를 하나의 선으로 나눌 때, A의 어떤 edge도 그 선을 지나가지 않을 때, 그 선이 A를 respect한다고 한다.
light edge : respect하게 cut(나눈 선)을 지나는 edge 중에서 최소 weight를 가진 edge들 중 하나. (light edge가 여러개 일 수도 있다. 그리고 어떻게 cut을 하느냐에 따라 light edge가 달라질 수 있다.)

light edge면 safe edge이다.

MST 구하는 방법

1. Kruskal algorithm
set A는 forest이다.
전체 forest에서 두개의 tree를 연결하는 weight가 가장 작은 edge를 찾는다. vertex 하나도 하나의 tree이다.
그 edge가 light edge이면 safe edge이다.
safe edge를 set A의 forest에 추가해 나간다.

탐욕적인 방법(Greedy method)이다.

사이클을 이루지 않도록 최소 weight edge를 하나씩 선택해서 모든 vertex가 다 포함되면 minimum spanning tree가 된다.

구현
disjoint-set 이용.
vertex set을 만든다. edge들을 정렬한 다음 제일 작은 edge부터 선택한다. 선택된 edge가 사이클을 안만드는 것이어야 한다. edge (u,v)에서 u와 v를 find-set(x)해서 두개 값이 똑같으면 같은 set에 있다는 거니까 다른 값이 나와야 한다. 다르면 union한다.

성능
disjoint-set의 구조에 따라 성능 차이가 있다. union-by-rank와 path-compression을 이용하면 빠르다.
Edge수를 m, Vertex 수를 n이라 하면
1. set 초기화 Θ(n)
2. edge 정렬  Θ(m lg m),
3. find, equal, merge는 Θ(lg m), 이것을 모든 Edge에 대해 반복하므로 Θ(m lg m)이다.
m >= n-1이기 때문에 2,3 번이 1번을 지배. 따라서 Θ(m lg m)
최악의 경우 완전그래프일 경우 edge의 개수는 m=n(n-1)/2. 따라서 시간복잡도가 (n^2lg n)

Greedy method를 사용해서 값을 구하면 이게 정말 optimal solution인지 확인해야 한다.


2. Prim algorithm 
마찬가지로 탐욕적인 방법.
set A는 언제나 하나의 tree이다.(Kruskal은 forest)
set A와 연결되는 light edge 구하기. set A와 나머지를 나누는 선을 긋고, 그 선을 지나는 최소 edge중 하나가 light edge.
root vertex에서 시작한다.

구현
Minimum spanning tree를 A라고 하자.
모든 노드를 우선순위큐에 넣고
최소 key를 가진 vertex를 꺼낸다. (처음에 초기화할 때 루트의 key가 0이고 나머지는 다 무한대로 설정해서 처음에 루트가 꺼내져서 A에 들어간다.) 꺼낸 vertex(u)의  인접 vertex(v) (큐에 아직 남아있는 것)만 탐색하여 v의 키값이 (u,v) edge의 weight 값보다 크다면 key값을 weight 값으로 변경한다. 그리고 부모노드를 u로 설정한다. 큐가 비워질 때까지 이 과정을 반복한다.

성능
큐에 vertex가 없을 때까지 while문 반복, |V|번. (V는 vertex수)
큐에서 최소값 뽑는 것이 O(lg V).
while 다 돌면 큐에서 모든 vertex를 뽑으니까 O(V lg V) ----------1번

그래프의 인접리스트의 총 edge 길이는 2|E| (undirected graph, E는 edge 수)
그래서 큐에서 vertex 뽑고 그 vertex의 인접리스트를 탐색하는 거 O(E).
탐색 과정에서 vertex가 큐에 있는지 확인하고 있으면 key값 변경하고, 부모노드 설정.
큐에 있는지 확인하는 것은 vertex에 bit하나를 할당하여 큐에 있는지 없는지 상태를 나타내면 큐를 다 뒤지지 않고도 상수시간에 큐에 존재여부를 확인 할 수 있다.
부모노드 설정도 상수시간.
그리고 key값 변경하는 것은 min-heap에서 Decrease-key랑 같은거다.(key값 변경하고 min-heap이 유지되도록 변경된 vertex의 트리에서의 위치를 찾는 것) O(lg V)이다.
따라서 인접리스트 탐색하면서 key값 변경하는 시간은 O(E lgV) ----------2번
1,2번에 의해 total time은 O(V lg V + E lg E) = O(E lg V)

Fibonacci heap을 통해 성능향상을 할 수 있다.

Greedy method를 사용해서 값을 구하면 이게 정말 optimal solution인지 확인해야 한다.

참고사이트
http://myungkyoonyim.tistory.com/entry/Minimum-Spanning-Trees
강원대학교 Greedy Method 강의자료

그래프는 vertex(node) set과 edge(link) set으로 구성되어 있다.

directed graph
directed graph는 방향이 있는 edge를 사용하는 그래프.
한 vertex가 어떤 edge의 끝점일 때 그 edge는 그 vertex와 incident하다고 한다. 
self-loops - 자기자신한테로 가는 edge.
edge는 vertex의 순서쌍으로 표시할 수 있다. (예 : E= {(1,2), (2,2)}, 숫자는 vertex)

undirected graph
방향이 없는 edge 사용
방향이 없으니까 Edge (u,v) 는 edge (v,u)하고 같다.
self-loops가 없다.
Adjacency - 두 vertex 사이에 edge가 있을 때 둘이 adjacent 하다고 한다.

Degree
out-degree 자기로부터 나가는 edge의 수
in-degree 자기로 들어오는 edge의 수.
한 노드의 degree는 out-degree + in-degree
undirected graph에서는 in, out degree가 없다. 그냥 한 vertex에 incident한 edge의 수를 degree라 한다.

Path
한 vertex서 다른 vertex까지 가는 길. edge를 지나는 vertex들의 집합으로 볼 수 있다.
path의 length는 path안에 있는 edge의 수.
한 vertex에서 다른 vertex까지의 path가 있을 때 두 vertex는 reachable하다라고 한다.

Simple path
같은 vertex를 두번 이상 지나지 않는 path.

Cycle
path의 시작 vertex와 끝 vertex가 같을 때.
사이클이 없으면 acyclic graph

Connected graph
undirected 그래프에서 임의로 2개 vertex를 선택하였을 때 path가 존재.

connected components
undirected connected graph을 모아논 graph

Strongly connected
directed graph에서 임의 두 vertex의 path가 있을 때

Strongly connected components
directed connected graph들을 모아논 graph

Complete graph
undirect graph의 임의 두 vertex가 adjacent할 때
edge 개수 : n(n-1)/2

Bipartite graph
undirected 그래프를 두개의 파티션을 나누는데, 각각의 파티션안에는 edge가 없고 서로의 파티션간에 edge가 있는 그래프. 

Forest
tree들의 모음
사이클이 없고, undirected graph

Tree
사이클 없고, connected한 undirected graph
사이클이 없으니까 두 vertex는 simple path가 하나밖에 없다.
edge 하나가 제거되면 graph는 disconnected가 된다.
edge 하나가 추가되면 graph는 사이클이 생긴다.
|E| = |V|-1

Dag
Directed Acyclic Graph

Handshaking lemma
모든 vertex들의 degree 합은 2*(edge 수). 왜냐하면 edge 하나가 vertex 2개의 degree를 만들기 때문.

Edge의 수

undirected graph
최대 |V|(|V|-1)/2. (완전그래프가 될 때)

directed graph
위에거에 곱하기 2에다가 self loop edge를 가질 수 있으므로 더하기 |V|. 계산하면 |V|^2이고 이는 최대로 가질 수 있는 edge 갯수이다.

그래프 구현방법

1. 행렬
vertex u, v에 edge가 있으면 행렬 M(u,v)의 값이 1, 없으면 0.
Θ(V^2) space, undirected graph이면 행렬이 main diagonal을 기준으로 symmetry하므로 Lower matrix만으로 충분.
2. 리스트
vertex별로 리스트 하나씩. adjacent한 vertex가 리스트의 노드가 된다.
Θ(V+E) space

그래프가 sparse 하면 행렬에 빈공간이 많으므로 리스트가 효율적, dense하면 행렬이 edge하나를 bit만으로 표현할 수 있으니 더 효율적.
모든 edge를 방문하고자 할 때 행렬은 존재하지 않는 edge도 방문한다. 리스트는 있는 edge만 방문한다.

edge에 값이 있는 weighted graph일 때는 행렬에 1대신에 weight값을 넣고, 리스트로 구현할 때는 각 노드에 weight 항목을 추가한다.

Transpose

main diagonal을 기준으로 대칭했을 때, 두 행렬이 같으면 transpose. 그래프로 봤을 땐 edge의 방향을 바꾸는 것. undirected graph는 바꿔도 변함이 없으므로 transpose이다.

Breadth-first-search

시작 vertex에서 거리가 가까운 노드부터 탐색.
탐색한 edge와 vetex들은 tree를 이룬다.
vertex들을 큐에 넣어 거리가 가까운 노드부터 탐색한다.
탐색여부는 색깔로 구분할 수 있다. 탐색안된것, 탐색중, 탐색완료.
모든 vertex는 최대 한번 탐색된다.
모든 edge는 최대 두번 탐색된다. 인접 vertex 찾아서 enqueue할 때, dequeue해서 인접vertex 찾을 때. 
수행시간 O(V+E), reachable 하지 않은 것이 있어서 Θ가 아님.

Depth-first-search

이것도 vetex에 색깔을 넣어 탐색여부를 알 수 있다. white는 탐색안한 vertex, gray는 탐색중인 vertex, black은 그 vertex의 모든 인접 vertex를 다 조사하고 끝난 vertex.

Parenthesis theorem
한 노드가 gray인 기간. 노드가 탐색이 시작되고 끝날 때까지의 기간.
자식이 끝나야 부모가 끝나기 때문에 시간간격이 부모가 자식을 포함하고, 겹쳐 지는 경우는 없다.

edge의 분류

tree edges
depth-first-forest(depth-first-search를 하면 트리들의 집합이 만들어진다)의 edge들
(u,v) edge에서 v가 white인 edge. 

back edges
depth first tree에서 자식에서 조상으로 가는 edge, self loop도 back edge.
(u,v) edge에서 v가 grey인 edge

Forward edges
조상에서 후손으로 가는 edge
(u,v) edge에서 v가 black인 edge (cross edge일수도 있다. u,v가 포함관계가 아닐 경우.)

cross edges 
다른 depth first tree에서 온 edge

 
undirected graph일 때, depth-first search하면 모든 edge는 tree edge이거나 back edge이다.
forward edge는 back edge가 되고(자식 노드에서 먼저 edge를 탐색하기 때문에)
cross edge는 tree edge가 된다. (unconnected 였는데 connected가 되기 때문)

running time : Θ(V+E), list로 구현했을 때.

스택을 사용한다.

Topological sort

그래프가 DAG(엣지방향이 있고 사이클이 없는 그래프)일 때, 모든 엣지를 왼쪽에서 오른쪽 방향으로 되도록 vertex를 일렬로 배열 할 수 있다.

출처 : homepages.ius.edu

 사이클이 있으면 불가능. no back edge. right에서 left로 가는 edge가 있기 때문이다.

 in-degree가 0인 vertex를 왼쪽부터, out-degree가 0인 것을 오른쪽부터 둔다.
Depth first search를 돌려서 finish time이 빠른 vertex부터 맨 오른쪽부터 놓는다.

 

          meal = breakfast; break;
case : 10~15
          meal = lunch; break;
case : 17~21
          meal = dinner; break;
}
meal();
}
왜 쓰는가?
코드가 유연해진다. 코드 중복을 피할 수 있다. C로 객체지향을 구현할 수 있다.(추상화)