인아웃

Allocation of Frames

여러개의 프로세스에게 어떻게 page frame을 할당할 것인가?

SW 측면에서 loop 내의 page는 한꺼번에 allocate 되는 것이 유리하다. 

그렇지 않은 경우 매 loop 마다 page fault가 발생할 수 있다.

Fixed Allocation

- Equal allocation : 각 프로세스에게 동일한 개수의 frame을 할당하는 방식

- Proportional allocation : 각 프로세스의 크기에 비례하여 frame을 할당하는 방식

Priority Allocation

: 프로세스의 중요도를 기반으로 frame을 할당하는 방식

I/O 를 감소시켜 waiting 상태의 시간을 줄여 실행이 빨리 끝날 수 있다.

page fault가 발생하는 경우 낮은 우선순위 프로세스의 frame을 선택하여 교체하도록 한다.

*Global vs Local Replacement

Global Replacement : replacement frame을 전체 frame에서 선택하도록 한다. 하나의 프로세스는 다른 프로세스의 frame을 가져와 사용할 수 있다. 동적으로 관리할 수 있고 circular queue로 관리하는 경우 전체 시스템으로 하나로 관리 할 수 있다.

Local replacement : 각 프로세스는 해당 프로세스 내에서 frame을 선택할 수 있다.

Thrashing

- 프로세스가 충분한 page를 갖지 못한다면 page fault rate가 높아지고 이는 CPU utilization을 떨어트린다.

- 프로세스의 잦은 page swapping으로 CPU 성능이 떨어지는 상태

Locality

프로그램의 메모리는 임의 시간 내에 프로그램의 일부분을 집중적으로 참조하는 고도의 지역성을 갖는다.

시간 지역성 : 현재 참조된 메모리가 가까운 미래에도 참조될 가능성이 높음 (loop, subroutine, stack)

공간 지역성 : 하나의 메모리가 참조되면 주변의 메모리가 계속 참조될 가능성이 높음(Array Traversal, 명령의 순차 실행)

Locality를 어떻게 계산할 것인가? 

Working-Set Model

- 현재 시점의 지역성을 확인하기 위한 목적으로 사용되는 working-set window를 사용

- working-set window가 너무 작은 경우 지역성을 반영하지 못한다.

- 각 프로세스의 working-set size의 합은 사용가능한 전체 frame의 크기보다 크면 Thrashing 상태가 된다.

이때 , 프로세스는 suspend 되도록 한다.

- 매번 working-set을 계산하는 것은 cost가 많이 필요하다.

Page-Fault Frequency Scheme

적절한 Page fault의 상한선,하한선 기준을 정해 벗어나는 경우 조치하도록 한다.

상한선 보다 높아지는 경우 frame을 더 할당해주며 하한선 보다 낮아지는 경우 frame을 회수한다.

-> Working set 방식은 page 참조 시마다 페이지 집합을 수정하고 PFF 방식은 page fault 발생 시에만 페이지 집합을 수정하여 오버헤드를 상대적으로 줄인다.

Virtual Memory 의 장점 (프로세스 생성 시)

Copy-on-Write

부모와 자식 프로세스가 처음에는 같은 page를 공유하도록 하고 write를 하는 순간 page를 복사하고 복사한 page에 write 작업을 수행

기본적으로는 page를 공유하도록 하고 write 할 때 copy 하여 수행하도록 하여 메모리 사용 효율성을 높일 수 있다.

Memory-Mapped Files

프로세스의 가상 공간 중 일부를 디스크에 있는 파일의 블록에 매핑하는 방식이다.

기존의 system call 의 오버헤드를 줄일 수 있다. (I/O를 줄일 수 있다.)

즉, 디스크 파일의 일부와 매핑하여 file system을 통한 과정을 거치지 않아 속도가 빠르고 I/O 발생으로 인한 오버헤드가 줄어든다.

Prepaging

일반적으로 페이징 기법을 사용할 때 초기에는 page fault가 반드시 발생한다.

이러한 page fault를 줄이기 위해 Prepaging으로 미리 올려둬서 page fault 를 줄일 수 있다.

Page size

- Page size가 과도하게 큰 경우 Internal fragmentation이 발생 할 수 있다.

- Page size가 작은 경우 Page table size가 커질 수 있다.

- Page size가 커지면 locality를 정확히 구분하기 어렵다.

I/O Interlock

- page가 memory에서 lock 상태가 되어야 하는 경우가 필요하다.

예를들어 디스크에서 외부저장장치로의 이동을 위해 buffer에 있는 경우 page 교체가 일어나면 정상적으로 파일이동이 불가하다.

이러한 경우 page가 교체되지 않도록 보호해줄 필요가 있다.

Virtual Memory

: logical memory 와 physical memory를 분리

프로그램 실행을 위해서는 logical memory가 모두 physical memory에 올라와 있어야한다.

하지만 실제 주소 공간은 논리적 주소공간보다 작다.

효율적인 공간 사용을 위해 CPU 입장에서는 다 올린 것 처럼 보이도록 하고 실제로는 실행에 필요한 부분만 메모리에 올리는 방법이다.

Demand Paging

CPU가 접근하여 필요로 할 때 page를 memory에 올린다.

- I/O 발생이 줄어든다.

- 메모리 사용이 줄어든다.

- 응답 속도가 빨라진다.

vaild-invalid reference를 memory에 올리는 과정에 사용한다.

Lazy swapper

- page가 필요한 경우에만 swap을 한다. page를 다루기에 pager 이라고도 한다. 

Valid-Invalid Bit

Valid(v)

- 메모리에 있는 상태

Invalid

- illegal : 해당 프로세스의 주소 공간이 아닌 경우

- not-in-memory : 해당 페이지가 메모리에 업로드 되지 않은 경우

- obsolete : disk에서 업로드되었지만 실제 데이터가 updated 되어버린 경우

주소변환이 일어날 때 invalid 상태인 경우 "page fault" 라는 핸들러를 통해 다룬다.

Page Fault

invalid page에 대한 접근은 trap을 발생시킨다. (page fault trap)

[ page fault handler 처리 과정 ]

1. illegal reference인 경우 해당 프로세스를 중단한다.

2. memory에 없는 경우라면 빈 page frame을 찾는다. free frame이 없는 경우 replace 과정을 진행한다.

3. page를 해당 frame으로 읽어온다.

4. CPU가 프로세스에게 할당할 때 page fault trap은 종료된다.

5 . page fault를 발생시킨 명령어를 다시 재시작한다.

Page replacement Algorithm

freeframe이 없는 경우 victim page를 선정하여 교체 과정을 진행해야 한다.

page fault를 최소화하여 replacement 과정이 이루어지도록 하는 것이 필요하다.

First-In-First-Out(FIFO) Algorithm

- frame에 먼저 들어온 순서대로 replace 과정을 진행하는 알고리즘이다.

- frame 개수가 늘어나는 경우 이론상 page fault가 줄어야 하지만 늘어나는 현상이 발생한다.(Belady's Anomaly)

Optimal Algorithm

- 이론상 최적의 알고리즘으로 미래 예측이 가능해야한다. 실제로는 불가능하므로 다른 알고리즘 성능을 평가하기 위해 사용된다.

Least Recently Used Algorithm(LRU)

- 과거의 사용을 기반으로 미래를 예측한다는 의미

- 과거에 가장 적게 사용된 것은 미래에도 사용되지 않을것이라 판단하고 victim page로 선정한다.

- timestamp를 사용하여 각 page의 최근 사용시간을 확인하여 찾아낸다. -> timestamp(I/0) 와 최소값을 찾는 과정의 오버헤드가 크다!

LRU Implementation Algorithms

: LRU의 timestamp 사용과 최솟값을 찾는 과정에 발생하는 오버헤드를 최소화하기 위해 사용하는 방식이다.

1) Counter implementation

- 정확한 시간은 필요없으니 상대적인 순서만 이용하기 위해 CPU counter를 사용하는 방식

2) Stack impementation

-double link 형식의 stack 구조를 사용하여 top에 최근 사용 page를 기록하는 방식 -> 자료구조 유지에 대한 오버헤드가 발생

LRU Approximation Algorithms

: 오버헤드를 최소화하며 LRU 처럼 동작하도록 하는 알고리즘

1) Reference bit

- 초기값을 0으로 설정하고 주기적으로 0으로 reset 해준다. (0인 경우 교체를 해준다.)

2) Additional-Reference-Bits Algorithm

- 주기적으로 오른쪽으로 한칸씩 이동해준다. bit 값이 큰 것이 사용이 많이 됨을 알 수 있다. -> 8비트 사용과 최솟값을 찾기 위한 오버헤드 발생

3) Second chance(clock) Algorithm

- 포인터를 사용하여 원형 큐를 사용한다.

- 포인터를 하나씩 이동하며 reference bit을 확인하고 1인 경우 0으로 바꾸고 0인 경우 replace를 한다.

- 기존의 자료구조,최솟값 찾는 알고리즘 등으로 인한 오버헤드가 사라진다.

- 원형구조로 사용되어 같은 reference bit가 0이어도 순서구분이 가능해진다.

Deadlock

프로세스가 서로 자원을 갖고 놓지 않아 다른 자원을 얻기를 기다리는 상태

Deadlock의 4가지 조건

Mutual exclusion : 한번에 단 하나의 프로세스만 자원을 사용할 수 있다.

No preemption : 프로세스가 자원을 놓는 과정은 자발적으로 이루어져야 한다.

Hold and wait : 프로세스는 적어도 하나의 자원을 갖고있는 상태에서 다른 프로세스가 갖고있는 자원을 기다리는 상태이다.

Circular wait : 자원을 갖고 기다리는 형태가 원형적으로 이루어져야 한다.

Resource-Allocation Graph

정점을 V, 간선을 E로 나타낸다.

V는 프로세스를 나타내는 P와 자원을 의미하는 R로 표현된다.

request edge - P1 -> Rj (P1이 Rj 를 요청)

assignment edge - Rj -> P1(Rj이가 P1에 할당됨)

graph가 cycle을 갖지 않으면 deadlock이 발생하지 않는다.

graph가 cycle을 갖는 경우 자원에 하나의 instance만 존재하는 경우에는 deadlock 발생, 여러 instance가 존재하는 경우 발생가능성이 있는 것.

Deadlock을 해결하는 방법

1. Prevent, avoid : 시스템이 deadlock 상황에 들어가지 않도록 미리 보장하는 방법

2. Recover : deadlock이 발생하도록 허용하고 발생 후 해결하는 방법

3. Ignore : deadlock이 발생하지 않을 것이라고 보고 무시하는 방법 (실제 deadlock 발생 확률이 낮기 때문)

Deadlock Prevention

Deadlock의 4가지 조건 중 하나라도 만족시키지 않도록 하는 방법

- Mutual Exclusion : non-sharable 자원을 갖도록 한다.  -> OS 구조상 불가능한 방법

- Hold and Wait : 프로세스가 자원을 확보할 때 모두 확보하도록 하자.(all or nothing) -> starvation 문제 발생

- No Preemption : Hold and Wait 방식과 유사하나 하나씩 확보를 해보고 모두 확보가 불가능한 경우 모든 자원을 내려놓도록 하는 방식.

- Circular Wait : 자원 유형의 전체 순서를 지정하고 각 프로세스가 순차적으로 자원을 요청하도록 한다. 즉, back edge가 만들어 질 수 없는 구조로 만드는 방식.

결론 : Prevention은 자원 활용성을 떨어트리는 방식이다.

Deadlock Avoidance 

Deadlock이 발생할 수 있는 경우를 비해서 가도록 하는 방식 -> 미리 Deadlock을 예측해야한다.

- 가장 간단하고 유용한 모델로 프로세스의 각 자원타입의 최대 자원 개수를 알아야 한다.

- deadlock-avoidance algorithm 은 circuler wait 조건이 만족하지 않도록 동적으로 자원 할당 상태를 예측해야한다.

- 자원 할당의 state는 가능 자원수, 할당된 자원 수 , 프로세스의 최대 필요 자원 수로 결정된다.

Safe State

자원을 할당했을 때 안전한 상태인지 판단한다. 종료 sequence가 존재한다면 Safe State로 판단.

시스템이 safe state인 경우 deadlock이 발생하지 않는다.

시스템이 safe state가 아닌 경우 deadlock 발생 가능성이 있는 것이다. -> 모든 프로세스가 최대 자원 개수를 모두 요청하는 경우

결론 : Avoidance는 시스템이 unsafe state에 절대 들어가지 않도록 보장해준다.

Avoidance Algorithm

- Single instance인 경우 -> Resource-allocation graph 사용

- Multiple instance인 경우 -> banker's algorithm 사용

Single instance per resource types

- claim edge : 사용할 자원을 나타내는 간선

- request edge : 프로세스가 사용을 위해 요청하는 상태를 나타내는 간선

- assignment edge : 자원이 할당되는 상태를 나타내는 간선

-> 사이클이 형성하지 않게 되는 경우에만 할당하여 간선의 상태변화

Multiple instances per resource types : Banker's Algorithm

- 각 프로세스는 자원 최대 사용량을 선언해야한다.

- 프로세스가 자원을 요청하는 경우 safe 하지 않으면 wait해야한다.

- 프로세스가 모든 자원을 확보한 경우 유한 시간내에 자원을 돌려줘야 한다.

Banker's Algorithm의 자료구조

n = 프로세스의 개수, m = 리소스 타입의 개수

Availabe[j] = k : Rj 리소스에 k개의 인스턴스가 사용가능하다.

Max[i,j] = k : Pi 프로세스가 Rj의 최대 k개의 인스턴스를 요청할 수 있다.

Allocation[i,j] = k : Pi가 현재 Rj의 k개 인스턴스를 할당 받았다.

Need[i,j] = k : Pi가 추가적으로 Rj의 k개 인스턴스를 필요로 한다.

-> Need[i,j] = Max[i,j] - Allocation[i,j]

Safety Algorithm

1. Work 는 사용가능한 자원, Finish는 프로세스 종료를 나타낸다.

    Work := Available

    Finish[i] = false -> 프로세스 i가 끝나지 않은 상태

2. 다음 두 조건에 만족하는 i를 찾는다.

    a. Finish[i] = false

    b. Needi <Work

    프로세스가 실행되어야 하고 필요한 개수가 사용가능 개수보다 적은 경우 3번 수행

    존재하지 않는 경우 4번 수행(더 이상 수행가능한 프로세스가 없는 경우)

3. 남은 자원을 할당해주어 프로세스가 완료되도록 한다.

    Finish[i] := true

    2번 과정으로 돌아가 반복하며 모든 프로세스에 대해 수행

4. 모든 i에 대해 Finish[i] = true 인 경우 sequence가 존재하므로 safe state임을 확인

safe 한 경우 -> Pi에게 자원을 할당

unsafe 한 경우 -> 이전의 resource-allocation state를 복구

Deadlock Detection

Deadlock이 발생하도록 두고 발생할 때 해결하는 방식

- Detection algorithm

- Recovery scheme

Single Instance of Each Resource Type

- wait-for graph를 사용한다.

- cycle을 찾기 위해서는 O(n^2) 의 시간 복잡도를 갖는데 이를 줄이기 위해 프로세스 Vertex만 사용하여 프로세스간 wait 관계만 표기

Deadlock Detection Algorithm

safety algorithm과 유사하지만 미래 예측이 필요없기애 max 같은 자료구조를 사용하지 않는다.

Availabe : 사용가능한 자원의 수

Allocation : 현재 프로세스에게 할당된 자원의 수

Request : 프로세스가 요청하는 자원의 수

1. Work, Finish 변수 사용

    Work := Available

    For i = 1,2,...,n

        Finish[i] = false (Allocation<j> != 0 인 경우)

        Finish[i] = true  (나머지 경우) -> 자원할당을 받지 않은 프로세스는 사이클 대상이 될 수 없으므로 종료된 프로세스로 취급

2.  다음 조건을 만족하는 index i를 찾는다.

    a. Finish[i] = false

    b. Request<i> <= Work

    만족하지 않는 경우 4번 과정으로 진행

3. Work := Work + Allocation<i>  -> 프로세스를 완료하고 자원을 놓아줌

    Finish[i] := true

    2번으로 돌아가 2,3번 과정 반복 수행

4. Finish[i] = false 인 경우가 존재한다면 deadlock이 발생 (Finish[i] = false 인 경우 Pi 가 deadlock 된 상태를 의미)

알고리즘은 O(m*n^2)의 시간복잡도를 갖는다. (m은 리소스 타입, n은 프로세스)

Problem : detection algorithm은 언제마다 실행되어야 하는가?

- 모든 요청시 -> 오버헤드가 크다.

- 요청을 받아들일 수 없을 때 -> 빈도는 다소 줄어듦

- 주기적으로? -> deadlock 이 발생하고 바로 할 필요없다. 주기적으로 하자

Recovery from Deadlock : Process Termination

- Deadlock 된 프로세스를 모두 죽이자.

- Deadlock cycle이 사라질 때까지 프로세스를 하나씩 죽이자

- 어떤 순서로 프로세스를 죽일 것인가?

   a. 프로세스의 우선순위에 따라

   b. 프로세스가 얼마나 실행되었고 남은 실행 기간에 따라

   c. 프로세스가 사용한 자원 수에 따라

   d. 완료까지 필요한 자원의 수에 따라

   e. 몇개의 프로세스가 종료되어야 하는지에 따라 (최소한의 프로세스를 죽이는 방법)

   f. 프로세스의 interactive, batch 여부에 따라

Recovery from Deadlock : Resource Preemption

- 희생 프로세스를 고른다 -> 어떤 프로세스의 자원을 뺏을 것인가

- Rollback -> safe state로 돌린 후 프로세스를 그 상태에서 재시작한다.

- Starvation : 하나의 프로세스가 계속 희생되어 starvation 문제가 발생 할 수 있다.

Avoidance vs Detection

Avoidance

- 미래를 예측하기에 소극적으로 동작한다. -> worst case assumption

- deadlock이 발생하지 않음에도 자원을 주지 않아 자원의 낭비가 발생한다.

Detection

- 현재를 기준으로 판단한다. -> best case assumption (프로세스가 추가적인 자원을 요청할 것이라고 생각하지 않음)

Classic Problems of Synchronization

1. Bounded-Buffer Problem -> 대표적인 동기화 문제 

2. Readers and Writers Problem -> scheduling 관련 동기화 문제

3. Dining-Philospohers Problem -> deadlock 관련 동기화 문제

Bounded-Buffer : Shared-Memory Solution

Producer, Consumer 문제

-> Bounded buffer 를 사용하여 producer는 생성만하고 consumer는 소비만 한다.

이때, buffer에 대한 동기화 문제가 발생하는데 이를 semaphore P, V 로 해결가능하다.

(버퍼가 꽉 찬 경우 Producer가 생성할 수 없고 버퍼가 비어있는 경우 Consumer가 읽어 올 수 없음 -> 쓰기,읽기 전 상태 확인 필요)

하지만 본질적인 문제는 Buffer 내의 변수들에 대한 동기화 문제도 동시에 해결해야함 -> 변수 자체를 semaphore 변수로 만들자! 

[문제 해결]

변수 자체를 semaphore 변수로 만들어 사용

integer semaphore N을 사용하여 buffer의 개수를 읽어 다른 process가 접근하지 못하도록 해야한다. 

N_empty-buf : 버퍼가 비어있는지 확인

N_full-buf : 버퍼가 가득 차있는지 확인

binary semaphore S_mutex 를 사용하여 buffer 에 대한 동기화 문제를 해결

integer semaphore 를 사용하여 buffer 가 비었는지, 꽉 차있는지 확인하여 접근에 대한 동기화 문제 해결

mutex가 필요할까?

-> buffer의 개수는 복수개이다. 반쯤 채워진 경우 두개의 프로세스가 통과하여 동기화 문제를 발생시킬 수 있으므로 P,V 를 사용하여 buffer를 보호해준다.

왔다갔다 할 수 있는 이유 -> P, V 함수가 atomic 하기때문에 가능하다.

Readers-Writers Problem

위에서 다룬 Producer, Consumer 문제와 유사하다. 하지만 생산자,소비자 문제에서는 Date를 소비하였지만 Readers-Writers Problem 에서는 Data를 소비하지 않는다는 차이점이 있다. 즉 Read-Only 동작을 하는 것이다.

동시에 Read를 할 수 있도록 하여 producer, consumer problem에 비해 Throughput을 높이고자 하는 동기화 방식으로 사용된다.

Read-Only를 하는 경우 Reader들간에는 동시에 접근이 가능하여 동기화 문제가 발생하지 않는다.

하지만 Writer 가 쓰는 도중에 읽거나, Reader가 읽는 도중에 쓰기 작업은 문제를 발생시키기 때문에 Reader와 Writer 간의 동기화 문제를 해결해줘야 한다.

<2가지 방식>

1. 모든 reader가 동시에 읽기 수행이 끝난 후 writer가 쓸수 있도록 하는 방식

2. 급한 작업인 경우 writer가 쓰고 난 후에 readers 가 읽을 수 있도록 하는 방식

여기서는 첫번째 방식을 다룬다.

reader 한명이 읽기를 시작한 경우 다른 reader들도 동시에 읽기 작업을 수행하도록 한다.

마지막 reader가 읽기 작업을 끝낸 후 writer가 쓰기 작업을 수행하도록 한다.

semaphore 변수 mutex, db를 사용하여 writer와 reader 간의 상호 배제 문제를 해결한다.

int 변수 readcount를 사용하여 reader의 읽기 상태를 확인하여 동기화 문제를 해결한다.

Reader는 첫 번째 reader 인 경우 P(db)를 호출한 뒤 읽기를 시작한다. -> Writer가 작업을 수행하지 못함

이후의 reader는 따로 P(db)를 호출할 필요가 없다. -> 두번재 reader도 호출하는 경우 동시읽기 작업 자체가 불가능해진다.

마지막 reader의 경우 읽기 작업을 끝낸 후 V(db)를 호출한다. -> Writer 가 작업을 수행할 수 있는 상태

Writer의 경우 대기하다가 마지막 reader가 읽기를 끝내고 V(db)를 호출하는 순간 쓰기 작업이 가능하여 critical section으로 넘어가게 된다.

쓰기 작업에 대해서도 마찬가지로 P(db), V(db)를 사용하여 reader 와의 동기화 문제로부터 보호한다.

Reader의 경우 P,V 함수를 호출하기 위해 첫번째,마지막 reader인지 확인을 위한 변수가 필요하다. => readcount 변수

readcount 변수 자체에 접근할 때에도 동기화 문제가 발생할 수 있다.

ex) 서로다른 reader가 동시에 readcount 를 증가시키고 읽기 작업을 수행하려는 경우 P(db)가 호출되지 않을 수 있다. 

=> 즉, read count 변수 자체에 접근하는 과정도 atomic하게 만들어줘야한다.

마찬가지로 readcount 연산 과정 앞뒤로 P,V 함수를 호출하여 count 과정 자체도 atomic하게 만들어줘 동기화 문제를 해결해준다.

( readcount ++; if(readcount ==1) , readcount --; if(readcount == 0)  해당부분이 critical section이 된다.)

Dining-Philosophers Problem : Think & Eat Repeatedly

[문제상황]

철학자들이 원탁에 둘러 앉아 생각을 하며 식사를 하는 상황.

하지만 젓가락은 양 옆으로 하나씩만 세팅되어있어 양쪽 젓가락이 사용 가능할때만 식사를 할 수 있다.

=> 젓가락을 집는 행위 자체가 동기화되어 이루어져야지 문제해결이 가능하다.

젓가락 하나를 공유변수라고 생각하면 왼쪽, 오른쪽 젓가락이 모두 사용중인 상태가 아닐 때 집어들어 식사를 할 수 있다.

P 함수(atomic한 함수)를 사용하여 P(chopstic[i])는 왼쪽, P(chopstick[(i+1)%5]) 은 오른쪽 젓가락을 나타내어 동기화 문제를 해결 할 수 있다.

But, 모든 철학자가 동시에 배가 고파 젓가락을 드는 경우를 생각해보자.

동시에 모두가 왼쪽에 있는 젓가락을 드는 과정까지는 성공을 한다. 하지만 모두의 오른쪽 젓가락은 사용중이기 때문에 대기상태에 빠진다.

서로가 기다리기만 하며 무한히 대기하는 상태가 발생하는데 이러한 상태가 Deadlock 문제가 발생한 것이다.

Deadlock이란 내가 다른 프로세스가 가진 자원을 해당 프로세스가 놓을 때까지 기다리는 형태가 원형회귀적으로 발생하여 해결되지 않고 무한히 서로가 서로를 기다리는 상태에 빠지는 것이다.

Deadlock and Starvation

Deadlock - 두 개 혹은 그 이상의 프로세스가 무한대기를 하는 경우 (대기 중인 프로세스가 깰 수 있지만 무한대기중이라 해결이 불가함)

<예시>

P0는 P(S)를 잡고 P1는 P(Q)를 잡은 상태이다.

이 경우 서로 P(Q), P(S)를 잡지 못해 서로를 계속 기다리는 상태에 빠져 다음 과정 진행이 불가하다. 마찬가지로 V(Q),V(S) 함수 호출 또한 할 수 없어 문제가 해결될 수 없다.

Starvation - 무한하게 blocking 되는 현상이다. 하지만 deadlock 문제와는 다르게 다른 어떤 프로세스는 진도를 나가고 있다는 것이 차이점이다.

LIFO 큐로 구성된 경우 Linked-List의 제일 앞의 프로세스는 거의 깨어나기 힘들어 희생되어 진행되지 못하고 있는 상태이다.

Deadlock - 3가지 해결방안

1. 젓가락을 하나씩 드는 것이 아니라 둘다 확인을 하고 동시에 들어서 문제를 해결하자 (양쪽 젓가락을 하나의 자원으로 취급)

2. Asymmetric coding -> 홀수번째 철학자는 왼쪽 젓가락을, 짝수번째 철학자는 오른쪽 젓가락을 먼저 들도록 함

3. 5명이 있는 경우 4명만 앉혀서 문제를 해결하자

-> 3가지 경우에 대해 직접 알고리즘 구현해보기!

Problems of Semaphore

: Semaphore를 이용하면 동기화 문제를 해결할 수 있지만 사용해서 해결하는 과정이 어렵다

- 코드를 구현하는 것이 어려움

- 정확성을 입증하는 것이 어려움 -> 오류를 재현하는 것이 어렵다

- 협력 과정이 필요하다.

- 잘못된 사용은 전체 시스템을 마비시킬 수 있음

* 조금 더 쉽게 해결할 수 있는 방법이 없을까? ==> Monitor 방식

Monitors : Similar to Abstract data type (private data -- public methods)

Hight-level language 에서 공유 데이터 접근 동기화 문제를 해결해주는 추상적인 데이터 타입

객체지향언어에서와 유사하게 public methods만 private data에 접근 가능한 구조이다.

Schematic View of a Monitor

Monitor 는 내부에서 단 하나의 프로세스만 active 가능하도록 보장한다. (Monitor의 기본개념)

여러 public method가 접근시도하는 경우 하나가 실행중이면 entry queue에서 나머지 프로세스가 대기하도록 한다.

Monitors

코드를 수행하는 중 조건을 만족시켜야 하는 경우가 발생하는데 다른 프로세스가 해당 조건을 만족시키는 경우가 발생한다.

=> Monitor 내부에서 wait 하도록 한다. active 하지 않게 sleep 상태로 wait 하도록 만들어주어 entry queue의 다른 프로세스가 실행할 수 있도록 해준다.

이를 위해 condition variable 을 사용한다.

condition x, y;

x.wait() -> x 조건을 만족시키지 못해 sleep 상태로 기다리도록 한다.

x.signal() -> x에서 기다리는 프로세스에게 시그널을 보내 깨워주도록 한다.

Monitor : Dining-Philosophers Problem

Dining-Philosophers Problem의 Deadlock 문제를 양쪽 젓가락을 드는 방식으로 해결한 경우

*Bounded Buffer Problem을 위한 Monitor 작성해보기

<전체코드>

전체적인 동작 과정

thinking, eating, hungry 세가지 상태로만 구분한다.

Monitor Implementation

Conditional-wait construct : x.wait(c); -> c 변수를 사용하여 우선순위를 정하여 순서를 제어하도록 하자.

Monitor 에서는 다음 두 가지 조건이 만족한다면 올바른 동기화 문제 해결책이 될 수 있다.

1. 항상 올바른 순서로 호출해야한다.

2.비협조적인 프로세스가 monitor 가 제공하는 상호배제 gateway를 무시하지 않도록 하며, 접근 프로토콜을 사용하지 않고 공유 자원에 직접 접근하도록 해야한다.

*access protocol : 장치가 네트워크를 통해 서로 통신하는 방식을 제어하는 일련의 규칙

Operating system structure

Multiprogramming

multipromgramming 은 efficiency 측면에서 필요하다. (자원 활용의 효율성을 높여준다.)

cpu가 불필요한 wait을 하지 않도록 해준다.

job scheduling을 통해 실행한다.

i/o 와 같은 wait 이 발생하면 다른 일을 수행한다. → multitasking을 위해, 모든 프로그램이 조금씩 실행하도록

Timesharing(multitasking)

-cpu의 시간을 나눠서 사용

-모든 프로그램을 메모리에 올릴 수 없으므로 swapping 방식(실행되지 않은 프로그램을 디스크로 보내는 것)을 사용 → 속도가 느려지는 문제 발생

-virtual memory를 사용하여 swapping 방식의 문제를 해결, virtual memory는 현재 필요한 부분만 메모리에 올리는 방식으로 메모리를 관리

Operating System Operation

interrupt는 hardware로 부터 발생한다.

software error , request는 exception이나 trap을 발생 시킨다. → 현재 실행중인 것을 중단하고 error 처리(error의 파급력이 전체적으로 크기 때문), i/o 때문x, interrupt방식과 유사

Dual-mode 동작이 OS를 보호한다.

-user mode 와 kernel mode 사용

-hardware 가 mode bit 제공

-system call은 직접 호출하지 않고 라이브러리 함수를 이용하여 안전하고 편리하게 호출한다. ex)printf()

-operating system code와 application code를 구분해서 전달 (권한이 달라지기 때문) > mode bit 사용

Process Management

Process : 프로그램 실행에 필요한 모든 정보를 담는 자료구조 → 메모리에 전달하는 형식

프로그램 실행 시 필요한 요소 : cpu, memory, i/o, files, initialization data

single-threaded process 는 하나의 program counter(프로그램 실행 위치 저장) 을 갖는다.

multi-threaded process의 경우 하나의 thread당 하나의 program counter를 갖는다.

program management activities

-creating and deleting user and system process

-suspending and resuming process

-providing mechanisms for process syncronization(동기화)

-providing mechanisms for process communication → 프로세스 간 통신

-providing mechanisms for deadlock handling

memory management

processing 전과 후의 모든 메모리 관리

메모리의 어떤 위치에 어떤 것이 있는지 내용들을 관리

어떤 data나 process를 memory에 넣고, 제거할 지 관리

필요할 때 memory 공간을 할당

Storage Management

Application이 Harddisk에 접근하는 방식은 어렵고 복잡 → file 공간에 쓰고 저장해라 그러면 OS가 알아서 하드디스크에 저장할게!

file을 체계적으로 저장하고 관리하기 위해 directories를 사용

Mass-Storage Management

-대량의 데이터를 저장하고 관리 →안전성,보안성,검색성,자원최적화 등을 보장

-free-space management

-storage allocation

-disk scheduling → i/o가 느리기 때문에 요청 순서를 조절하여 harddisk head의 움직임을 최소화

Migragion of integer A from Disk to Resgister

magnetic disk → main memory → cache → hardware register

multitasking 환경은 최신 data(recent value) 라는 것을 보장해줘야한다. → core가 여러개일 때 어려워짐

multiprocessor 환경에서는 cache coherency를 보장하여 모든 cpu에서 cache에 가장 최근의 데이터 값을 갖도록 해야한다.

I/O Subsystem

OS는 사용자가 수많은 종류의 I/O 장치를 구분없이 사용할 수 있도록 해주는 것이 목표이다.

block device, clock device 만 구분해서 전달해줘 > 나머지는 OS가 해줄게

-buffering(임시저장공간)

-caching(빠른 저장 공간에 두는 것)

-spooling (직접 보내지 않고 spool에 두면 os가 읽어가는 방식)

Protection and Security

프로세스는 실행한 사용자의 권한을 승계받아서 작동

Protection - 권한 없는 사용자가 접근 시 보호

모든 사용자에 ID를 부여하고 ID에 권한을 부여하여 관리 (root는 만능 , 모두 가능)

-system은 사용자들을 구분하고 권한을 구분

-user identities

-user id

-group identifier(group id)

-privilege escalation → ex)os가 만든 영역(spool)에 사용자가 접근하는 것이 불가능 하여 print의 경우처럼 권한을 잠시 부여 후 다시 회수하는 것

Operation System Services

System Calls

:os가 제공하는 service 의 programming interface

system call을 이용하여 os가 제공하는 service를 사용 가능하다.

direct system call 보다는 주로 Application Program Interface(API) 통해서 접근

-WIn32 API → 윈도우용

-POSIX API → UNIX계열

-JAVA API → JVM

→ 계열에 따라 같은 API를 사용한다. print()의 경우 C에서 제공하는 것이라 공통적으로 사용 가능

system call 보다 api를 사용하는 이유 : portability(이식성) → 소스 코드를 하나로 통일 가능 , 쉬운 사용

System Call Implementation

일반적으로 시스템 호출 인터페이스와 관련된 번호는 이러한 번호에 따라 색인된 테이블 유지→table을 찾아서 이동

시스템 호출 인터페이스는 OS 커널에서 의도된 시스템 호출을 호출하고 시스템 호출의 상태와 반환 값을 반환

호출자는 시스템 호출이 구현되는 방법에 대해 아무것도 알 필요가 없음

-API를 준수하고 결과적으로 OS가 수행할 작업을 파악해야 함

-API에 의해 프로그래머에게 숨겨져 있는 OS 인터페이스의 대부분 세부 정보

Virtual Machines

-하드웨어와 OS를 묶어서 텅 빈 하드웨어처럼 만들어줌(실제 OS는 존재)

-a는 nonvirtual machine, b는 virtual machine

virtual machine은 각각의 os를 따로 관리할 수 있음(경제성이 높음)

The Java Virtual Machine

-사용자 PC에 가서 해당 PC에 맞도록 컴파일 하자!

-JVM을 각 기기에 설치

Background

동기화 문제를 다루는 이유?

->공유 data로의 동시적 접근이 발생하는 경우 result inconsistency 문제가 발생할 수 있음

Race condition

:몇몇의 process들이 접근하여 shared data를 동식에 조작하는 상황

-> 이 경우 final value 는 마지막 실행 프로세스의 결과에 따라 달라짐

Race condition 문제를 방지하기 위해 concurrent processes는 synchronize 되어야 한다.

The Critical-Section Problem

n개의 process들이 shared data를 사용하기 위해 competing 하는 상황

각 process는 code segment를 갖는데 이를 critical section이라고 한다. (shared data가 접근되는 영역)

Race condition을 막기 위한 solution : 하나의 process가 실행중인 경우 다른 process는 critical section을 실행하지못하도록 막자!

Requirements for the Solution

3가지 요구조건

1. Mutual Exclusion

- 상호베타적으로 Critical Section을 수행할 수 있도록 해줘야 한다.

하나의 process pi 가 critical section 에서 실행중이면 다른 어떤 process도 critical section에서 수행할 수 없도록 해야한다.

2.Progress

-과도하게 막아서 어떤 process도 critical section에서 수행중이지 않은데도 못들어가게 막는 상황은 발생하면 안된다.

3. Bounded Waiting

- 다른 process가 실행중이라 기다리는 중인데 순서가 계속해서 밀려서 기다리게 되는 경우가 발생해서는 안된다.

(기다리는 시간의 bound값을 정해야 한다. -> starvation 개념과 비슷)

Progress, Bounded Waiting 은 Race condition을 방지하되 Throughput이 떨어져 전체적인 성능이 저하되지 않도록 하기 위한 조건

Initial Attemps to Solve Problem

2개의 process p1,p2가 있는 경우

entry section과 exit section을 설정

entry section : 진입 가능한 상태인지 확인 (다른 process의 상태를 확인)

exit section : 끝난 후 다른 기다리는 process에게 알림 (본인 상태를 다른 process에게 알림)

-> process 상태를 나타내는 변수가 필요

Algorithm 1

Shared variables : int turn, initially turn = 0

turn 이라는 변수를 사용하여 해당하는 값의 process만 critical section에 들어갈 수 있음

turn이 0이 아닌 경우 while loop 문을 돌면서 기다린 후 process가 끝나서 turn =1 이 되면 실행

특징 : P0이 끝나서 turn =1 이 되면 P1이 실행되어 turn =0 이 되어야지 다시 P0 실행이 가능하다.

mutual exclusion 조건을 만족하지만 progress 조건을 만족하지 못한다. -> swap-turn 문제 발생

=> solution이 될 수 없다!

Algorithm 2

들어가고자 하는 process를 들어가도록 만들어주자

Shared variables : boolean flag[2];

initially flag[i] = flag[j] = false;

flag 값이 true 이면 critical section에 들어간다. 이때 상대방의 flag를 먼저 check 하여 true 인 경우 양보하고 기다린 후 끝나면 들어감

swap turn 문제는 해결되지만 여전히 mutual exclusion 조건만 만족하고 progress 조건을 만족시키지 못한다.

->둘 다 true 인 경우 while 문에서 서로 기다리기 때문에 막혀버려서 critical section이 비었음에도 양보하며 기다리기만 하는 현상 발생

=> solution이 될 수 없다!

Algorithm3 (Peterson's Algorithm)

Algorithm1 과 Algorithm2 의 변수를 모두 사용하여 합친 개념

(1의 경우 들어갈 생각이 없는 process에게 turn을 줘서 문제 발생, 2의 경우 둘 다 들어가려고 하는 상황에서 교통정리를 못해줘서 문제 발생)

flag,turn 두 가지 변수를 모두 사용하여 문제를 해결 (상대가 들어갈 생각이 있고 순서를 갖는다면 문제 해결)

3가지 요구조건을 모두 만족 시킴 -> solution이 될 수 있음!

But 문제점

1. Busy waiting (waiting 상태에서 process가 while loop를 돌면서 CPU를 잡아먹고 있음 -> 매우 비효율적)

2.entry section 부분의 코드가 길다. -> 각 process 마다 작성하는데 너무 code가 복잡해질 수 있다. 개발자 입장에서 비효율적

Solution to Critical-section Problem using Locks

-위의 문제를 locking system을 이용하여 해결하자.

lock을 사용하여 해당 process 가 key를 확보하면 critical section에 진입하고 끝나면 key를 반납하여 다른 process가 사용가능하도록 설계

중요한 전제 조건 : key는 반드시 단 하나의 process만 갖도록 보장되어야 한다.

Synchronization Hardware

: 특별한 Hardware 회로를 제공하여 하나의 실행이 끝까지 수행되도록 보장해줌 (Atomic Hardware)

Cpu가 하나인 경우 CPU Scheduling에 의해서 process를 이동하며 문제가 발생한다. -> interleaved execution 발생

P1이 LOAD 되기 전에 CPU Scheduling이 발생하지 않도록 한다면 괜찮지 않을까?

->critical section을 빠져나오면 그때 cpu를 놓을 수 있도록 하자

How? -> interrupt가 발생하는 경우 cpu scheduling이 일어남

interrupt가 발생하는 경우는 i/o device, time out 두 가지 경우가 있음. critical section에서 I/O 발생은 일어나지 않으므로 time outㄹ을 활용하자

timer device가 time quantum이 끝나서 interrupt를 발생 시킬때 cpu scheduling이 발생한다.

critical section에 들어가면 timer interrupt를 disable 시키고 끝나고 나오면서 enable 시키자! => critical section 동안 cpu를 계속 사용 가능함

최근에는 atomic hardware instruction을 제공한다

atomic = non -interruptible

1. Test - and - Set (TAS)

2. Swap

Synchronization Hardware (1. TAS)

Test and modify (= Test and Set, TAS)

-한번 실행하면 중지 없이 끝을 보장한다. (atomically)

Mutual Exclusion with Test-and-Set

초기 lock은 false 값을 가지며 TAS에 의해 false를 return 하고 lock 은 true 값을 갖게 된다.

이 경우 lock 값이 true 이므로 새로운 process가 들어오려고 해도 while 문을 돌게 된다.

critical section이 끝나고 lock이 false 값을 가지면 새로운 프로세스가 들어올 수 있는 상태가 된다.

=>Peterson's Algorithm에 비해 매우 간단하다.

TAS 라는 atomic hardware가 존재하기 때문이다. (atomic 한 성질때문에 가능)

Synchronization Hardware (2.Swap)

shared data : boolean lock; (초기값 false 설정)

-swap(lock, key)를 사용하여 lock이 false 인 경우에만 critical section으로 들어갈 수 있다.

이미 실행중인 경우 lock 값이 true 가 되어 swap(true,true) 가 되며 key값이 그대로 true값을 가져 while문을 실행하게 된다.

=>결론 : atomic 한 hardware가 있다면 synchronization 문제를 해결할 수 있다.

Semaphores

Hardware를 사용하지 않고 Software적으로 해결할 수 있는 방법은 없을까? -> Semaphores

Semaphores : primitive한 것만 호출함으로써 동기화 문제를 해결해주는 도구

integer variable Semaphore S 사용

반드시 두 개의 atomic operation으로만 access 가능

1. P( ) : wait function

2. V( ) : signal function

S는 초기값 0을 사용하여 0보다 작은 경우 실행하지 않고 실행이 끝나 1값을 가지면 critical section 수행

Critical Section of n Processes

shared data : semaphore mutex (초기값 1)

mutex가 초기값 1을 가지고 critical section에 들어가면 0값을 가진다. 이때, 다른 프로세스가 와도 mutex값이 0이므로 while 문 실행

critical section이 끝나면 mutex는 다시 1값을 가지고 다음 프로세스가 들어가게됨

가능한 이유?

P, V 함수가 atomic 함수이기 때문이다. (atomic hardware와 동일하게 동작)

P, V 가  atomic한 함수가 아니라면 어떤 문제가 발생할까?

-> critical section에 두 process가 동시에 진입가능하게 될 것이다. atomic 하지 않다면 동시에 mutex 값을 1로 읽을 수 있음

Semaphore Implementation

Single Process인 경우 P 함수 첫부분에 interrupt disable을 설정하고 제일 마지막 부분에 interrupt able을 설정한다.

Single Process가 아닌 경우 Semaphore S를 Peterson Algorithm으로 감싸서 보호하여 S에 대한 동시 접근이 불가하도록 한다.

기존의 Peterson's Algorithm 과의 차이점?

->Semaphore를 사용하지 않는다면 critical section을 만날때마다 Peterson's Algorithm 구현이 필요하다.

하지만 Semaphore를 사용하여 P, V에 구현을 해두면 사용할 때마다 구현할 필요가 없다. (P, V 자체가 Peterson's Algorithm에 의해 Synchronization 되고 있다!)

P() 를 사용하는 경우 busy waiting 문제가 발생한다. 

critical section이 커지게 되는 경우 waiting 이 길어져 오버헤드가 커진다. 

Block / Wakeup Implementation

busy waiting 문제를 줄이기 위해 사용

while문을 돌면서 busy waiting을 하는 대신에 sleep을 시키고 조건이 충족되면 wakeup 해서 실행하도록 하자.

semaphore를 변수가 아닌 구조체로 정의

*L -> 포인터를 사용하여 sleep process들을 linked-list로 저장

block, wakeup 을 사용하여 관리

Implementation : block/wakeup version of P() & V()

초기값 1로 설정하여 S.value --를 통해 0이 되고 if문에 걸리지 않아 critical section을 수행하게 된다.

하지만 이후 들어오는 프로세스는 -값을 가져 if문에 걸려 block 된 후 linked-list에 추가된다.

critical section이 끝난 후 value값에 1을 더하고 하나를 list에서 제거 후 wakeup을 실행하여 다음 프로세스가 수행하게 된다.

이때 wakeup을 하는 경우 block 된 위치부터 실행하므로 바로 critical section으로 들어가게 된다.

integer semaphore -> value값을 사용하여 기다리는 프로세스의 개수를 파악 할 수 있음

binary semaphore -> 개수는 파악할 수 없고 유/무만 파악 가능

=>while loop 가 없어서 busy waiting 문제가 해결된다.

But! 무조건 좋은 것은 아니다. sleep, linked_list 저장, wakeup 모두 overhead를 발생시키기 때문이다

=> critical section이 짧은 경우 그냥 busy waiting을 하는 것이 더 효율적일 수 있다.

When the CS problem occurs in Operating System?

: 여러개의 Process 가 동시에 일하는 일이 OS에서도 일어날까? -> 발생한다!

3가지 경우

1.  Interrupt handler 와 kernel 사이에서 발생

2. kernel 이 system call 수행중 context switch 가 발생하는 경우

3. Multiprocessor - shared memory에서 kernel data 사용하는 경우

CS problem in OS (1) Interrupt handler v.s kernel

kernel process는 하나임에도 내부에서 동기화문제가 발생한다.

kernel code 실행중에 interrupt가 발생하여 interrupt handler code 실행 중 같은 kernel 변수를 사용하는 경우

-> disable/enable intrp 을 사용하여 해결

CS problem in OS (2) Preempt a process running in kernel?

: 프로세스간 scheduling 에 의해서 발생하는 문제

shared data가 없음에도 systemcall이 수행되는 동안 interleaved execution이 발생 할 수 있음

If you preempt CPU while in kernel mode

system call 이 발생하여 kernel code 수행 중 CPU Scheduling이 발생하여 다른 프로세스가 실행되고 이 프로세스가 kernel code 를 수행하게 되면 잘못된 결과를 도출한다.

-> System call 발생동안 CPU Scheduling이 발생하지 않도록 해서 문제를 해결하자

*UNIX의 경우 systemcall이 끝날 때까지 기다린다.

CS problem in OS (3) Multiprocessor

System 내에 CPU가 여러개인 경우 Interrupt disable,enable로 해결 할 수 없다.

1. Operating System 자체를 하나의 거대한 critical section으로 취급하는 방법 (간단한 방법)

CPU가 kernel 수행중이면 다른 CPU가 kernel 작업을 못하도록 한다.

-> 과도한 blocking으로 성능상의 문제가 발생한다. (CPU 개수를 늘려도 성능이 저하됨)

2. kernel 변수 하나하나에 대한 동기화 방법 (복잡한 방법)

-> 복잡하지만 성능면에서 문제가 발생하지 않음

=> 적절한 방법을 선택하는 것이 중요

Short-term scheduler라고 생각하면 된다.

현재 cpu 자원을 수행중인 프로세스 중 누구에게 줄지 결정하는 것

-> 사용자와의 interactive를 위해 i/o bound job에 cpu를 빨리 할당해줘야 한다.

State Transition Diagram

CPU Scheduler

:어떤 process에게 cpu를 줘서 실행할 것인가를 결정 (Multiprogramming environment)

cpu scheduler는 메모리에서 프로세스를 선택한다. 

cpu scheduling이 일어나는 4가지 경우

1. running 상태에서 waiting 상태로 바뀌는 경우 (i/o request)

2. running 상태에서 ready 상태로 바뀌는 경우 (timerunout)

3. waiting 상태에서 ready 상태로 바뀌는 경우 (i/o finished interrupt)

4.terminated

3의 경우는 interrupt 가 끝난뒤 원래 실행 program으로 돌아오는것이 아니기에 다시 cpu scheduling을 시작

1,4의 경우 nonpreemptive, 2,3은 preempive 경우이다.

Dispatcher

:  결정된 process에게 cpu를 주는 과정을 수행한다.

Dispatcher module

-switching context, switching to user mode, 사용자 프로그램의 적절한 위치로 jump 하고 재시작

dispatch latency

기존 프로세서를 중단하고 새로운 프로세서를 실행하는데 걸리는 시간 -> context switch overhead

Scheduling Criteria (기준)

CPU utilization : cpu가 계속 동작하도록 하는 것이 좋음 

Throughput : 단위 시간당 처리하는 작업의 양 -> maximize

Turnaround time : process 시작부터 끝까지 걸리는 시간 -> minimize

Waiting time : ready queue 에서 프로세스가 기다리는 시간

Response time : interactivity

Scheduling Algorithms

FCFS Scheduling

: First Come First Served ->먼저 온 process에게 먼저 cpu를 할당해주겠다. (공평성이 강점)

->실행시간이 짧은 프로세스가 먼저 들어오는 경우 waiting time이 줄어듬 -> convoy effect!

Shortest-Job-First(SJF) Scheduling

: 빠른 것을 앞으로 보내서 wait 시간을 줄이자 (average waiting time 측면에서 optimal)

두 가지가 존재

1. Nonpreemptive :더 짧은 것이 들어오더라도 기존의 실행이 끝난 후 실행

2. Preemptive : SRTF(Shortest-Remaining-Time-First), 더 짧은 프로세스가 들어오면 기존의 것을 중지하고 짧은 것을 먼저 실행

Determining Length of Next CPU Burst

: 알고리즘 사용을 위해 process의cpu 사용시간을 알아야함 -> 알수없음

estimate 하는 방식!

기존의 값들을 참고하여 예측하는 방식을 사용한다.

a값이 작아질수록 과거의 데이터가 공평하게 반영되고 값이 커질수록 최근에 대한 가중치가 높아진다. 최근 데이터에 가중치를 높게 주면 정확도가 높아지는 것을 확인 할 수 있다. 증감이 일정한 경우에는 정확도가 높은 값을 가질수 있다.

증감이 일정하지 않고 증감이 수시로 반복되는 경우 완전히 잘못된 결과를 가져올 수 있음 -> why?

최근 데이터에 가중치가 높으면 증가하다가 감소로 변하는 지점에서 감소에 대한 데이터 대신에 직전에 증가하던 데이터에 가중치가 높아져 정확도가 떨어지는 결과를 낼 수 있음

Priority Scheduling

:우선순위를 고려한 Scheduling 방식

각 process 에 priority number가 부여되고 이 번호에 따라 실행 (작은수가 높은 우선순위)

문제 : Starvation, 낮은 우선순위 프로세스는 계속 뒤로 밀려남

해결 : Aging, 대기시간이 길어짐에 따라 우선순위를 높여줌

Round Robin(RR)

: time quantum(cpu사용 가능 최대시간)을 설정하여 모든 프로세스가 돌아가면서 한번식 실행될 수 있도록 함 -> multiprogramming 목적으로 나온 방식

단점 :  time quantum 이 너무 작은 경우 context switch overhead 발생

higher average turnaround 이지만 response가 뛰어나다.

Multilevel Queue

Ready queue를 나눈다.

forground(interactive) : RR -> i/o bound job

background(batch - no human interaction) : FCFS -> cpu bound job

RR자체로만 쓰기에는 부족하여 Multi level queue 사용

Scheduling 은 queue 사이에서 진행

1.Fixed priority scheduling : 모든 forground 를 수행 한 뒤에 background 수행 -> starvation 문제 발생

2.Time slice : 조금씩 나눠서 starvation 문제를 해결 eg. forground in RR 80%, background in FCFS 20%

Multilevel Feedback Queue

I/O bound job, CPU bound job을 어떻게 구분하기 위함

process들은 queue 간 이동을 함

MLFQ의 5가지 정책

1. queue의 개수

2. 각 queue에 해당하는 scheduling algorithms

3. upgrade 방식

4. demote 방식

5. 어떤 queue에 process를 넣을 것인지

Real-Time Scheduling

Hard real-time systems

: guaranteed amount of time (deadline) 내에 반드시 수행되어야 함

Process 개념

Process : 현재 실행중인 프로그램

프로그램은 반드시 연속적으로 일어나야함 -> jump, 분기 instruction 때문에 바뀔 수 있음, default는 seqeuntial

Process는 5가지 별도의 공간을 가짐

text section : program code 부분

Stack : function call 과 context switch

   function call : parameter 저장, return address, local 변수 등

   context switch : 레지스터 값을 저장 (PC 포함) , stack pointer 저장

data section : static, global 변수 저장 -> 실행상황과 관계없이 어디서든 접근 가능한 Data

heap section(free memory pool) : 동적 할당을 위해 (malloc) -> 동적 할당 메모리 관리

stack으로 관리하는 이유?

Process in Memory (메모리 상에서 Process 모습) : Address Space(프로세스의 주소 공간)

text,data -> 고정 영역

stack 과 heap -> 가변 영역이지만 만날 가능성은 없음

Process State

프로세스 실행 과정에서 상태 변이가 일어난다.

new : process가 생성된 상태 (아직 cpu scheduling 대상은 아님) -> 실시간 system에서는 각 작업의 deadline이 정해져 새로운 process가 들어오면 자원할당이 필요하고 기존 process가 deadline을 만족시키지 못할 수 있기에 바로 scheduling 대상에 포함하지 않는다. 즉 , 기존 processe들이 deadline을 맞출 수 있는지 확인 후 scheduling 대상에 포함한다. 일반적인 os에서는 바로 편입

running : instruction이 실행되는 상태 (cpu를 잡고 일하는 중)

waiting : process가 event 발생을 기다리는 상태 (주로 I/O event)

ready : process가 할당받기를 기다리는 상태 (언제든 cpu를 할당받을 수 있는 상태)

terminated : process가 실행을 끝낸 상태( 마지막 instruction 수행 끝난 상태)

Process Control Block(PCB)

:어떤 프로세스에 대한 자료구조

kernel data structure

process state , program counter, cpu register, cpu scheduling information, memory-management information, accounting information, i/o status information

CPU Switch from Process to Process

:Multiprogramming, Multitasking을 위해 cpu를 잡고있는 process를 상태를 포장해서 저장후 다른 process 실행

Process Scheduling Queues

Job queue : process의 pointer를 갖고 있음(PCB의 pointer들)

Redy queue : CPU를 기다리는 process들이 모여있는 queue

Device queues : I/O Device를 기다리는 process들이 모여있는 queue

-> 프로세스의 상태가 변하면 queue에서 queue로의 이동이 일어남

Ready Queue and Various I/O Device Queues

1.CPU를 어떤 프로세스에게 줄지 결정

2. new -> ready 상태 변경을 결정

Schedulers

Long-term scheduler( or job schedular)

:new 에서 ready로 대상을 결정하는 schedular

-빈번하지 않게 발생하며 느리다.(seconds,minutes)

-degree of multiprogramming(현재 cpu를 이용하여 조금씩 수행중인 process 개수)를 control

Short-term scheduler( or CPU scedular)

:Ready 인 상태의 프로세스에게 어떤 scedular를 줄 것인지 결정

-매우 자주 발생하며 빨라야 한다. (mileseconds)

Addtion of Medium-term scheduling

Process는 두가지로 구분 -> process는 scheduling 입장에서 매우 중요한 정보를 가짐, 효율성을 위해 프로세스를 구분하여 관리한다.

I/O -bound process - 연산보다는 I/O에 대부분 시간 사용 (editor, hwp, massenger...), CPU를 짧게 여러번 사용

CPU-bound process - 연산에 대부분의 시간 사용, CPU를 길게 적게 사용

Context Switch

:Multiprogramming을 위해 생기는 것

CPU가 다른 process로 바뀔때 system은 이전 프로세서의 상태를 저장하고 새로운 저장된 상태의 프로세스를 불러온다.

store : regiser -> pcb

reload : pcb -> register

Context Switch Time 은 Overhead

-> 부가적인 overhead 발생 

switching 시 system은 특별한 일을 수행x

하드웨어의 지원을 받음

cache flushing - cache miss over head - context switch 가 발생하면 기존 cache 내용이 필요없어서 cache를 비워버림

Provcess Creation

-Process를 만드는 주체는 다른 어떤 Process이다(shell process).

부모 프로세스는 자식 프로세스를 생성한다.  -> tree 구조

프로세스는 pid(process identifier)로 식별하고 관리한다.

일반적으로 부모프로세스와 자식 프로세스는 내용적인 관계가 없다. 하지만 자식프로세스가 죽었을 때 부모 프로세스가 return 값을 받아줘야 한다.

resource를 공유하는 밀접한 관계도 있음

Execution : 부모와 자식 프로세스는 동시에 실행된다. 부모는 자식프로세스가 종료될때까지 기다린다.

Address spcae : 자식이 부모 값을 복제(default값) -> fork 하자마자의 상태는 부모와 동일

UNIX example

-fork() systemcall은 새로운 프로세스를 생성한다.

-exec() systemcall은 fork 호출 이후 프로세스의 메모리를 새로운 프로그램으로 대체한다. -> exec()가 호출되지 않으면 부모와 동일한 상태

Starting point of the child process -> 자식 프로세스가 fork() 된 시점을 정확히 알아야 함

fork() system call 이후  return 값을 받기 전에는 부모와 동일한 상태

자식 프로세스의 return  value는 0이며 부모 프로세스는 자식프로세스의 pid를 return value로 갖는다.

Process Termination

process 실행이 마지막 statement실행 후 os에 프로세스 삭제 요청을 함 -> exit() 

wait을 통해 자식 프로세스의 output이 부모 프로세스에 전달

프로세스 resources 는 os에 의해 deallocated

부모 프로세스가 자식프로세스의 실행을 중단시킴-> abort

- 자식 프로세스의 자원할당이 초과하는 경우

-자식 프로세스의 일이 필요없는 경우

-부모가 exit 하는 경우 os는 자식프로세스가 더 이상 작동하지 않도록 함 (cascading termination)

Interprocess Communication

Single and Multithreaded Processes

Threads

:thread(lightweight process)는 CPU utilization 의 기본단위

- program counter, register set, stack space로 구성되어 있음

threds는 code section, data section, files 내용을 공유한다. 

Threads 사용의 장점

Responsiveness

- 부분적으로 blocked가 발생하거나 긴 operation이 수행되더라도 program이 계속 작동할 수 있도록 해준다.

Resource Sharing

-process를 여러개 사용한다면 address space가 독립적으로 존재하여 overhead가 크게 발생한다. 하지만 thread는 memory copy를 하지 않고 공유할 수 있다.

Economy

-프로세스를 만들고 context switch를 하는 것 보다 경제성이 뛰어나다.

Scalability(확장성)

-각 thread는 다른 프로세서에서 병렬적으로 실행될 수 있다.

User Tread

-> 가볍고 빠르다

사용자 수준 thread 라이브러리에서 수행되는 thread 관리 -> 응용프로그램에서 thread 를 생성하고 관리
-thread 생성, 스케줄링 및 관리
-kernel에서 지원되지 않음
-신속한 생성 및 관리
-단일 thread 커널을 사용하면 차단 시스템 호출을 수행하는 하나의 사용자 수준 thread로 인해 전체 프로세스가 차단됨
(OS는 해당 프로세스의 다른 thread의 존재를 모르기 때문에 CPU를 다른 프로세스에 할당합니다)

예

Kernel Thread

커널에서 지원됨
-커널이 스레드 생성, 스케줄링, 관리를 수행함: 사용자 스레드보다 느림
-차단 thread는 전체 프로세스를 차단하지 않음
-MP 기계에서 커널은 다른 프로세서의 thread를 예약할 수 있음

-여러 Thread 간에 컨텍스트 스위칭을 해야 하므로, 성능 저하가 발생할 수 있음

예

Threading Issue