Cpace

관계 데이터 모델의 개념
 relation : 2차원의 테이블 (스프레드 시트와 유사)
 record : relation의 각 행
 tuple : record를 좀 더 공식적으로 부르는 용어
 attribute : relation에서 이름을 가진 하나의 열
 domain : 한 attribute에 나타날 수 있는 값들의 집합. 프로그래밍언어에서 데이터 타입과 유사. 동일한 도메인이 여러 attribute에 사용될 수 있음. 도메인 정의 ex) CREATE DOMAIN EMPNAME CHAR(10); CREATE DOMAIN EMPNO INTEGER
 degree : 한 relation에 들어있는 attribute들의 수. 유요햔 relation의 최소 degree는 1.
 cardinality : relation의 tuple 수. 유효한 relation의 최소 cardinality는 0.
 relation schema : relation의 이름과 relationdml attribute들의 집합. relation 이름 (attribute 1, attribute 2, ..., N) -> 기본 키에는 밑줄을 그어 표현. intension이라고 부름.
 relation instance : relation에 어느 시점에 들어있는 tuple들의 집합. 일반적으로 relation에는 현재의 instance만 저장됨. extension이라고 부름.
 relation key : 각 tuple들 고유하게 식별할 수 있는 하나 이상의 attribute들의 모임.
   - super key : 한 relation 내의 특정 tuple을 고유하게 식별하는 하나의 attribute 또는 attribute들의 집합.
   - candidate key (후보키) : 각 tuple을 고유하게 식별하는 최소한의 attribute들의 모임. 모든 relation에는 최소한 한 개 이상의
     후보키가 있음. 후보키도 두개 이상의 attribute로 이루어질 수 있으며 이런 경우 composite key(복합키)라 부름.
   - primary key : 한 relation에 후보키가 두개 이상 있으면 설계자가 이들 중에서 하나를 primary key로 선정.
   - alternate key : 기본키가 아닌 후보키
   - foreign key : 어떤 relation의 primary key를 참조하는 attribute. relation들 간의 관계를 나타내기 위해 사용. foreign key
     attriibute는 참조되는 primary key와 동일한 DOMAIN을 가져야함.

Types of Scheduling
- Long-term scheduling : New 상태에 있는 프로그램들 중에 누굴 memory에 올릴지 결정
- Medium-term scheduling : suuspended 상태에 있는 프로그램들 중에 누굴 올릴지 결정
- Short-term scheduling : ready 상태에 있는 프로그램들 중에 누굴 올릴지 결정

Scheduler가 발생할 때
1. 누가 와서 내 프로세스를 뺏어갈 때 (preemptive), ready상태로 감.
2. 내가 자발적으로 프로세스 놓음 (nonpreemptive), blocked 상태로 감.

Scheduling 기준
- CPU utilization : CPU가 얼마나 바쁘게 일하는지
- Turnaround time : 프로그램을 실행시켜서 끝날때까지 시간
- Response time : 반응할때 까지 시간
- Waiting time : ready 큐에서 기다린 시간의 합

First-Come-First-Seved
 ready큐에 가장 오래 기다린 process가 선택된다. CPU-bound process (I/O보다 연산의 비중이 높은 프로세스)에 유리하다. nonpreemptive scheduling algorithm.

Round-Robin
 time-sharing system 과 비슷하다. clock에 기반한 preemption

Shortest Process Next
 실행시간이 짧은 거 먼저 실행 (프로세스 실행 시간을 다 알고 있어야 함). 우선순위 기반.

Shortest Remaining Time First
 남은 시간이 짧을 수록 먼저 실행 (이것도 실행시간을 추정해야 함). 우선순위 기반.

Replacement Policy : 어떤 page가 대체 (swap) 될 것인가? 대체되는 Page는 나중에 가장 참조될 가능성이 적은 애이다.

Basic Replacement Algorithms
- FIFO : memory에 가장 오래 있던게 대체된다.
- Optimal Policy : 제일 긴 시간 후에 사용될 page를 대체한다. 하지만 예측할 수 없으므로 사용 못한다.
- Least Recently Used : 가장 오래전에 사용된 page를 대체한다. 근데 시간을 저장하므로 시간, 비용이 많이 든다.
- Clock Policy : LRU와 비슷하지만 근사한시킨 알고리즘을 사용한다. use bit을 설정하여 0인 page를 대체한다.
 성능은 OPT > LRU > CLOCK > FIFO 순이다. (OPT는 현실적이지 않다.)
- Enhanced Clock Policy
 use bit과 modified bit를 pair로 참조한다. 최근 사용 여부와 내용 수정 여부를 확인했을 때 둘 다 (0,0)인 page가 가장 우선적으로 대체된다.

Trashing
- Degree of multiprogramming : memory에 있는 process의 갯수
 process의 조각이 필요하기 전에 그 조각이 swapping (대체)되면 page fault가 발생한다. process가 충분한 page를 갖고 있지 않으면 page fault rate가 높다. -> 낮은 CPU 이용률을 초래한다. OS는 multiprogramming의 degree를 높여야겠구나 라고 생각한다. 다른 process가 추가되고 process 당 memory frame이 적어진다.
 CPU 이용률이 증가함에 따라 degree도 늘어나다가 모든 process들이 page fault 당해서 CPU 이용률이 갑자기 낮아지는 상태 -> Trashing (processor가 user instruction 실행보다 swapping pieces에 대부분의 시간을 사용함)
 memory에 들어와있는 모든 process의 locality 크기와 working set size가 memory 크기보다 크면 trashing이 일어난다. 이에대한 해결은 memory의 process 수를 줄이는 것이다. -> Process Suspension

Page-Fault Frequency Scheme
 page-fault rate가 upper bound보다 크다는 것은 page-fault를 너무 자주 당한다는 것이다. -> 해당 process에 공간을 더 준다. (frame 갯수를 늘인다.)
 page-fault rate가 lower bound보다 작다는 것은 다른 process보다 page-fault를 적게 당한다는 것이다. -> frame 갯수를 줄인다. 다른 애들한테도 골고루 공간을 주기 위함.
 lower bound - upper bound 사이가 되도록 하는 것이 page-fault Frequency Scheme이다.

프로세스는 조각되어 들어가기 때문에 main memory에 연속적으로 들어갈 필요가 없다.

- Virtual memory의 이점
 main memory 크기와 상관없이 더 큰 process도 실행할 수 있다. 더 많은 process 들이 main memory에 올라온다. -> CPU가 노는 시간이 줄어든다.
 현재 실행 중인 process들이 다 I/O가 되어 blocked 상태이면 CPU가 논다. -> swapping이 제안되었지만 suspended로 보내는 것도 process를 디스크에 올리는 데 오래 걸림 -> VM이 제안됨. 조금씩만 memory에 올림.

- Program 실행
 1. OS가 program의 조각 조금을 main memory에 가져온다.
 2. main memory에 없는 주소가 요구되면 interrupt이 발생한다.
 3. OS는 해당 process를 block 시키고 디스크에 해당 부분을 가져올 것을 말한다.
 4. 디스크가 I/O 처리할 동안 OSS는 다른 process 실행하고 I/O 끝나면 Ready 상태로 간다.

Types of Memory
 - Real Memory : Main memory, 주소는 real address, physical address.
 - Virtual Memory :disk에 있는 memory, 주소는 virtual address, logical address.

- Paging
 fixed-sized pages로 구성된 process가 virtual memory에 저장되어 있다. main memory에 접급해야 하는 page들은 올라간다. 각 page는 main memory의 아무때나 위치할 수 있다. 
 Page table은 logical (virtual) address를 physical memory에 mapping할 때 필요하다.
 Virtuual address는 Page Number 20 bit + Offset 12 bit로 구성되어 있다. 해당 virtual address로 page table에 mapping 하여 Frame Number를 알아낸다. Frame Number 20 bit + Offset 12 bit로 구성된 physical address로 mapping 시켜 main memory에서의 주소가 나온다.

Page Table의 크기
 Page table의 단점은 VM에 따라 크기가 비례한다는 점이다. 너무 커지면 main memory에 안들어가진다. -> page table 자체를 여러개의 조각으로 나누어 쓰이는 것만 main memory에 올리자.
 - Two-Level Paging
    Virtual address에서 20 bit Page number를 p1(10 bit), p2(10 bit)로 나누다. p1이 outer-page table의 위치를 가리키면 그 안에
   page of page table이 있고 p2가 해당 table에서의 위치를 가리킨다. 즉, page table을 여러개 만드는 데 그 page table을 순서대로
   저장한 게 outer-page table이다.
- Translation Lookaside Buffer
    하지만 Page table을 읽기 위해 memory를 많이 읽어야하는 문제가 있다. 이를 위한 해결 방안이다.
    CPU에서 virtual address의 page number 위치에 있는 page number들과 PT Entries라는 영역으로 이루어져있다. PT Enteries는
   처음에는 비어져있지만 한번 access하면 해당 Page Number에 mapping 되는 Frame Number가 저장된다. 순차적으로 찾는게
   아니여서 오래 걸리지 않고 CPU에 저장되므로 memory를 거치지 않는다.
    이 buffer는 cache여서 PT Entry가 있으면 hit, 없으면 miss다.

memory 할당 및 할당 후 보호

요구사항
- Relocation : 프로세스는 실행하는 동안 다른 메모리 위치를 점령한다. 프로그램이 실행되는 동안 디스크로 swap 되고 다른 위치의 main memory로 반환된다.
- Sharing :  몇몇 process들이 memory의 같은 부분에 접근하는 걸 허용

Memory Partitioning
- Equal-size Paritioning : 모든 process의 memory를 똑같이 할당한다. 하지만 이러면 안쓰게 되는 부분(internal fragmentation)있다. 메모리 낭비.
- Unequal-size Partitioning : memory 공간을 효율적으로 할당할 수 있지만 시간, OS가 낭비 된다.
- Dynamic Partitioning : process 크기만큼만 할당한다. -> Internal fragmentation이 없어진다. 하지만 시간이 지날수록 빈공간이 생긴다. 빈공간의 합이 10M라고 프로세스 크기가 9M이 넋을 사용 못한다. -> external fragmentation이 발생한다. -> relocation (빈공간을 위로 올린다.) 하지만 관리가 복잡해지고 쓰고 안쓰는 공간을 알고 있어야 한다.

Buddy System
  Buddy System은 2^n 단위이다.
  요청 크기가 2^(u-1)초과 2^u이하이면 2^u만큼을 다 할당해준다. 해당 조건을 만족시키지 못하면 두 가족으로 나눈다. 이때 한
 조각이 buddy. 또, 두 조각 중 한조각만 나누어질 수 있음. Release될 때 해당 공간 회수하고 buddy가 비었으면 합치고 아니면
 그냥 끝남.

memory 주소의 타입
- Physical address : 실제 main memory 주소
- Logical address : memory가 사용하는 주소가 아니라 process가 사용하는 주소
- Relative address : 시작번지부터 얼마나 떨어져있는 지를 기준으로 이동.
- Virtual address : 32bit (1GB 커널, 3GB stack heap bss data code)

Instruction과 data의 memory binding
- Address binding : logical address를 physical address로 바꾼다. 세 단계에 걸쳐 발전함.
   1. compile time Binding : 컴파일 하고나면 시작 주소가 바로 있고 컴파일 한 process를 memory에 올리면
    Logical address == Physical address. 컴파일하는 user가 main memory의 상태를 다 알아야 한다. relocation이 안된다.
   2. Load time Binding : 컴파일 하고나면 프로그램 시작 주소가 $BA로 정의되어 있다. memory에 올리면 $BA의 값이
    지정되면서 Logical address == Physical address. relocation이 안된다.
   3. Execution time Binding : memory에 올리고 나서도 프로그램 시작 주소가 정해지지 않고 $BA이다. 실행할 때 binding된다.
    따라서 $BA값만 바꾸면 relocation도 가능하다. Logical address != Physical address

Paging : memory에 생기는 빈공간들에 Process를 조각내어 넣자. process의 조각들이 page
- Page Table
  각 PCB마다 page table 가지고 있다. Index와 Content가 있는데 main memory에 몇 번 frame에 각 process 조각 순서가
 있는지 저장되어 있다.

Segmentation
 program의 모든 segment는 똑같은 길이가 아니다. paging은 equal size fixed partitioning와 비슷한 방법이고 segmentation은 dynamic partitioning과 비슷.
 얘도 process를 조각내어 segment table에 size, 시작 주소를 저장하는 것이다.

Deadlock : 두개 이상의 process가 자원을 기다리는 데 일어나는 충돌. 각자 자원을 가지고 있는 상태에서 다른 거 요청할 때 일어난다.

 - Reusable Resources : 한번에 하나의 프로세스에만 사용되며 그 사용으로 고갈되지 않는다. ex. Processor, I/O channels, main memory, semaphore ...
    예제. memory 공간에 200KB의 가용 공간이 있다. 
     P1에는 80KB 다음 60KB를 요구하는 statement가 있다. P1에서 80KB를 요구하는 statement를 실행하고 (남은 메모리 120) context switch 일어나서 P2를 실행한다. P2에는 70KB 다음 80KB를 요구하는 statement가 있다. 70KB를 할당해주고 (남은 메모리 50) 80 할당하려니 못해주니까 P2는 blocked queue로 들어간다. 그리고 다시 P1으로 왔지만 여기도 60을 할당하지 못한다. 그래서 P1도 blocked queue로 들어간다. P2는 P1의 80이 풀어지길, P1은 P2의 자원이 풀어지길 계속 기다린다.
 - Consumable Resources : 한번 소비하면 없어지는 자원 ex. Interrupts, signals, messages ...
    Receive message가 blocking되면 Deadlock 발생 -> 서로 상대방이 자신들에게 신호를 주길 기다리는 상황.

자원이 요구될 때는 process -> resource, 자원이 할당될 때는 resource -> process.

Deadlock의 발생조건 (동시에 만족되어야 함)
1. Mutual exlusion => 오로지 자원은 프로세스 하나에만 배정되어야 한다.
2. Hold-and-Wait
3. No preemption => 남의 자원을 뺏으면 안된다. 우선순위가 높은 프로세스여도 뺏으면 안된다. 우선순위는 오로지 CPU 자원만 뺏을 수 있다.
4. Circular Wait => P1 -> Resource a -> P2 -> Resource b -> P1 ... 이런식으로 요구, 할당 관계가 circular 하게 연결된 경우.

Deadlock 다루는 방법
1. deadlock 에 들어가지 않게끔 사전에 방지 => process가 4가지 조건을 충족하지 않도록 한다. OS 입장에성 일하는 것이다.
2. deadlock에 들어가 recover
3. 아무것도 하지말고 내버려두기 (OS가)

Deadlock 예방 => 4가지 조건을 깨트린다.
 Hold and Wait  X : 처음부터 한꺼번에 자원을 받게 한다. 하지만 너무 가지게 되어 자원 낭비가 된다.
 Circular Wait X : 자원에 일련의 순서를 매겨서 낮은 자원이 높은 것을 요구할 수 없게 하는 것

Deadlock 회피 : 알고리즘을 돌려 자원을 파악한다. deadlock을 발생시킬 문제가 있다면 시작하지 않는다. (banker's algorithm)

Deadlock 발견 후 전략 : 다 죽이거나 하나씩 죽여보자.

CPU 하나가 여러개의 프로그램을 동시다발적으로 진행.

하나의 processor (CPU) 에 producer processes와 consumer process가 가동된다.
Producer/Consumer Problem
 하나 이상의 Producer가 data 만들고 buffer에 저장함. 하나의 consumer는 buuffer에서 하나씩 가져옴. 한번에 오직 하나의 consumer or producer 만이 buffer에 접근할 수 있다.
Producer/Consumer : Finite Buffer
 main memory에 shared memory 공간을 할당해 변수들을 저장한다. (shared data) -> 동시에 producers, consumer가 접근할 수 있다.
 - Producer Process

1	item v;
2	while (1) {
3		while (counter == BUFFER_SIZE);
4		b[in] = v;
5		in = (in+1) % BUFFER_SIZE;
6		counter++;
7	}

   4~6 부분은 critical section 이다. critical section은 shared resource에 접급하여 값을 변경하는 statement이다. 다른
  process가 critical section에 있을 때는 실행하지 않는다. -> 한번에 오직 하나의 program 만이 critical section에 있을 수 있다.
 - Consumer Process

1	item w;
2	while (1) {
3		while (counter == 0);
4		w = b[out];
5		out = (out+1) % BUFFER_SIZE;
6		counter--;
7	}

   현재 예시에선 consumer가 하나이다. 그래서 conumser내에서 쓰이는 out이 critical section에 포함되지 않는다.
  여기서 critical section은 5번째 줄이다. counter는 producer와 같이 값을 쓴다.

- Race Condition in a Uni Processor
   IPC using a shared memory
   Race Condition : 다수의 thread 또는 process가 shared data item을 읽고 쓰는 데 실행 타이밍에 따라 되어 경쟁한다.
   예를 들어, counter++;이나 counter--;를 실행할 때 mutual exclusion을 위해서는 atomic하게 실행되어야 한다. 일반적으로는
  한문장 실행하고 interrupt 확인하고, 한 문장 실행하고 interrupt 확인하고 ... 이렇게 실행된다. atomic 하게 실행한다는 것은
  끊김없이 한 문장 끝나고 interrupt이 와도 처리하지 않고 다음 문장을 실행하는 것이다. 
   그러니까 counter++을 lower language로 보면

load register, counter	(register <- counter)
increment register	(register <- register+1)
store register, counter	(counter <- register)

  이렇게 세문장이 나오는데 atomic하게 실행되면 이 세문장이 끊김없이 한 단위로 다 실행이 된다.
   Race Condition의 예시로 위의 Producer, Consumer 코드를 보자면,
  1. Producer가 buffer에 item을 넣고 counter를 5라 했을 때,
     load register, counter   (register <- counter=5)
     increment register       (register = 6)
  2. 이때 time slice 만료되어 (clock interrupt) CPU가 counsumer로 dispatch되었다.
     load reigster, counter   (register <- counter=5)
     decrement register      (register = 4)
     store register, counter (counter = 4)
  3. time slice 만료로 CPU가 다시 producer.
     store register, counter (counter <- 6)
   최종적으로 counter의 값이 4아님 6이다. 이러한 race condition이 일어나지 않으려면 mutual exclusion이 필요하다. (서로
  겹치게 실행되지 않아야 한다.)

- Race Condition 방지
 * critical section을 atomic 하게 실행한다.
   하지만 critical section이 긴 경우에는 그동안 interrupt을 막으므로 문제가 생길 수 있다.
 * critical section 주위에 fence를 만든다.
   atomic하게 실행하는 것이 아니라 겹쳐서 실행하는 것을 막는다. fence 안에 들어갈 수 있는 것은 하나의 process.

- Critical Section Problem
  n 개의 process들이 shared data를 사용하는 경쟁을 한다. 그리고 각 process는 그에 접근할 수 있는 critical section
 코드가 있다. 한 process가 critical section을 실행 중 일때 다른 process는 허용되지 않도록 확실히 해야한다.
  해당 문제가 이루고자 하는 것은 Mutual Exclusion (한 process가 critical section에서 실행 중일 때 다른 process는 접근하지
 못하게 하는 것), Progress (critical section에 process가 없을 때, 원하는 process가 알아서 critical section에 들어가는 것.),
 Bounded Waiting (critical section에 process가 있을 때 기다리는 것) 이다.
  * Software solution : critical section 전에 담장 역할을 하는 entry section, 후에 exit section 코드를 추가한다. process들은
   해당 수행을 동기화 하기 위해 변수를 공유한다. 하지만 코드에 문제점이 있어 Hardware solution 개발.
  * Hardware solution : OS 개발자가 testset이라는 특수한 함수를 만들어 critical section으로 묶고 atomic 하게 실행한다고
   지정함. 오래 걸리지 않음. 그래서 program에서는 critical section 전에 testset을 호출해 담장 역할을 한다 내가 들어갈 수
   있나 없나는 검사한다. 들어오면 critical section을 실행하는 데 이때는 atomic하게 실행하지 않는다. 어차피 하나만 담장을
   통과해서 실행하고 있는 것이기 때문. 하지만 Deadlock이 발생할 수 있다. P1이 critical section에 있는데 time slice 되어 새로
   생긴 P2를 실행하는 데 얘가 우선 순위가 더 높다. 그러면 section에 들어갈 권한은 없지만 CPU는 P2가 계속 가지고 계속
   서로가 기다리게 된다.

- Semaphore : 공유 자원을 써도 되는 지 확인해주는 신호
  Signaling을 위해 semaphore라는 변수가 사용된다.
  semWait(s)는 semaphore s 의 값을 감소시킨다.
  semSignal(s)는 semaphore s의 값을 증가시킨다.
  이 두 함수는 atomic하게 수행된다.
  semaphore를 바구니라 하면 바구니 안에 돌이 있어야 내가 공유 자원을 써도 되는 신호구나 하고 바구니에서 돌을 빼고
 (semWait)쓰면 된다. 다 쓰고 나면 바구니에 돌을 넣느낟. (semSignal) 그래서 돌을 빼려고 했는데 돌이 없으면 blocked 된다.
  semaphore를 쓰면 mutual exclusion, bounded waiting이 제공된다. 또한 P3가 CPU를 가지고 있으면 얘가 critical section에
 들어가는 것을 아무도 막을 수 없다. -> Progress 제공.
  * Synchronization Tool로써의 semaphore
   실행 순서를 맞춰준다. 예를 들어, 내가 항상 A가 끝난 후 B가 실행되도록 한다면 A의 끝에 semSignal(flat), B의 앞에
  semWait(flag)를 하면 B는 semWait가 끝나면 실행되므로 A가 끝나고 semSignal이 실행되기 전까지 실행이 안된다.

- Message Passing
 mutual exclusion을 강화하는 또 다른 방법.
 send(dest, msg), receive(src, msg)

File Systems : 파일을 관리하는 시스템. 물리적인 디스크에 논리적으로 끊어서 공간을 할당.
File System에는 FCB (File Control Block)이 있다. device file의 FCB는 device type 필드와 device number 필드가 있다. major number는 장치의 타입 (ex. terminal, disk), minor number는 장치의 단위들을 나타낸다.

- File Directory : 파일에 대한 정보를 담고 있다. basic information, address information (파일이 저장된 디스크 내의 위치값), access control information. 얘네는 PCB 에도 저장된다. 그러면 같은 정보를 두 군데에 저장하므로 문제가 생겨 FCB에만 저장을 하게 하고, Directory는 FCB를 가리키게 한다. (mapping)
    inoode : FCB of Unix/Linux, FCB 고유 숫자
    Directory는 계층적인 구조이다. 각 디렉토리마다 inode가 있다. 만약 최상위 directory의 inode에서 FCB를 보면 해당 파일의
   내용이 들어있는 block의 번호가 있다. 해당 번호의 data block을 보면 하위 디렉토리 inode 번호들이 있고, 해당 inode 번호를
   통해 또 하위로 타고 타고 들어간다.

Acyclic-Graph Directories는 한 파일을 다른 위치에서도 볼 수 있다. 즐겨찾기 개념. 파일을 가리킨다.

- File System Structure
 내가 하드 디스크를 파티션하거나 그럴 때 File Systme Structure가 만들어짐.
 Boot Block : OS를 메모리로 읽어오는 code.
 Super Block : file system에 대한 정보를 담고 있다.
 Inode List : inodes의 배열 (FCB list). FCB 하나는 128bytes.

파일 공간 할당 방법
- Contiguous allocation
 디스크에서 data block에 파일을 할당하는 데 만약 file A의 길이가 3이고,  block 2부터 할당된다면 연속되게 2, 3, 4에 저장된다. File allocation block에 start block number, length가 저장되어 운영체제가 어디서부터 시작하여 어디까지 할당시킬 지를 안다. 근데 이 방법은 파일을 수정하여 확장시키기가 힘들다.
 - Chained allocation
 4KB인 한 블러마다 4byte씩 공간을 만들어 다음 block number를 저장한다. start block number와 해당 파일의 길이 정보를 가지고 체인을 따라 간다. 근데 이 방법은 내가 파일의 끝을 읽는다 하면 처음부터 체인따라 읽어 끝으로 이동해야 한다.
- Indexed allocation
 File allocation table에는 각 파일마다의 index가 있다. 파일 하나당 index block을 할당해서 해당 index block에는 파일 data block들의 number들을 저장한다. index block을 읽고나면 파일의 내용에 곧바로 접근이 가능하다. 파일의 앞이든 뒤는 읽는 속도가 같다. external fragmentation이 없다. (안쓰이는 작은 공간이 생기는 현상이 없다.) 파일 크기가 늘어나는 걸 걱정하지 않아도 된다. 하지만 index block이 날아가면 모든 걸 잃어버린다.

디스크 전체의 빈 공간을 어떻게 관리할 것인가?
- Counting
 빈 부분 block의 시작번호부터 연속으로 비어있는 block의 갯수 기록
- Linked list (free list)
  chained allocation과 비슷하다. head가 빈 block 처음을 가리키고 그 다음 빈 block을 차례차례 next로 가리켜 linked list가 된다. 맨 앞의 것을 할당해주고 head의 주소만 바꾼다.
- Bit vector (bit map)
 n개의 block이 있으면 1bit씩 할당하여 bit[n]으로 어느 block이 비었는지 확인한다. bit[i] = 0이면 block i가 할당되어 있고 1이면 비어있다.

UNIX FIle Management : Indexed allocation 방법 사용.
   - Data Block Addressing
    indoe에 direct block 10개, indirect block 3개가 있다. direct는 파일을 직접가리키고 indirect는 single이면 2개만큼,
   double이면 3개, tuple이면 4개만큼 거쳐 파일을 가리킨다. 
    Directly accessed된 것의 크기를 구하자면 10 * 4KB(한 block 크기) = 40KB이다. single indirected + double + tuple도
   구하여 모든 block이 할당될 경우의 max size를 구하면 40KB + 4MB + 4GB + 4TB이다.

Linux Virtual File System에는 direct block 12개, indirect block 3개가 있고 Page Cache (Disk Cache)가 있다.

I/O Devices = Controller (명령어 전달)

IO Systems은 IO Management (kernel의 I/O subsystem), Device-driver interface (driver에 읽고 쓰기를 하면서 파일 시스템의 함수를 호출하여 파일 시스템에 근접한 interface), Drivers for specific HW devices로 구성되어 있다.

I/O Function
   - Polling

    모드 체인지만 한다. User program이 계속 실행되고 있어 context switch를 하지 않는다. pollstatus는 다했냐고
   주기적으로 계속 다했다는 status가 올 때까지 물어본다. 하지만 이것도 결국 Device Drvier의 함수를 실행하는 
   것이므르 시간이 지연된다. 이를 해결하기 위한 방법이 Interrupt-Driven I/O이다.

   - Interrupt-Driven I/O
    1. Process A가 I/O 요청 (user space)
    2. IO Management에게 요청 (kernel space)
    3. Device Driver -> Device 전달. pollstatus가 없고 명령 내리고 바로 process management 실행.
    4. Device Driver -> Process Management (kernel space) Process Management가 어떤 프로세스 실행할지
        선택
    5. context switch (user space)
    6. Process B가 실행되고 실행 중 A에서 입력이 끝남.
    7. Device에서 IRQ 보냄 (kernel -> user)
    8. IRQ 신호 받으면 바로 B는 kernel로 들어옴.
    9. Scheduuler에서 ready로 풀린 A가 우선순위 높다면 A 실행.
        (스케쥴러를 실행한 것은 B이다. 아직 커널이 B에 있다.)
    근데 만약 5. 하는 도중에 장치가 I/O 다 끝났는데 A의 우선순위가 더 높으면 B는 실행 못함. -> 이럴때는 polling

   - Directed Memory Access
    입출력이 되려면 Processor가 명령을 내리고 I/O의 데이터를 받아오면 이 값을 메모리에 넣는다. 항상 프로세서가
   일을 한다. 입출력문이 나오면 processor(CPU)가 CMA에 전달한다. DMA가 입출력에 관해 실행한다. 다 끝나면 
   CPU에게 interrupt하고 CPU는 그동안 user program을 실행한다.
    프로세서를 거치지 않고 바로 메모리로 간다.

   - Kernel IO Management
    Buffering : 문서 작업을 하다 프린트를 누르면 프린트 당시의 문서를 buffer에 넣고 그 이후에 문서를 수정해도
                     프린트 되는 건 buffer 속 문서.
    Caching : 속도 차를 해결하기 위함.
    Spooling : 프린트를 여러명이 했을 경우 프린트 될 문서는 buffer에, 나머지 대기 문서들은 spooling.

Kernel entry points는 Interrupt, Trap (software interrupt), System call이다.
CPU가 체크해서 I/O event를 동기화시키는 것은 Interrupt, Polling, DMA.

- Interrupt Handling
    kernerl 함수 호출 -> mode change. 현재 저장하던 register 정보를 Kernel stack에 저장.
   ISR 실행하다가 interrupt 또 걸리면 새로운 애 먼저 ISR 실행하고 이전 꺼 다시 실행. kernel stack에 있기 때문에
   이어할 수 있다.

- Trap Handling
    div_by_zero, invalide machine code, page fault, segmentation fault

- System Calls Handling
    함수들의 주소가 있는 테이블, IDT에서 0x80이 system_call()이다. 이를 참조.

Disk Scheduling
 운영체제가 하드디스크에 저장하는 단위는 block이다.
 회전하는 디스크를 disk arm의 head가 읽는다. track 한 줄 씩 완주하는 데 track의 단위 sector마다 읽으며
정보를 읽는다. 
 Seek time : arm이 현재 읽어야하는 sector가 원하는 track으로 이동하는 시간. 제일 많이 걸린다.
 Rotational Delay : 디스크가 회전하며 sector가 head 밑으로 오는 데까지 걸리는 시간.
 Data transfer : head가 sector의 정보를 읽어 들이는 시간.

Disk Scheduling의 의의는 seek time을 줄이는 것이다.
   - FIFO
    온 순서대로 track 번호를 찾아 arm이 이동한다. 오래 걸림.
   - SSTF (Shortest Seek Time First)
    현 arm 위치에서 가까이 있는 track 먼저 읽는 것이다. 근데 얘도 '거리'에 따른 우선 순위 기반이여서 우선 순위
   낮은 애한테 starvation 현상.
    -SCAN (Elevator Algorithm or Look policy)
    방향을 정해서 한 방향으로만 쭉 간다. starvation 현상이 없다.

RAID (Redundant Array of Inexpensive Disks) : 데이터가 분산된다.
   - RAID 0 : non-redundant
   - RAID 1 : mirrored, 똑같은 거 백업.
   - RAID 3 : 데이터를 바이트 단위로 나누어 디스크에 동등하게 분산한다.
   - RAID 4 : block-level parity. 데이터를 block 단위로 나눈어 분산한다. RAID 3하고 비슷하지만 RAID 3은 모든
                   디스크를 읽어야 한다. 얘는 디스크의 멤버(block)마다 독립적. parity를 계산하여 parity만 저장하는 디스크 하나.
   - RAID 5 : block-level distributed parity. RAID 3, 4에서 별도의 parity 디스크를 사용함으로써 생기는 문제점 보완.
                   만약 1개의 하드가 고장나더라도 남은 하드들을 통해 복구한다. parity 정보를 stripe로 구성된 디스크 내에서 처리한다.
   - RAID 6 : dual redundancy. RAID 5에서 다른 드라이브들 간에 분포되어 있는 2차 parity 정보를 넣어 2개의 하드에 문제가
                  생겨도 복구 가능.
   - RAID 01 : (RAID 0)
                                     > RAID 1 = RAID 01.  양쪽 RAID 0 구성 중 하나씩 고장나면 전체 손실.
                      (RAID 0)
   - RAID 10 : (RAID 1)
                                     > RAID 0 = RAID 10.  
                      (RAID 1)

- Disk Cache (buffer cache)
 디스크 sector를 위한 main memory 안의 buffer. stack.
 최근에 자주 쓰인 sector copy가 stack의 top. buffer 공간에 다차면 최근에 자주 쓰이지 않는 걸 비운다.

커널에 프로세스 생성을 요구할 때 일어나는 일
1. 새 process의 PCB data structure 생성
2. child process에게 PID 부여
3. PCB의 value 설정
4. linkages 설정 (가족들끼리 연결)
5. 다른 data structure 생성 또는 확장
6. user context 생성 (부모 PCB로 복사한 data, stack은 child용 공간을 만들어 사용한다.)
7. child process를 Ready 상태로 설정하고 Ready Queue에 삽입
8. parent process에게 child의 PID 반환하고 child에게 0줌.

Context switch (Process Switch)를 할 때,
1. 프로세스 종료
2. time slice 종료
3. Blocking System calls
4. I/O interrupt

Context switch 단계
1. program counter와 register를 포함한 process의 context 저장
2. Running 상태에 있는 process의 PCB update
3. PCB를 ready 또는 blocked 또는 ready/suspend queue로 이동
4. 그 다음 실행할 process 선택 (by scheduler)
5. 선택된 process의 PCB update (ready -> running)

프로세스가 죽을 때, exit() 함수 호출을 통해 죽는데 이 함수는 커널 모드에서 동작한다. parent process에게 signal을 보내고 parent process가 wait() 함수 호출을 통해 child의 PCB 정보를 넘겨받을 때까지 child의 PCB는 남아있다.

- Cooperating Process
    다른 process의 실행에 영향을 받을 수 있다. -> 분산 시스템
    Interprocess Communication (IPC) for the information sharing -> message passing, shared memory, remote procedure call
    message passing : process마다 message 공간이 있고 커널을 통해 message를 주고 가져온다. 하지만 커널에 가기 위해 system call을 실행하는데 mode change에 시간이 걸림.
    shared memory : 공유된 메모리에 process A가 메시지를 주면 process B는 그 메모리에서 읽어오는 형식. 빠르지만 메시지를 여러 개 보낼 때 shared memory가 하나라면 overrupt 된다.
    cooperating process의 동시 실행은 동기화된 메커니즘이 필요하다. 그 중 하나가 Signal ex. SIGKILL, SIGINT, etc ->얘가 IPC

Threads

- process의 특징
    Resource ownership : process image를 유지할 virtual address space를 포함한다.
    Execution and Scheduling
    위 두가지는 OS와 독립적으로 다루어진다.
- Threads
    process의 실행의 unit (by a group of instructions)
    execution state (running, ready, etc)를 가진다.
    stack, memory for registers context

- Multi threading
    process는 동시에 실행 가능한 threads들로 나누어진다. (각 thread마다 registers, stack은 있고 code, data는 공유)

- thread의 이점
    thread는 register와 stack만 필요 (미니 PCB) -> 그래서 만드는 데 적게 걸림.
    process를 switch 하려면 메모리 (code, data, file)도 바꿔야해서 시간이 걸리지만 thread switch 하려면 register, stack만 바꾸면 끝.

User-level thread : user space에서 thread 생성. 커널 입장에서는 process하나니까 single-thread가 됨. 여기서는 thread 하나 block되면 process 전체가 block 됨.
->이점 : kernel-level thread보다 overhead가 적음. user-level threads는 어떠한 OS 위에서도 실행 가능.
Kernel-level thread : kernel space에서 thread 생성. 여기서는 thread 하나 block 되며녀 다음 thread로 넘어감.
->이점 : blocking system call 호출하면 process의 모든 threads가 blocked. multithread는 multiprocessing의 장점이 없음.