지밍이 블로그

# 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

# 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 등등

KLDP 등 여러 리눅스 커뮤니티에 공지를통해서

커널연구회라는 곳에서 세미나를 주최하여 진행하였음.

일시 : 2015.08.29(토) 14:00 ~ 17:00

내용 : Device Tree,  커널 4.0 포팅

1. 소개

- 강사소개 및 출판서적

커널연구회, 정재준대표님

Dedvice Tree 상세분석 in Linux Kernel 4.0

- 3.2커널이후부터는 디바이스 트리가 규약화 됨

- 디바이스 트리란? 디바이스 트리의 스크립트 부분만 수정하여(전체 커널소스는 수정하지 않아도됨) 다시 컴팡리하면 많은 하드웨어 디바이스를 지원이 가능하게하는 일종의 규약으로 탄생

- 임베디드 작품들 구경 및 설명

2. 컴퓨터 아키텍쳐

# 8bit microprocessor (AVR ATmega)

- Block Diagram of the AVR MCU Architecture

- 8bit 레지스터 * 32개

- 8bit : op + op1 + op2

   ex. + 001   01      01

- program memory map, data memory map, 

- the pararrel instruction fetches and instruction executions

- single cycle ALU Operation

- on-chip data sram access cycles

- Clock Distribution

# ARM cortex 제품 라인업

- cortex-A : s/w 위주 위주로 개발할 때 

- cortex-R & M  : h/w  위주로 개발할 때

# 32bit Architecture 

: 2^32 = 4 GB

# 32bit Architecture Memory Map

# 2^64 = 1024 * 1024 * ...... * 2^4 = ??GB

# ARM Cortex-M (32bit)

참고하기. http://lifeseed.tistory.com/m/post/60

3. 리눅스 커널 소스

- 2.6..21~ : task_struct 구조체, Linked-list(pointer), 라운드로빈, RTS 알고리즘

-  2.6.35~ : CFS 자료구조, 레드블랙트리 알고리즘

# 소스 다이어그램

- linux kernel map : http://www.makelinux.net/kernel_map/

- kernel diagram : http://www.makelinux.net/kernel/diagram

- system

- networking

- storages, file system

- memory

- processing

- human interface

# 커널 자료구조

- Device Tree : /proc/device-tree

/arch/...

/devices/...

/net/...

/mm/...

/devices/...

/fs/...

http://ssup2.iptime.org/wiki/Device_Tree

# 커널 4.0 포팅하는 방법

- GIC : 분산처리해주는...

- DMC 

http://forum.falinux.com/zbxe/index.php?document_srl=613440&mid=lecture_tip

<디바이스 트리>

- 타겟보드로 컴파일을 진행할땐 uboot로 진입해야함

- fastboot로 실행을 시킴

- 각 파티션으로 나누어져 있고 해당부분에 올려서 크로스컴파일로 진행

- root권한으로 진행

- DTB, DTC, DTS,
http://forum.falinux.com/zbxe/?document_srl=589850&mid=lecture_tip&page=3

http://forum.falinux.com/zbxe/?mid=lecture_tip&l=ru&document_srl=589850

<커널>

- ubuntu 버전에서

- kernel.org에서 리눅스 소스를 받으면 됨 
    https://www.kernel.org/pub/linux/kernel/v4.x/

- "make" 컴파일

"make build"  

https://kldp.org/node/133775

http://mintnlatte.tistory.com/429

https://www.gnu.org/software/make/

Ramdisk

buildroot : http://buildroot.org/

* logic analizer

https://www.saleae.com/downloads