지밍이 블로그

# Trashing 

> Trashing이 발생하는 과정

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

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

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

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

5. Memory는 점점 부족하게 됨

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

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

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

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

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

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

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

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

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

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

# Working Set

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

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

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

=> locality도 변하게 됨

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

> Working Set을 이용한 Prepaging

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

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

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

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

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

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

> Working Set의 단위

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

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

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

# Working Set의 approximation

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

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

=> key point !!

> Resident Set

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

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

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

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

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

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

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

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

# Memory Management의 Trends

<이슈>

1. Physical Memory의 크기가 커짐

- Page Frame이 넉넉해짐

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

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

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

2. Virtual Memory의 크기가 커짐

- 64bits with 4K page

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

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

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

4. Large Page Table의 Handling

- 문제 :

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

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

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

<해결방법>

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

<Two-Level Page Table>

- 32bit 환경에서,

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

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

* First Level Index == Outer Level Index

- Page Table Entry : 1 word size, 4bytes

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

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

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

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

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

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

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

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

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

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

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

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

# Page Replacement Policies

> Page replacement Algorithms

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

2. FIFO

- Linked List로 구현

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

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

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

Temporal Locality에 기반한 Page Replacement 정책.

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

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

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

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

* Dirty Bit

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

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

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

ex. LRU ...

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

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

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

=> LRU algorithm

> LRU

1. reference bits algorithm(8bits)

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

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

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

2. Clock Algorithm

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

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

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

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

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

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

3. Enhanced clock algorithm

- reference 안됐고 clean한 page

- reference 안됐고 dirty한 page

- reference 됐고 clean한 page

- reference 됐고 dirty한 page

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

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

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

> FIFO 사용

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

- used page frame list (linked list)

- free page frame list (linked list)

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

# Page Replacement Style

: allocation style

1. Global replacement

: 시스템 단위로 replacement

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

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

2. Per-process replacement

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

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

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

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

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

# Demanding Paging

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

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

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

* Principle of Locality(Locality of Reference)

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

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

* 90/10 Rule

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

* Swap Device

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

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

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

> Demand Paging의 Policy

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

* Memory Access Latency

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

* Thrashing 

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

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

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

* Resident Bit 

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

> Virtual Memory 사용의 key!

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

> Demanding Paging 구현의 기술적 이슈

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

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

<Page Fault Handling>

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

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

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

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

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

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

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

* MOVE (SP)+, -(R2)

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

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

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

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

> 정리

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

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

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

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

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

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

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

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

* 이상적인 Page Selection Policies

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

1. Demand paging : 

- pure demanding paging

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

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

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

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

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

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

- 과거에 사용했던 기법

- 예. Overay

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

=> Working Set 대두!

> 여러가지 관점

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

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

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

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

> 카페

  http://cafe.naver.com/ojsag

> 네이버 SVN

  http://dev.naver.com

  * 멤버등록

  * 암호설정

> 이클립스

  * plug-in  

  * SVN Repository

https://dev.naver.com/svn/ojsag20

subclipe 설치 > SVN  설정 > checkout

> 소프트웨어 개발 패러다임

구조적     >     정보공학     >     객체지향 >                 Contents Based Development?                 >     SOA     >     ROA

"절차"            "데이터"                "클래스"                                - Controller - Suvlet

    멤버(필드, 메소드)                         - View - html, xml

  - Model - JSON

* library와 Contents의 차이

: library는 그냥 모듈화, Contents는 MVC 모델을 포함하는 모듈화

> 프토토콜

비연결지향 (HTTP)

연결지향(FTP)

> 웹

"비연결지향 프로토콜의 단점을 해결하기 위한 기술"

1. Client Side

쿠키

2. Server Side (서버상태를 저장하기위한 객체 4가지)

PageContext 페이지

HttpServletRequest

HttpSession 웹브라우저

ServletContext 톰캣

3. File

4. DBMS

 > 요청 (Client Side - HTML5 + CSS + JavaScript + jQuery + Ajax)

URL

> 응답 (Server Side - Controller + View + Model Service + Model Entity)

HTML, XML, JSON, Text, ...

> 소프트웨어 공학

95년도 4학년 과정으로 선택과목으로 등장

2000년도 이후 필수과목으로 채택

"품질" - ISO 9126(6가지 품질), IEEE 1471(아키텍처 표준), ISO 52000(테스트 표준)

"객체지향"

> 소프트웨어 위기

"스파게이티 소스"

> 클래스 vs 객체지향

1. 저장위치

- 클래스 : 파일이므로 하드디스크

- 객체 : 파일의 클래스 로더가 클래스를 로딩하여 메모리에 올림. 값을 담기위해 만들어진 구조체.

2. 값의유무

> 객체 라이프 사이클

1. 클래스 정의

2. 객체참조변수 선언

3. 객체생성

4. 생성자호출

5. 주소할당

6. 객체사용

7. 객체소멸

"    Student st = new Student();   "

1. 클래스 정의 : Student. Student는 이미 정의되어 있어야 함.

2. 객체 선언 : st, 

3. 객체 생성 : new, 개발자가 직접 객체를 생성하느냐, Controller에게 객체생성을 위임하느냐(IoC), 

* has a, is a 관계

dependency, association, composition, aggregation

4. 생성자 호출 : (). 

5. 주소할당 heap메모리를 "st" 객체참조 변수에 assignment :  =. call by value, call by reference, call by name(없어짐)

6. 객체사용. polymorphism

7. 객체소멸.  java performance tuning 

java - " fojo, annoation "

> OOSD 기본 개념 7가지

<Object-Oriented Design concepts>

Cohesion 응집도. 하나의 클래스가 하나의 기능에 얼마큼 충실하는지 나타내는 척도. 높을수록 좋음.

Encapsulation. 

Coupling 결합도. 응집도를 높이기위해 클래스를 잘게 나누면, 원래 하나였던 클래스는 서로의 결합도를 높이게 됨. 모듈화의 결정 포인트를 잘 맞춰야 함. 낮을수록 좋음.

*Looser Abstract Coupling

Implementation ingeritance .

Composition

Interface ingeritance

Polymorphism

<java method 5가지>

> *Looser Abstract Coupling

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

client  -->   <<interface>>

Service

^

|

|

ServiceImpl

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

interface Service {

}

class ServiceImpl implements Service {

}

class Client {

Service s;

}

cf. looser couping

 http://tadhg88.blogspot.kr/

> 클래스 간의 관계

* Is-a

* has-a

> OOSD 원리 3가지

> 디자인 패턴

> 웹 서비스

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

홍창윤 강사님 / 010-3206-4184 / hiroad@naver.com

OJSAG 오라클자바소프트웨어아키테트그룹

# 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를 처리하는 프로시저로 구성. 프로세스를 호출하여 사용

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

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