지밍이 블로그

# Heap management

- Heap Structure

- allocation : malloc, new, free, delete 

- Free List : Heap의 사용가능한 공간을 linked list로 구성

- Free함수의 역할 : Free List로 반환되는 공간이 기존 가용한 공간과 병합이 가능한 경우는 하나의 큰 공간으로 병합하고 아닌 경우에는 새로운 포인터로 연결

- Fragmentation : allocation과 reverse의 반복과정에서 생기는 작은 메모리 hole

- fragmentation이 많이 발생하면 메모리할당을 제대로 수행할 수 없음

- Buddy Allocator, Slap Allocator

: http://jiming.tistory.com/131

- Buddy Allocator의 Free 

: 인접한 buddy 들이 가용 상태인 경우 이를 병합함으로써 쉽게 큰 크기의 가용한 메모리 공간을 확보할 수 있음

# Free List

- Lisked List, Bitmap

 Free List가 주어지면 런타임에 어떤프로세스가 메모리 요청을 했을 때 메모리 할당에 대한 정책

- 메모리 fragments를 줄이기 위해 메모리 할당시에 적용되는 정책

: Best-fit, First-fit, Worst-fit

- Best-fit으로 allocation하는 것이 항상 좋은 결과를 가져오지 못하는 이유

: 시간이 지남에 따라 First-fit, Worst-fit에 비해 작은 크기의 hole들이 생성되기 때문에 Fragmentation 문제가 더 심각해 질 수 있음

- Memory Pool

; uni 사이즈로 메모리 요청을 수행하도록 함

: 여러 사이즈를 메모리 노드들을 동일한 사이즈끼리 묶어서 관리(다양한 사이즈를 지원할 수 있음)

: but, 사이즈 별로 불균현의 문제를 가지고 있음

# Static  vs  Dynamic

- Static : execution 전, pre-runtime, offline, static analisys, 

- Dynamic : execution 후, runtime, online

- Static Allocation : 프로그램이 수행되기 전에 미리 메모리를 할당하는 것 (Code(text) Segment, Data Segment)

변수의 lifecycle이 프로그램의 시작과 끝에 일치하는 것

- Dynamic Allocation : (Stack Segment, Heap Segment)

*Activation Records(Stack Frames/Acivation Frames) 

: 프로시저가 수행되기 위해 필요한 정보들을 저장하고 관리하기 위해 stack에 저장되는 데이터 구조

: 라이프사이클은 해당되는 함수가 시작되고 수행이 끝날 때까지임

: 함수 호출과 리턴은 Stack의 push, pop operation과 정확이 매칭됨

# Memory Manager

- Dynamic Storage Allocation, Heap

- Demanding Paging

# Linker and Loader

* .c (source file) -> Compile -> .o (object file)-> linking -> executable file -> memory loading -> executing

* object file 

: instructions, datas, address 정보, symbol table(프로그램에서 사용하는 symbol들에 대한 정보를 저장하는 자료구조), 링커가 프로그램 링킹을 위해 사용하는 정보(relocation table)

* Compiler : 소스파일을 오브젝트 파일로 변환

* Linker : 여러개의 오브젝트 파일을 하나의 실행가능한 파일로 변환

* Loader : OS의 한 부분으로 (fork, exec) 메모리에 프로그램을 로딩

# Section

: 오브젝트 파일을 구성하는 유닛. 어떤 데이터를 묶어둔 단위. text(code, instructions), datas, symbol table ...

- type이 각 section마다 다를 수 있음. 

- 각 section은 메모리에 저장이 될 때 독자적인 영역을 가짐짐 => segment 

<Object file의 Section 종류>

- Text Section : code, instructions 

- Data Section : 초기화된 전역변수

- BSS Section : 초기화 되지 않은 전역변수 (Block Started by Symbol)

=> 전역변수를 Data Section과 BSS Section을 구별하는 이유 ? 

초기화된 변수는 실제 메모리도 디스크상이지만 공간을 잡아야 하지만, 초기화 하지 않은 변수는 실제공간은 할당하지 않고 사이즈 정보등만 저장

- Other Section : symbol table, relocation table, ...

# Linking Process

<linking 과정의 문제점 - compiler가 주는 문제>

- 마이크로 프로세스는 프로그램을 수행할 때 symbol(함수명, 변수등)이 아닌 인스트럭션들의 op-code, operand 주소, branch의 target 주소를 보기때문에 symbol은 주소로 변환이 되어야 함. symbol을 주소로 변환하기 위해 실제 주소를 알아야 함.

* cross reference : 현재 파일에서 사용하고 있는 symbol이지만 다른 파일에서 주소의 위치가 정해진 symbol들의 주소

- cross reference를 알 수 없음 

=> 여러 파일에 흩어져있는 주소들을 모아야 하므로 한번의 Path로는 주소들을 모으기 힘들기 때문에 최소 2 path를 통해서 주소들을 모을 수 있음. 

=> symbol table : symbol들의 정보를 저장하는 테이블이며 엔트리는 각 symbol들이 됨(Symbol name, Section name, Section내의 Offset). linker가 수행

(같은 오브젝트파일에 들어있는 symbol의 주소는 당연히 알 수 있지)

-  PC Relative Addressing : 현재 PC값에서 Symbol의 주소로 점프하는 주소. Relocatable Address

* Internal Symbol들에 대한 PC Relative Addressing을 하는 이유 : 전체 Section의 위치에 관계없이 PC로부터의 상대적인 주소는 변하지 않기 때문 

# Race condition의 방지

- 하드웨어적 매커니즘 : 인터럽트 enable/disable, 버스의 트랜잭션 기법들

- 소프트웨어 매커니즘 : semaphores, monitors

# Deadlock

: 여러 프로세스들이 concurrent하게 수행할 때 발생. 

<해결방법>

- prevention. 예방하는 방법

- detection and recovery. 증상을 최소화하는 방법

* Resource Allocation Graph : 프로세스와 자원사이의 관계를 나타내는데 사용하는 자료구조

box : 프로세스

rounded box : 자원

자원-> 프로세스 : 자원이 프로세스에 할당

프로세스->자원 : 프로세스가 자원을 사용하기를원하는 상황

- Resource Allocation Graph를 이용한 Deadlock 탐지 : Cycle이 존재하는 경우 Deadlock이 발생한 상황임을 알 수 있음.
        단, 자원을 관리하는 세마포어가 바이너리 세마포어인 경우만 반드시 Deadlock 발생

# Deadlock의 사촌들

- Deadlock : 리소스를 공유하는 프로세스들이 서로가 원하는 리소스를 분점하고 있기 때문에 더 진행하지 못하는 것. 리소스를 기다리면서 wating상태에 빠지므로 CPU 관점에서의 리소스를 낭비하는 경우는 없음. 

- Livelock : CPU 리소스를 계속적으로 사용하지만 아무일도 하지 못하는 상황   

ex. router나 DB Server등에서의 Receive Live Lock. 

* interrupt coalescing : 인터럽트발생 빈도를 줄이기 위해 여러번의 입력을 모아하서 한번에 인터럽트를 발생시키거나 일정 시간마다 한번씩 인터럽트를 발생

* 패킷의 우선순위 매기기

- Indefinite postponement : 프로세스 하나 혼자서 주로 발생. 절대 일어날 수 없는 이벤트를 기다리는 상황

# Deadlock의 발생

<필요조건 4가지>

1. Mutual exclusion : 리소스를 공유할 수 없음

2. No preemption : preemption(자신의 리소스를 포기하고 리소스를 전달해 주기)을 할수없는 상황

=> 1,2번은 resource의 특징이므로 어쩔 수 없음

3. Hold and wait : 자신의 리소스는 점유하고 있으면서 다른 리소스를 또 원하는 상황

=> 프로세스가 수행을 시작할 때 해당 프로세스가 필요한 리소스를 한번에 다 받게 하기

=> 현실성이 없음. 어떤 프로세스가 어떤 리소스를 얼마나 필요로 할 지 프로그램 수행전 알기가 어렵고, 안다고 하더라도 비 경제적 임(한번에 많이 할당)

4. Circular wait : 원하는 리소스의 패턴이 Circular하는 상황

=> 역시나 비현실적임. 프로세스들이 사용할 수 있는 시스템의 리소스들을 넘버링하여 한방향으로 리소스를 할당시킴

# Prevention and Detection

1. Banker's Algorithm

: 어떤 프로세스들이 리소스를 점유하고 있을 때의 상태를 2가지로 분류

- safe state : 시스템이 Deadlock 상태에 빠지지 앟는 상태

- unsafe state : 시스템이 Deadlock 상태에 빠질 가능성이 있는 상태

ex. 1997년 12월 24일 우리나라의 IMF 상황

- 새로운 프로세스는 자신의 최대의 resource need를 선언해야 함 (단점이기도 함)

- 어떤 프로세스가 리소스를 요청하면 safe state와 unsafe state를 판단하여 리소스를 할당하거나 wait state로 진행

- Notations

* n : 시스템에 존재하는 프로세스의 갯수

* m : 시스템에 존재하는 리소스의 갯수

- Available[1:m] : 어떤 리소스 i가 몇개있는지 표현

- Max[1:n, 1:m] : 프로세스 i가 j타입의 리소스를 최대 몇개까지 원하는지 표현

- Allocation[1:n, 1:m] : 프로세스 i가 j타입의 리소스를 몇개 받아서 있는지를 표현

- Need[1:n, 1:m] : Max - Allocation. 향후 몇개를 더 할당 받을 수 있는지를 표현

- vectors X, Y

- work array : 어떤 자원의 중간 계산 결과를 저장하고 있는 array

- finish array : 어떤 프로세스가 종료되었는지를 나타내는 boolean array

- Safety Check

step 1. work에 현재 사용가능한 리소스를 asign. finish array의 모든 값을 false로 설정(아직 어떤 프로세스도 끝나지 않음을 의미)

step 2. 현재 수행을 끝내지 않았고, 최대로 필요로하는 리소스를 모두 만족해 줄 수 있는 어떤 프로세스 i를 찾음

step 3. 프로세스를 terminate시키고 finish로 리소스를 반납하는 과정을 모든 해당되는 프로세스만큼 반복하여 수행

step 4. 모든 finish[] 엔트리 값이 true가 되면 끝

- Safety Check를 사용해서 resource grant을 수행하는 방법

step 1. Request array에 각 프로세스의 새로 요청하는 request를 기록

step 2. 어떤 프로세스의 request가 Maximum보다 더 많은 요구를 하게되면 요청을 받아주지 않음

step 3. Maximum 값보다 적은 상태라면 일단 satety check 알고리즘을 수행한 후 safe하면 요청을 들어줌 

=> banker's algorithm은 satety하게 구현하며 deadlock avoidance를 수행. 

=> 프로세스가 maximum request를 각 타입별로 관리해야하고 그걸 수행하기 위해 비용이 비싼 의사결정이 필요하고 deadlock avoidance를 할 수 없는 상황도 있음.

=> Deadlock Detection!!

# Banker's Algorithm을 변형

step 1. 현재 리소스 상태가 주어지면 termination이 가능한 프로세스들을 termination시키기

step 2. 남은 리소스들을 보고, 데드락 때문에 종료되지 못한 리소스들을 발견할 수 있음  

* Deadlock Detection 기법이 큰 주목을 받지 못한 이유

Personal Computer에서는 사용자들이 임의로 종료시키기 때문에 큰 문제가 되지않음.

Server에서는 일종의 watch dog을 사용하여 termination 시킴

* 경우에 따라서는 termination이 비용이 굉장히 비싼 경우가 있음

이럴때, CPR(check point resume)이라는 응용이 동작 중에 일정 시간 간격으로 응용의 모든 상태를 디스크에 저장하고 문제가 발생했을 때 저장된 응용의 상태를 사용해 응용의 수행을 재개하는 기법

# Process Synchronize

- Why? Process Interactopn

1. Process, Design time Entity, Independently Develop, => Modular Design

2. Degree of Concurrency

3. to share resources

- Non-reentrant code : 인터럽트 서비스 루틴과 프로세스가 함께 상호작용하며 돌게될때 올바른 계산 결과를 내지 못하는 코드 

* reentrant code : 여러 process들이 동시에 호출되거나 이전 호출이 완료되기 전에 반복 호출되어도 올바르게 수행되는 코드

- Atomic Operation : share하는 resources를 atomic하게 만들어야 함. 소프트웨어적만으로 구현하기엔 매우 복잡하므로 일반적으로 하드웨어적인 서포트가 필요

=> 인터럽트를 disable시키기. (process와 interrupt  서비스 루틴 사이). context switching이 발생하지 않음. 

=> single processor에서는 인터럽트 disable이 만병통치약

- syncronization 문제 : 서로 상호작용하는 프로세스들이 리소스를 공유할 때 OS차원에서 공유되는 자원들을 관리하지 않으면  correctness 문제가 생김

- Race Condition : 경합조건. 여러 프로세스들이 동기화 절차를 거치지 않고 동시에 자원을 사용하기위해 경쟁함으로써 그 수행 결과를 예측할 수 없게되는 상황

- Critical section

: 어느 코드 섹션을 atomic하게 만든 코드. 하나의 프로세서만 수행되는 구간. 

: Mutual exclusion : 한 프로세서가 크리티컬 같은 구간에 들어가면 다른 프로세서를 들어오지 못하게 방어하는 매커니즘

- Mutual exclusion

: 주어진 시간에 여러개의 프로세서가 진입을 원하더라도 언제나 하나의 프로세서만 허용. 

: 빈번한 발생이 발생하므로 성능이 중요함

: Mutex, Semaphore, Monitor 등

=> 인터럽트 disable을 시키는 것은 큰 job이므로 늘 사용하기에는 적합하지 않아  Semaphores가 등장

* Interrupt Disable을 사용한 Synchronization의 문제 : Interrupt Disable은 시스템 전체에 영향을 미치기 때문에 상관없는 프로세스의 수행도 방해받게 됨

# Mutex

: Locking Mechanisms

: lock을 가지고 있는 경우에만 공유자원에 접근이 가능하며 lock에 대한 소유권이 존재. 

# Semaphores

- Semaphore Mechanisms

- 1970년대 Dijkstra로부터 고안된 fusion mechanisms

- syncronization을 제공해주는 정수형 변수

- API 

: lock(semaphore), = wait(s), = P(s)     => resource destroyed()

: unlock(s), = signal(s), = V(s)     => resource created()

- Synchronization 외에도 Scheduling, Control Transfer을 야기함

<세마포어의 종류>

: 세마포어는 동시에 리소스에 접근 가능한 Counter로 Counter의 갯수만큼 공유자원에 접근이 가능

- Counting Semaphore : 보호하려는 공유자원이 여러개인 경우의 세마포어. 초기값은 필요한 세마포어의 갯수만큼 필요

- Binary Semaphore : 보호하려는 공유자원이 한개인 경우로 0과 1의 값을 가지는 세마포어. 초기값은 1. (개념적으로 Mutex와 의미가 동일함)

- Block Semaphore : 초기값이 0, 인터럽트 서비스 루틴에서 V(s), 프로세스에서 P(s)

* Dining Philosophers : concurrency의 대표적인 예, Deadlock, Resources Sharing, Synchronize의 문제

# Semaphores의 단점

- unstructured programming construct이기 때문에 컴파일러 등의 도구를 사용한 디버깅이 어려움

*structured construct : 코드상의 pair된 구조. (ex. { } )

# Monitor

: Mutex(lock)과 Condition Variables(wating queue)를 가지는 Synchronization Mechanisms. 

- Semaphores 사용. but, Semaphores는 unstructured contruct이므로 이를 해결하기 위해 등장하게 됨

- Abstract Data Type 구조를 기반으로 구현하며 pair구조를 가짐

- Data와 Data를 처리하는 프로시저로 구성. 프로세스를 호출하여 사용

- 지정된 공유자원에 접근을 하기위해서는 모니터로 들어가야하며, 모니터 내부에 들어간 프로세스에게만 공유자원에 접근할 수 있는 기능을 제공

- 프로세스가 모니터로 들어가고자 할 때, 이미 다른 프로세스가 모니터 내부에 있다면 큐에서 대기

# Resource Scheduling 

<2가지 측면의 resource>

- preemptable resource : 양보가 가능한 리소스. 한 프로세스가 점유한 상태에서 다른 프로세스에게 양보가 가능한 자원.  CPU, memory...

- non-preemptable resource : 한 프로세스가 점유하면 사용을 마칠 때까지 다른 프로세스에게 양보할 수 없는 자원. printer...

<CPU 스케쥴링>

1. CPU를 어느 프로세스에게 줄 것인지의 문제

2. 얼마만큼 오래 CPU를 할당해 줄것인지의 문제

- CPU Bursts : 프로그램의 수행 중에 연속적으로 CPU를 사용하는 단절된 구간. 스케줄링의 단위. 

- I/O Bursts : 프로그램의 수행중에 I/O의 완료를 기다리며 블록되는 구간

*Batch Monitor에서의  Job :  한번 수행을 시작하면 수행을 완료할 때 까지 쭉 하는 것

Process : 끝나지 않은 여러개의 Job이 동시다발적으로 수행될 수 있음

- CPU Bursts Size

Burst Size가 큰 작업 : 과학기술 연산 등 CPU intensive한 작업

Burst Size가 작은 작업 : 터치패드 동작 등 I/O interactive 한 작업

- CPU Scheduling

1. 어떤 프로세스를?

2. 얼마나 오랫동안?

- CPU State Transition

: new, terminate, ready, running , waiting 

: ready -> running : dispatching(not scheduling)

: running -> ready : 하드웨어 인터럽트. OS의 스케줄러가 개입(preemptive scheduling)

: running -> waiting : 자기 스스로 CPU Yield하여 (non-preemptive scheduling)

: running -> terminating : non-preemptive scheduling

: waiting -> ready : preemptive scheduling

# Scheduling Policies

- Aging : 태스크가 CPU를 기다리는 시간에 비례하여 우선순위를 점진적으로 높여주는 기법

- Scheduling Objective

Maximize resource utilization, 의미있는 수행을 극대화시키기, CPU, I/O Device, ...

Minimize overhead

Minimize context switches

Distribute CPU cycles equitably, fairness =>FIFO, Priority, Aging ...

- Maximize Throughput, CPU intensive(background codex algorithms)

- Minimize Response time, foreground app

- Minimize Turnaround time 

- Minimize Waiting time 

* Response time관련의 예

: 아이폰과 안드로이드 젤리빈의 스크린 터치 스와핑

아이폰 : in-house OS로 스크린 터치 스와핑을 최적화

안드로이드 : 리눅스 OS기반으로 다양한 환경(Server, Cloud, Moblie,...)에서 사용하다보니 CPU intensive의 문제도 배제할 수 없어 최적화 시키지 못함

=> 여러가지 fake기술을 통해 극복 (백터 알고리즘을 미리 예측하는 기술 등)

# Scheduling Policies

- FIFO (First In First Out)

: CPU Burst 단위로 FIFO를 수행, preemtive scheduling, blocked의 단위로 종료

: Blocked이 일어나야 종료되므로, 한 CPU Burst안에 무한 루프가 있으면 CPU가 monopolized될 수 있음. => timeout 설정(RR)

: short time 작업에 대한 수행을 먼저 처리하지 못함

* CPU Burst : CPU 실행, I/O Burst : 입출력 대기

- SJF (Shourtest Job First) : Optimal Algorithm, 개념적 알고리즘임 

: SJF에서는 OS가 태스크의 남은 CPU Burst Size를 예측할 수가 없음. (burst size와 지난 예측 값 등으로 알파값을 구하여 CPU Burst Size를 예측을 하기도 함)

- preemtive SJF : re-scheduling, STCF(Shortest Time to Completion First) => 남은 시간을 계산

- non-preemtive SJF : no re-scheduling 

- RR (Round Robin)

: 기본적으로 FIFO수행, timeout 값까지만 수행하고 다시 ready-queue로 반환되고 다시 수행됨. => CPU Burst가 작은것 먼저 수행되게 됨

* Time Slice(Time Quantum) : time out 값, 태스크에게 CPU가 할당된 후 다음 스케줄링을 위한 timer interrupt가 발생할 때 까지의 시간

*work load의 패턴에 따라 FIFO가 RR보다 성능이 좋을 때가 있음

* Slide Switch 모델의 도입

: FIFO(or RR(TS=∞)) <----[switch]------> RR(TS=0)

=> dynamic한 algorithm이 필요하게 됨

=> "Adaptive Scheduling" : workload와 workload안에 있는 프로세스의 특성에 따라 Time Slice의 크기를 동적으로 바꿔주는 스케줄링 기법

CPU Bound Process의 요구사항 CPU utilization과 Throughput

I/O Bound Process의 요구사항 짧은 ResponseTime

- MLFQ (Multi Level Feedback Queue)

* Real-time System : 작업 수행이 주어진 시간안에 성공적으로 마쳐야하는 시스템. 비행기 항법제어 등등

=> priority 중요!

- Priority-based Scheduling : 프로세스드레게 선호도를 매기고, 선호도가 높은 프로세스를 먼저 수행하는 스케줄링 기법

반대로, gerneral performance program에서 priority-based scheduling이 알맞지 않은 이유

starvation : 수행할 준비를 마치고 CPU 할당을 기다리는 프로세스가 무기한 연기되는 현상

* 리눅스 2.4 ~ 2.6

- Fair Share Scheduling : Bandwidth Scheduling, Proportial Share Scheduling 이라고도 함

대기 중인 프로세스들에게 정해진 베율에 따라 CPU의 Bandwidth를 분배하는 스케줄링 기법ㅋ

* Performance Isolation : 어떤 CPU를 많이 차지할 것 같은 애플리케이션이 들어오면 그 애플리케이션의 영향을 격리시키는 것 (자동차 OS의 제어)

* 멀티미디어

=> Bandwidth Scheduling이 필요. (실제로, 리눅스에는 CFS(Completely Fair Scheduler)가 들어있음)

* rotating Staircase deadline  scheduler : CPU를 빼앗기면 큐의 맨 뒤로 가는게 아니라 자신의 데드라인에 따라서 큐의 중간, 맨앞, 맨뒤로도 갈 수 있음

제일 처음으로 Fair Share Scheduler로 채택

=> CFS, 리눅스의 기본 커널 스케줄러 - 리눅스 2.6.23 ~

# Process

:  OS위에서 프로그램을 실행시키는 기본 주체, 런타임 시스템의 수행 주체, 자원할당의 주체. 및 단위

: program in execution

:  An execution stream in the context of a particular process state

<process 구성>

- execution stream : 프로세스가 지금까지 수행한 모든 명령어들의 순서 

- process state : process의 수행에 필요한 정보. Context

1. Memory context : code, data, stack, heap

2. Hardware context : Register values(cpu registers, I/O registers, ...)

3. System context : Per-Process kernel information

- abstraction

- decomposition 복잡한 문제를  단순한 여러 개의 문제로 나누어 처리하는 방법론

- Multi-programming vs Multi-processing

Multi-programming : 메인메모리의 관점

Multi-processing : cpu의 관점

- swapping

<두가지 관점에서의 Process>

- Run-time entity vs Design-time entity

Run-time entity : 자원 할당의 주체

Design-time entity : 소프트웨어 개발에서 설계 단계에서 디자인 한 "set of tasks"들의 단위로 구현단계에서 구현하게 되면 프로세스단위의 프로그램이 만들어 짐

# Process의 구현

* Program = Data structure + Algorithm

Data structure

1. System context

2. Hardware Context

3. Memory Context

- Process Control Block : 프로세스의 정보. process id, process scheduling, ...

- Process Table : 여러 프로세스를 관리하기 위해 array 형태로 PCB를 저장하는 단위

-> easy to many-play, but OS가 지원할 수 있는 프로세스의 수가 한정적임 => linked list로 구현

- Process State Transition : 어떤 프로세스의 어떤 상황을 설정하는 것

-> process의 life-cycle : new - ready - running - waiting - Terminated

* ready queue : ready 상태의 프로세스들을 관리하기 위해 queue 형태로 만든 자료구조. 일반적으로 PCB를 linked list로 구현

* waiting 상태의 프로세스는 waiting reason에 따라 각각 다른 queue로 관리되어 짐

# Process Scheduling

: 각 프로세스들이 공평하게 CPU를 공유할 수 있도록 다음에 수행해야 할 프로세스를 선택하는 작업(Fair, Share)

- Process Scheduler의 2단계 구성

1. policy : 다음에 수행될 프로세스를 선택하는 기준. scheduling policy

2. mechanism : CPU를 한 프로세스에서 다른 프로세스로 넘겨주는 방식. dispatcher mechanism

- dispatcher : scheduler policy와는 무관하게 하드웨어 매커니즘으로 동작

program은 수동적, process는 능동적, OS는 능동적인 존재이지만 passive함,

OS 내부의 dispatcher는 굉장히 능동적인 존재임. 이렇게 생각하면 프로세서는 최소 2개가 필요. (dispacher가 도는 프로세서와 user program이 도는 프로세스)
하지만 싱글 프로세서 환경에서도 잘 동작함. 이유는????

=> CPU controller이 dispatcher(OS)와 user processor 사이에 컨르롤을 넘기면서 동작해야함. (인터럽트 매커니즘)

(Kernel mode <-> User mode,  mode changing, context switching)

# Context Switching

: 현재 프로세스의  state를 저장하고, 다음 수행 될 프로세스의  state를 불러오는 작업

* process의 state

1. process가 기억하고있는 모든 정보. Context를 표현할 때 (Memory Context, Hardware Context, System(kernel) Context)

2. Process의 State Transition 상태

- Context Saving. 저장해야 할 정보들

: 대피값들은 stack에 저장

1. CPU register들(다음 프로세스가 사용해야하니까), 

2. Memory 내용

- 전혀 저장하지 않는 경우 : 멀티프로그램드 배치 모니터 시절에는 여러잡을 한번에 배치로만든 후 메인메모리에 올렸으므로 CPU를 교체한다는 건 메모리자체를
 옮겨가는 것이므로 값들이 없어지지 않음

- 전부 저장해야하는 경우 : uni programming시에는 disk같은 장치에 메모리의 값들을 전부 저장. (rollin-rollout swapping)

- 부분적 저정하는 경우 : memory over-commit(degree of memory), swapping, memory hierarchy

* OS가 관리하는 Kernel data structure - 링크드리스트의 형태로 프로세스마다의 구조로 저장되므로 따로 저장하지 않아도 됨 

- Mechanism

1. 현재 인스트럭션의 수행 중간에 인터럽트 발생

2. 현재 인스트럭션의 수행을 끝낸 후 스택에 현재 PSW값과 주소(PC)를 저장 (->하드웨어의 support)

3. Process Status Word의 mode bit을 0으로 변경하여 kernel 모드로 변경

4. 마이크로 프로세서는 IRQ Number를 확인 한 후, 해당 number에 맞는 값을 인터럽트 벡터 테이블을 뒤진 후, 해당 인터럽트 서비스 루틴의 시작주소를 확인하여 점프

5. 인터럽트 서비스 루틴이 수행. 

: 인터럽트 서비스 루틴이 수행되면 초반에 CPU Register 값들이 우선적으로 stack에 저장된 후 인터럽트의 메인 로직이 수행됨

6. 인터럽트 서비스 루틴이 종료된 후 이전의 인스트럭션이 끝난 후의 주소로 돌아가야 함

- Stack Pointer register 

- OSPCBCur : OS 안에 존재하는 글로벌 변수 중 하나

OS : OS 변수

PCB : Process Control Block

Cur : Current, 현재 수행 중

=> 현재 수행중인 프로세스의 정보를 가지고 있음

- PCB : process identifier(id), Scheduling 관련 정보, Context Switching에 필요한 정보(Stack Pointer filed..)

- Interrupt

1. Stack의 top에 PSW, Return Address가 저장

2. 해당 인터러븥 서비스 루틴으로 점프

3. CPU register값들을 stack에 저장( intel : PUSHA, push all ) 후 인터럽트 루틴을 수행 (Context Saving 완료)

4. scheduler호출로 scheduler는 다음에 돌아야 할 프로세스의 PCB의 Pointer를 얻어와 OSPCBCur에 저장

- Stack Pointer Register value

: PCB의 SP 필드에 Stack Pointer값을 따로 저장해야 하는 이유는 stack에 값을 저장하면서 stack의 SP값은 계속 변하므로 돌아갈 SP의 값(저장해야 할 값)이 제대로 저장되지 않게 되므로 별도로 PCB의 SP 필드에 저장시킨다.

- Stack의 pop을 통해 저장한 값들을 cpu register로 들어옴

- 바뀐 stack의 값으로 새로 들어온 프로세스로 return

* fake stack

: 처음 프로세스가 수행될 때는 해당 매카니즘을 수행하기 위해 마치 인터럽트를 당한 것 처럼 PSW와 Return Address값에는 시작주소의 entry pointer값을 넣고 register의 값들은 0같은 값으로 셋팅하여 수행하게 됨

# Abstraction & Decomposition

OS의 Complexity 문제의 해결

- Abstraction : Layered Architecture

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

Software

Middleware

OS

(HAL, Hareware Abstration Layer)

H/W

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

*API, Application Programming Interface : 계층과 계층 사이의 통신을 위한 규격

- Decomposition

- Layer Principle : 위의 계층은 아레 계층이 제공하는 기능만을 사용할 수 있으며 반대의 경우는 발생하지 않아야 함(아래계층은 위계층에게 인터페이스 제공)

-> 레이어계층에서 윗계층에 종속적이라면 종속적인 것 외에는 받아들일 수 없어, 여러 상위 프로그램을 수행 할 수 없으므로

- Preemptive Scheduling : via HW interrupt. 어떤 프로세스가 하드웨어 인터럽트에 의해 CPU를 빼앗기게 되는 형태의 스케줄링. 

- Non-preemptive Scheduling : via SW interrupt.

# Process Creation&Termination

- creation : data structure allocation, (1970년대 ~ 현재)

<일반적인 프로세스 생성 개념>

1. file system에 대상 file의 path가 OS에게 전달

2. executable file의 code를 Memory Context의 code segment에 읽어들임

3. executable file의  global 변수의 값으로 data segment의 각 영역을 잡아 줌

(2, 3번 => 프로그램 "load"과정)

4. initially stack segment, initially heap segment

5. 실행될 프로세스의 PCB을 malloc으로 생성 후 값을 채움

6. 해당 PCB를 ready queue에 push

<unix에서의 프로세스 생성>

1. 첫번째 실행되는 프로세스만 일반적 과정으로 생성 (Process Zero만 이 과정을 수행)

2. 이후부터는 프로세스 생성을 복제의 과정을 통하여 생성

* Parent Process : Process Cloning을 초래하는 기존의 Process

- fork() 시스템 콜을 호출

- OS는 Parent Process를 일시정지 하여 Process ID를 제외한 모든 데이터를 복제하여 Child Process를 생성 

- Child Process의 PCB를 Ready Queue로 보내어 Run시킴

=> 클로닝을 통한 프로세스 생성에서의 문제점 : fork()만으로는 맨 처음 process외의 다른 Process는 수행할 수 없으므로 exec()이라는 another 시스템 콜을 호출

-  exec() : 생성되어 수행할 executable file의 path정보를 매개변수로 받은 후 실행을 수행

=> Parent Process : fork() -> wait(자신이 생성한 자식프로세스의 ID) 

Child Process : fork()로 copy가 된후 exec() -> exit() 

- -> exit code를 검사하여 parent process에서 확인하여 wait()에서 깨어나게 됨. 

* Zombi Status : 모든 수행을 마친 후 Parent Process가 자신의 exit code를 읽어가를 기다리는, exit status만을 가지고 있는 프로세스의 상태

# Multi-threading

- Server Architecture : Server <-> Message Queue/Request Queue

- Server Architecture 구현의 2가지 방식

- iterative server : 서버가 message queue에서 request를 가져와 스스로 처리하는 수행과정을 반복

- concurrent server : message queue에서 request를 가져오면 서버가 직접처리하지 않고 worker process를 fork하여 생성된 그 자식 프로세스가 해당 request를 처리하도록 하고, 서버 프로세스는 다시 message queue에서 다른 request를 가져와 또 다른 worker process를 만들어 처리하도록 하는 병렬적인 방식

- Concurrent Server

단점 : request를 받아올 때마다 새로운 프로세스를 fork하는 작업을 수행하므로 오버헤드가 큼

=> Concurrency를 높여 이런 단점을 극복하고, Execution Unit을 생성하거나 수행시키는데 부담을 줄이는 방안으로 Multithreading이 나옴

- 새로운 모델의 필요로하는 시대적 배경

: 1980년대 중반인 인터넷이 대중화되기 직전(인터넷의 대중화 1990년대)에서 여러 서버들의 개념 등장

: 과학 연산의 필요. 병렬적 처리 수요의 증가, 병렬 프로세스 수행이 필요

=> Multithreading이 필요한 이유

1. 적은 비용으로 Concurrency를 얻기위해(response의 agility를 높이기 위해)

2. Massively Parallel Scientific Programming을 할 때 발생하는 오버헤드를 줄이기 위해

- 장점

: 프로세스보다 적은 오버헤드로 작업을 수행할 수 있음

: 적은 시간, 적은 메모리 사용, 스레드컨텍스트 스위칭 등은 프로세스보다 효율이 좋음

: 반응시간이 더 빠름

- Thread Architecture

: 서버를 구현하기 위한 하나의 프로세스 - dispatcher thread - worker threads

- Traditional Process Model

: Process = Thread of Control(Execution Stream) + Context(Process에게 부여된 Resources)

: 프로세스에서 Thread of Control을 여러개를 두어 Thread(혹은 light weight process)라고 부름

: 하나의 자원을 여러 Thread가 공용으로 사용

- 하나의 프로세스는 여러개의 Thread를 가짐

- Thread는 Stack으로 구현. 이유? Thread는 Execution stream 이므로 function들이 sequential 하므로 Thread는 Stack으로 구현

- Multi Threading를 수행하면, 하나의 프로세스가 여러개의 스택을 가지게 됨

- 해당 각 스레드도 id와 해당 정보의 저장이 필요하게 됨 => Thread Control Block (TCB)

# Task : decomposition을 통해 설계하여 나온 독립적으로 수행가능한 Entity (Design time Process)

* run time process : 자원을 할당하고 수행시키는 주체들

- Mach OS에서의 task의 의미 : Proc = Task(프로세스에 부여된 리소스들) + Thread 

- 리눅스에서는 User level에서는 Process와 Thread로 구분, Kernel에서는 내부적으로 process와 Thread를 혼용하여 task라고 부름

# Multithreading 구현

1. User-level thread implementation : Kernel이 모르게 구현

- stack 구현

- TCB을 user-level에 각 Thread 마다 구현

- thread간의 switching, scheduling을 하기 위해 user-level에 scheduler를 함수들을 library로 구현

<user-level thread의 문제> 

- preemtive scheduling을 수행할 수 없음(이유는, 운영체제가 스레드에게 직접 인터럽트를 전달할 수 없기때문에)
    * non-preemptive scheduling은 가능

- 한 thread가 수행하다가 blocking system call을 호출하여 blocking system interrupt가 발생하면  커널이 해당 thread 뿐 아니라 다른 모든 thread가 blocking됨. (Blocking Anomaly)

<장점>

멀티스레딩이 처음 나왔을때, OS를 수정하지 않고도 멀티 스레딩을 적용할 수 있었음

: 단순 연산을 수행하는 작업을 할 때는 외부로부터 인터럽트를 받을 필요가 없기 때문에 user-level thread의 적용이 무방함

=> 구현이 쉽고, OS 코드를 안거쳐도 되고, 병렬 연산에 잘 매핑되어 사용이 되었음

2. Kernel-level thread implementation : Kernel이 100% 알게 구현

: task가 생성되고 소멸되는 것을 kernel이 알아서 해줌

thread creation, termination이 kernel system call로 구현하므로 인터럽트 포워딩도 가능.

<장점>

: user-level thread의 단점을 해소

<단점>

: kernel 단의 수행 시간이 증가하면서 추가적인 오버헤드가 발생(시스템 콜 시 발생하는 시스템 콜 핸들러 호출, 커널함수가 dispatcher, 커널함수 수행...)

3. Combined User-level/Kernel-level thread implementation 

: 상당 부분은 user-level thread에서 처리하고, preemptive scheduling이 가능하도록 user-level에 기법을 추가

- 인터럽트가 발생하면 인터럽트를 user-level thread에게 forward해서 어떤 thread가 깨어나야 하는지 알려주는 기법 추가

- 어떤 프로세스가 blocking system call을 호출하면 현 수행중인 스레드의 수행은 중단시키고, 새로운 커널스택을 할당 후 user-level process에 붙여 다시 리턴.

user-level의 스레드 스케줄러가 다른 스레드를 골라서 수행. 

# PThread Programming Model

- Multithreading API : POSIX pthread API 

* POSIX(Portable Operating System Interface) : 다양한 유닉스 계열의 운영체제들의 API를 표준화 하기 위해 IEEE가 정의한 인터페이스

1. pthread_create() : 스레드의 코드. 즉 함수의 function pointer를 매개변수로 사용

2. pthread_exit() : calling thread를 terminate

3. pthread_join() : 매개변수로 온 스레드가 terminate할 때까지 wait. (main thread)

4. pthread_yield() : CPU를 포기하고 싶을 때. (thread의 status가 stop)

- main thread

- thread life cycle

- 해당 API가 user-level thread에서는 library로 구현되고 kernel-level thread에서는 system call로 구현

# Compute System Architecture

- CPU, Memory, I/O Device

1. System interconnect

- 시스템버스 : 데이터버스, 어드레스버스스

- Bus Master :  Bus를 장악하여 read/write transaction을 수행 (CPU, I/O Controller, DMA Controller, ...)

- Bus Arista : 여러 Bus Master들이 버스를 장악하려 할 떄, 특정 버스마스터에게 권한을 부여하는 역할을 수행. 

버스 마스터로부터 버스 request signal을 받은 후 알맞은 버스 마스터를 선정하여 grant signal을 부여

- Bus Slave : 데이터를 담고있는 장치이며, 데이터의 주소 정보를 저장하여야 함 (메인메모리, I/O Controller안의 버퍼메모리나 레지스터들)

- Memory의 Address와 I/O Device들의 Address의 주소 형식은 같게 할수도 다르게 할수도 있음

: 빈 주소/공간의 메모리에 엑세스를 하면 메모리의 셀에 접근하지 않고 I/O Device의 레지스터에 정보를 넘기는 방식 등...

- Interrupt-Driven I/O : I/O가 완료되면 I/O Controller가 CPU에게 비동기적으로 완료됨을 알려주는 방식

- Polling I/O : 무한루프를 돌면서 I/O Controller를 체크하여 I/O가 완료되었는지 확인

- I/O Address : I/O Controller의 주소

- Port Mapped I/O : I/O Contoller의 레지스터들을 Port 레지스터라고도 함. 메모리와 디바이스 레지스터들의 관리를 별도로 수행.

디바이스 레지스터들을 위해 별도의 주소공간을 할애하여 Port Address Space를 가짐. Input/Output을 위해 별도의 매커니즘이 필요

- Memory Mapped I/O : 메모리 공간의 일부를 디바이스 레지스터들을 위해 따로 할당하여 관리를 수행

- DMA(Direct Memory Access)

: 일반적으로 사용하던 character I/O 방식은 1byte 전송시마다 인터럽트가 수행되므로 Block Data I/O 에는 맞지않음

: CPU가 DMA Contoller에게 Initation하려면, CPU는 메모리상에서의 데이터의 시작주소와 Block Data의 크기, read/write Command를 DMA Controller에게 전달

: DMA Conrtoller는 Bus 마스터로 버스를 장악하여 버스로 메인메모리에서 데이터를 가져와 자신의 버퍼에 저장하였다가 I/O 디바이스로 전송

=> CPU의 개입없이 I/O Controller가 메모리에 직접 접근하여 데이터 Read/Write 수행

- DMA가 Block 데이터를 I/O하는 두가지 방식

1. Cycle Stealing : cpu가 버스를 사용하고 있지 않을때만 DMA Controller가 bus를 사용하는 방식

CPU의 성능에는 영향을 주지는 않음

2. Block Transfer : CPU와 DMA Controller가 대등하게 경쟁하여 Bus를 장악하는 방식으로 CPU의 성능에는 영향을 줌

# Interrupt Mechanism

: Interrupt Driven Operating System

- 기본적으로는 하드웨어적인 매커니즘으로 처리되며, 대부분의 경우 비동기적 매커니즘

- CPU의 컨트롤이 Interrupt Service routine 함수로 넘어와 수행하게 됨

- 소프트웨어 인터럽트 : 컴퓨터 내부에서의 알림. Trap

- 소프트웨어 인터럽트는 발생할 시점을 미리 예측할 수 있어, 동기적 매커니즘이라고 함함

- 인터럽트 매커니즘의 세부 Operation

- 하드웨어 인터럽트

: 마이크로 프로세서에 인터럽트 시그널을 받을 수 있는 Pin이 존재해야 함

: 인터럽트 Sources (DMA Controller, I/O Controller 등..)

처리 1. PC에서 현재 마이크로 프로세서에서 수행중인 인스트럭션의 주소를 저장

처리 2. Pin을 통해서 인터럽스 시그널을 받으면 현재 수행중인 현 인스트럭션의 수행은 마무리하고 중단

처리 3. 시그널을 받으면, 마이크로 프로세서는 인터럽트 Source를 구별하는 Interrupt Request Number(IRQ)를 가지고 어떤 Source 인지를 판별

처리 4. 메모리상의 한 부분에는 Interrupt Vector Table이라는 처리해야할 인터럽트 핸들러 정보가 저장되어 있어(인덱스로 저장되어 있음), 

이를 참조하여 인터럽트 서비스 루틴의 주소를 확인하고 수행

처리 5. 인터럽트 수행이 종료되면 수행중이었던 인스트럭션의 주소정보를 가지고 다시 처리가 진행되게 됨

=> 인터럽트 Pin의 scalability의 문제로 Programmable Interrupt Controller(PIC)이 등장

- PIC : Interrupt Source와 CPU사이에 존재하여, 하나의 output 라인과 여러개(약 16개정도)의 input 라인을 가짐

        : PIC를 확장하여, 앞의 PIC의 input line 하나와 연결하는 식으로 캐스캐이딩하게 확장이 가능함

: Interrupt Source들의 프로그래머블한 제어가 가능함(PIC에 Interrupt Source들에 대한 1bit의 플래그를 이용하여 소프트웨어적으로 disable/enable 설정이 가능)

=> 16개의 Interrupt Sources가 있으면 16비트짜리 플래그 레지스터가 존재 => Interrupt Mask Register

: Interrupt Mask Register는 I/O Operation이 필요하므로 Mask Register의 port number(I/O Address)를 타겟으로 output 작업이 수행됨

즉 Interrupt Mask Register는 I/O Address Range에 속해야하고 Port number를 부여받음

# Hardware Protection Mechanisms

- Active Job들의 Multi 수행을 위해 Base Register, Bound Register의 값을 설정하여 메모리 상의 주소를 관리

- Privileged instruction의 구현

1. Basic Mechanism - Dual Mode Operation

: 두가지의 수행모드로 동작. Kernel mode, User mode

- Processor Status Regitster : 마이크로프로세서의 특정 상태를 나타내는 레지스터.

최근에 수행한 작업들의 내용을 플래그 기반으로 기억하여 다음 작업의 수행에 영행을 미치게 됨

해당 레지스터의 mode bit라고하는 한 비트를 사용하여 수행모드를 결정함(Kernel mode : 0, User mode : 1)

- Priviliged Instruction의 수행 

1. 작업을 patch

2. patch한 작업을 디코딩하는 과정에서 mode bit을 확인

3. 문제가 있을 시 trap으로 소프트웨어 인터럽트를 발생시킴

=> Kernel Mode : Priviliged Instruction의 수행, Memory Access에 대한 모든 권한

- 모드간의 전환 : 소프트웨어적인 처리로는 매끄럽게 해결할 수 없음. 하드웨어적인 인터럽트 매커니즘을 사용하여 mode bit를 바꿔주어 처리

커널 모드로 변하는 순간 모드 체인지를 관할 할 수 있는 인터럽트 서비스 루틴이 시스템을 장악

2. I/O Protection

: I/O 자원을 여러 Job들이 공평하게 혹은 효율적으로 나누어 쓰게하기 위해 I/O Protection이 이루어 져야함

3. Memory Protection

4. CPU Protection

: CPU 자원을 monopollize 하지않기 위해 수행시간을 할당해 줌. counter 등등

KVM/KSM

http://noon.tistory.com/581

계속 헷갈려서.. 한번 써봐야겠음

# 스토리지의 문제점 2가지

1. CPU나 Memory 속도를 따라가지 못해 병목현상 유발

2. 드라이브 고장 시 데이터 날림

=> "Fault Tolerance"를 높이고자 함

=> RAID로 해결

- Redundant Array of Inexpensive Disks

     or

- Redundant Array of Independent Disks (최근)

# DIsk Array 

: 여러 하드웨어 디스크를 배열로 하나 혹은 하나이상의 논리 드라이브로 구성

# RAID 구성 방법

- 하드웨어적 구성 : 레이드 구성을 위해서는 레이드 컨트롤러가 필요하고 레이드를 구성할 시 데이터 처리에 있어 부하가 걸리므로

                         별도의 어댑터 형태의 컨트롤러를 사용. 이런 레이드 컨트롤러에는 프로세서 및 메모리가 따로 있으며 가격이 비쌈.

                         어댑터 형태의 컨트롤러 외에도 메인보드에 내장되어 나오기도 하는데(SATA), 지원여부에 대한 사전확인이 필요.

- 소프트웨어적 구성 : 별도의 레이드 컨트롤러없이 소프트웨어적으로 레이드를 처리하여 안정성이 하드웨어적인 레이드 구성보다는 떨어짐

# RAID 0

: Striping, 데이터를 배열 드라이브에 분산시켜 저장

- 단순 round-robin 방식을 사용 (with out Fault Tolerance)

- 단순히 하나의 디스크로 보여지도록 만들어 줌

그림. 위키

- 최소 2개의 드라이브가 있어야지 적용이 가능

- 같은 모델, 같은 용량의 디스크 준수

- 데이터 분산방식으로 배열드라이브의 전체 용량이 하나로 통합

- 입출력 병렬처리로 인하여 속도 향상(RAID 구성 중 가장 빠른 속도)

- parity데이터를 저장하거나 미러링하지 않음. 즉 하나의 디스크에 문제가 발생하면 나머지 디스크에 저장된 데이터를 쓸 수 없음(복구 불가능)

# RAID 1

: Mirroring&Duplexing, 한 디스크 드라이브에 저장된 데이터를 다른 배열 드라이브로 복제

- disk mirroring을 사용하여 데이터 데스크에 저장된 모든 데이터들을 pair를 이루고 있는, 반사 디스크 같은 위치에 복사

- 거의 완변한 Fault Tolerance를 제공하지만 가격이 높음

- 신뢰도가 높은 시스템에서 사용

그림. 위키

- 2n개씩 구성

- 두개의 디스크에 똑같은 데이터를 저장

- 일정한 수준의 데이터 중복을 허용

- 하나의 디스크 고장시 복제된 데이터로 복구가 가능

- 일반적으로 입출력 성능이 저하됨. 

- HDD 사용시, 데이터에 더 가까운 배열 드라이브 헤더가 더 빨리 데이터에 액세스하므로 탐색 및 회전대기 시간이 줄어듬

- 구성한 디스크 용량은 하나의 디스크 용량과 동일(중복이므로)

# RAID 2

: Each bit of data word is written to a data disk drive

- 비트단위 인터리빙 방식을 사용 : 데이터를 각 디스크에 비트 단위로 분산 저장

- Hamming code를 이용한 오류 검출 및 정정 방식을 사용

단점! 필요한 검사 디스크들의 수가 많아서 가격이 비쌈

주요 용도! 오류가 많이 발생하는 환경에서 사용

=> 현재 거의 사용하지 않음

# RAID 5

: Parity, Striping, 배열 드라이브에 패리티 데이터 저장하여 데이터의 손실여부를 점검 할 수 있도록하며 RAID 0처럼 Striping 지원

- RAID 4의 문제점을 보완하기 위해 패리티 블록을 라운드-로빈 방슥으로 분산 저장

=> 병목현상을 해소하고, 쓰기 동작들의 병렬수행이 가능

- but, small write problem : 어느 한 블록만 갱신하는 small write의 경우 네번의 디스크 액세스가 필요하기 때문에 성능 저하가 발생

그림. 위키

- 최소 3개의 드라이브 필요

- striping 기능으로 성능을 향상하며, 패리티데이터를 저장하여 RAID 1처럼 일정수준의 중복을 제공

- ahems eltmzmdp voflxl wjdqh wjwkd

- 디스크가 고장이나도 데이터 손실은 없음

- 다시 복구하는데 오래걸림. 일반적으로 작은 용량에 추천

- 3개의 1짜리 드리이브를 RAID 5로 구성시. 2만큼의 용량을 제공

- 가장 널리 사용됨

* RAID 1과 RAID 5의 비교

- RAID 1 : 읽기와 작은 쓰기가 많은 환경에 적합하고 데이터를 완벽하게 보관할 수 있음

- RAID 5 : 용량과 비용면에서 보다 우수하고, 응용이나 큰 쓰기가 필요한 시스템에 적합함(가격대비성능 굳)

# RAID 6

: 패리티데이터를 모든 디스크에 저장하며 2차 패리티데이터도 저장

- 두개의 패리티를 따로 다른 디스크에 저장

- 데이터를 디스크에 나누어 저장

- N개의 데이터 디스크와 2개의 패리티 디스크가 필요

- 데이터 가용성이 높음

: 데이터가 손실되려면 3개의 디스크가 동시에 불량이 있어야 함

: 쓰기 문제가 심각해 짐

- 2개의 디스크가 고장이나더라도 복구가 가능

- 성능이슈 및 사용가능한 디스크 공간이 그만큼 줄어듬

# RAID 3, 4

: Parity, 패리티 데이터를 별도의 디스크에 따로 저장

 (하나의 데이터를 디스크 수대로 나누어 여러개의 디스크에 저장)

- 패리티비트 p = b1 XOR b2 XOR b3 XOR b4 (보통 짝수 패리티 사용)

- 최소 3개의 드라이브 필요

- RAID 3 : Byte 단위

- RAID 4 : Block 단위 (속도 장점)

- Parity Disk에 고장나면 복구가 불가능

- Disk 1,2,3 / Disk 4의 속도차이로 병목현상 발생의 가능성이 있음

=> 장점 : 병렬 데이터 read/write가 가능하여 디스크 액세스 속도 향상

단점 : write 동작 때마다 패리티 비트를 갱신할 필요가 있음

별도의 패리티 정보가 저장되어있는 패리티 디스크를 읽어야 하므로 여러번 액세스를 해야함

(원래 데이터 읽기, 원래 패리티 읽기, 새로운 데이터 쓰기, 새로운 패리티 쓰기) 

=> 디스크 수에 상관없이 한 블럭 갱신 시 네번의 디스크 액세스가 필요

# RAID DP(Double Parity)

: 1차, 2차 패리티데이터를 여러 드라이브에 분산으로 저장하지 않고, 2개의 드라이브에 패리티데이터를 저장

# RAID 10

: RAID 0, RAID 1 각각의 장점만 가지고 결합

- 4개의 드라이브 필요

- 2개씩 RAID 1로 구성(총 2개), mirroring이 되어 복구가 가능

- 2개의 RAID 1을 RAID 0으로 구성, RAID 1에 비하여 용량이 2배

- 용량 추가시에는 RAID 1을 더 추가

- RAID 1로 구성된 디스크가 고장나도 정상동작이 가능

- 용량은 줄지만 가용성이 높음

# RAID 0+1

: RAID 10과 반대, RAID 0으로 먼저 구성한 후 구성된 묶음들을 RAID 1 방식으로 mirroring 시킴

- Striping, Mirroring을 동시에 사용

- 속도와 안정성 

- mirroring의 이유로 RAID 10이 더 많이 쓰임

# 현재 테스트로 사용중이던 intel 서버에서 보드에서 RAID를 지원하지만 리눅스용 드라이버를 제공하지 않음.

그래서 BIOS에서 보드에서 지원하는 RAID 기능 부분을 disable 시키고 설치시 파티션 부분에서 software raid 0로 설정

[마이크로 커널 운영체제]

1. 마이크로커널 운영체제란?

# 마이크로프로세스의 수행모드

kernel mode <-> user mode

- kernel mode : OS의 모든 기능을 수행할 수 있음

- user mode : 대부분의 사용자 프로그램을 실행

멀티 프로세스를 지원하기 위함

# 운영체제의 2가지 종류

- 모노리틱 운영체제 : 모든 프로그램이 OS의 커널모드에서 수행되는 방식

os/360, Unix, VMS, MS-DOS, Linux, ...

- 마이크로커널 운영체제 : 운영체제의 최소 기능만 OS의 커널모드에서 수행되고 대부분의 기능이 user mode에서 수행되는 방식

Mach, Chorus, L4, Minix, ...

# Mechanism과 Policy의 분리

- Mechanism : 마이크로커널(커널모드)

  a. Thread Manager, 스레드 생성/종료

  b. IPC Manager ,  inter-process communication 여러 스레드, 프로세스 간 메시지 전달

  c. address space Manager : 주소공간을 생성 및 페이지 할당 등

  d. interrupt Manager : device는 policy를 사용하므로 micro kernel에 있지않고 user mode 쪽으로 존재. 이 드라이브를 micro kernel에 등록/호출 

- Policy : 서버프로그램들(유저모드)

  a. pager : 페이지폴트 처리

  b. device driver

그림 

b. 마이크로커널 운영체제의 변천사

- 1세대 : CMU에서 Mach OS 개발

개념이 너무 좋아서 많은 사람들이 굉장하였지만, 성능이 좋지않아 실망함 (사람들의 인식=>마이크로커널운영체제는 개념은 좋지만 성능은 별로)

- 2세대 : GMD의 Liedtke가 효율적인 IPC 구현 기술을 개발. 1세대 마이크로운영체제보다 수십배 빠른 마이크로운영체제를 만듬

굉장한 많은 복합적인 컴퓨터과학부분의 방법들을 적용을하여 Optimization 시킴

=> 성능향상 (개발자 왈 : 마크는 원래 개념도 좋고 성능도 좋다. 본디 최적회가 안되었을뿐)

- 3세대 :  수학의 logic과 프로그래밍언어의 sementics를 사용하여 formal verification 기술을 개발. (테스트가아닌 "증명"을 수행하여 신뢰할 수 있는 마이크로 커널을 만들게 됨)

=> 고 신뢰성을 보장. security, availability, reliability ...

2. 기본적인 특징 

: flexibility, safety, modularity

a. flexibility

: mechanism과 policy를 분리하여 유연한 운영체제를 구현. 모노리틱커널운영체제보다는 훨씬 쉽게 구현가능

- 하나의 microkernel 상에서 다수의 운영체제를 동시에 수행시킬 수 있음.

   ex. linux OS, windows OS

- 하나의 microkenel 상에서 다수의 정책을 쉽게 구현이 가능 ( 하나의 프로세스에 다수의 policy를 구현 )

   ex. 일반 paging, 멀티미디어용 paging을 동시에 적용 할 수 있음

- 어떤 file system 위에 다른 file system을 쉽게 구현 할 수 있음

   ex. stacked file system

b. safety 안전성

: microkernel과 server program이 분리되면서 microkernel 모듈이 굉장히 줄어들어 커널 자체가 가지는 안전성이 굉장히 높아짐.

: 대부분의 프로그램들이 server program에서 user mode로 수행이 되므로, OS의 한 부분에 문제가 생겨도 kernel이나 다른 서버에 문제가 생길 소지가 적어지게 됨(fault isolation)

c. modularity 모듈성

: 전체 OS가 작은 마이크로커널 + 다수의 서버프로그램으로 모듈화됨

:- os를 개발할 때 하나의 모듈을 개발 할 때 개발비용이 적어짐

- 모노리틱 커널에 비해 테스트가 용이

- 유지비수 비용이 낮아짐

- 운영체제를 재부팅하지 않고 file system 등 크리티컬한 프로그램도 쉽게 업데이트할 수 있음

3. 내부구조

# 마이크로커널 부분

a. thread manager

- thread_create, thread_exit

- thread scheduler : priority 기반의 round robin(scheduler는 policy가 있으므로 서버프로그램으로 구현하여야 하지만 성능의 문제로 아직은 micro kernel 내에 구현)

- data structure

: TCB(Thread Control Block), thread_id, thread_state, thread_quota, address_space(memory), kernel_stack(system call이 아예없지는 않기떄문인듯)

b. IPC(inter-process communication) Manager

: 시스템호출만 제공하여 두 스레드사이에 데이터를 주고받음

- synchronous IPC  : ipc_send, ip_resceive

- asynchronous notification: 데이터를 전달하는 개념보다는 어떤 이벤트가 발생했을 때, asynchronous하게 이벤트를 알려줌

  ipc_notify, ipc_getnotify, ipc_event 필요, 

* synchronous IPC + asynchronous notification

* 현재 microkernel에서는 synchronous IPC를 사용

why? microkernel 운영체제는 IPC 성능이 매우 중요

synchronous IPC를 제공하면서 많은 optimization을 적용할 수 있게됨

(synchronous IPC는 이미 많은 기술들이 발전했으므로 적용가능한 optimiza)

* asynchronous notification을 병행하는 이뉴? 마이크로커널의 성능을 높이기위해 

thread프로그래밍을 할 때 synchronous만 있는 경우는 너무 불편하므로 섞음

c. address space manager

- 모노리티커널의 메모리 관리자와는 완전 다름

- 최소한의 메커니즘만 제공

- as_create(address space create) : address space 생성

- as_map : 하나의 page 할당

- as_unmap : 할당받은 page 반환

- 사용하는 자료구조 

: AS, Address Space 구조제. AS구조체 내에 as_id와 page_table(물리주소) 필드를 사용

(* 실제 페이지를 바꾸는 처리나 page fault exception의 처리는 microkernel이 수행하지는 않고 "페이저"라는 서버프로그램이 담당)

d. interrupt manager

- system call : intr_register 새로운 디바이스 드라이버 등록, intr_unregister 등록된 디바이스 드라이버 해제

(device가 user mode에서 실행되는 서버프로그램이므로 인터럽트가 들어오면 어느 프로그램인지 알기위해 정보를 관리해야함)

- kernel interrupt handler : 인터럽트가 발생하면 실제 처리는 하지 않지만, 기본적으로 kernel로 올라오므로 등록된 디바이스 드라이버를 IPC로 호충

- 사용하는 자료구조

: IH, interrupt Handler 구조체. kernel_thread_id, device_driver_thread_id 등등

: Interrupt manager는 실제 처리는 안하고 인터럽트 종류와 처리할 프로세스간의 매핑 정보만 저장. 

ex) 인터럽트 5번은 인터럽트 스레드 50번에서 처리해

(-> Interrupt manager는 각 interrupt의 semantics를 알 지 못함, policy를 알지 않는다는 뜻)

# 서버프로그램부분

a. pager : page fault exception을 처리

- user_thread()에서 page fault가 발생하면, ipc_send(pager, faddr) 시스템 콜로 마이크로커널을 통해 pager_thread()에게 전달만 하게함

- pager_thread()에서 ip_receive(user, faddr)로 정보를 전달받음

- pager_thread()에서 kernel에게 as_map(faddr)시스템 콜을 통해 커널이 페이지매핑 요청만 하게함

- 다시 ipc_send(user, _)와 ipc_receive(pager, _)를 사용하여 마무리

b. device driver

- 인터럽이 발생하면 policy를 갖지않는 커널의 인터럽트 핸들러가 호출되어 인터럽트 처리는 하지 않고, irq 커널스레드를 통해서 처리해주는 thread와 맵핑. 실제 ipc 번호를 식별하여 인터럽트 처리 프로그램이 동작하게 됨.

# 결국, 마이크로커널운영체제에서는 모노리틱커널운영체제보다 ipc가 훨씬 많이 사용하게 된다.

4. 성능향상 기술

# 마이크로커널 운영체제에서 IPC

- 모노리틱커널운영체제 : function call

- 마이크로커널 운영체제 : IPC(IPC는 마이크로커널 운영체제에서 성능과 가장 많은 연관성을 가지고있음)

* 1세대의 microkernel은 IPC 성능을 향상시키지 못해 성능이 떨어졌다.

2세대의 microkernel은 IPC성능을 향상시키기위해 다양한 방법이 적용되었다.

현재의 microkernel은 모노리틱 커널과 거의 유사한 성능을 날 수 있음.

# IPC 성능향상 기술

a. Message Direct Transfer

: thread A에서 thread B로 IPC를 전달할 때, 주소공간이 다르므로 중간에 커널주소공간을 거쳐서 message가 복사된다. (2 copies)

-> 1 copy로 전환. Synchronous IPC와 temporary mapping을 사용. 

: 커널은 메시지 복사 전에 thread A의 주소공간 중 메시지가 있는 page를 thread B의 주소 공간에 임시매핑

- thread A의 message를 복사할 때,

- thread A의 message가 있는 page를 Thread B의 특별한 부분에 잠시 임시로 맵핑. 

- 커널이 그 사이 message를 copy

- 임시 매핑 해제

b. Short Message 사용

: 발생하는 수많은 IPC 중 50%-80%가 8bytes 이하의 짧은 메시지

: message를 메모리가아닌 register를 사용하여 zero message 기법으로 메시지 전달을 수행

(register는 어디에서나 접근이 가능하니까..)

c. Direct Process Switching

: thread A에서 thread B로 message전달 시, kernel의 스레드 스케줄러라는 또 다른 thread C가 수행되어 thread를 전환한 후 thread B가 수행됨

(thread A  ->  thread C(kernel의 스레드 스케줄러)  -> thread B)

=> 메시지 send/receive에서 성능저하가 나타남

: thread A에서 메시지 복사 후 스케줄러를 수행하지 않고(스케줄러를 무시하기), thread A의 남은 "time slice" 동안 IPC가 thread B로 컨트롤을 넘겨 thread B를 수행 후 다시 thread B가 thread A에게 메시지를 전달

(thread A  ->  thread B  -> thread A)

5. 마무리

최근에들어 보안의 중요성을 절실히 필요로하는 고신뢰성을 가지는 시스템을 구현하기에 마이크로 운영체제는 최적화되어있으며, 

many core(core가 1000~2000개) 시대가 도래할 것으로 예측되며, 이런 환경에서는 마이크로커널운영체제가 급 부상 할 수 있음