DEVELOPyo

1. Contiguous allocation (연속 할당)

1-1) 고정분할

1-2) 가변분할

2. Noncontiguous allocation (불연속 할당)

1) Paging 기법

- Page table은 main memory 에 상주

- Page-table base register(PTBR)가 page table을 가리킴

- Page-table length register(PTLR)가 테이블 크기를 보관

- 모든 메모리 접근 연산에는 2번의 memory access 필요

- page table 접근 1번, 실제 data/instruction 접근 1번

- 속도 향상을 위해 자주 사용되는 주소값을 가지고 캐시와 같이 가지고 있는 TLB 사용

※ TLB

- TLB 조회시 fullscan이 이루어지므로, parellel search 가 가능한 associative registers 사용

- 주소값이 없으면(miss) page table 사용

- TLB는 context switch 시 flush 된다(process 마다 달라져야 하므로)

※ Two-Level Page Table : 2단계 페이지 테이블

32 bit address 사용시 2^32 (4G) 의 주소 공간

page size 가 4K 일 경우 1M개의 page(=page table entry) 가 필요 ( 4G / 4K = 1M )

각 page entry가 4B 일 경우 프로세스당 4M의 page table 필요 (프로세스 하나에 page table 1개)

사용되지 않는 주소 공간에 대한 outer page table 의 엔트리 값은 NULL (대응하는 inner page table 이 없음)

inner page table의 크기는 page 크기와 동일. inner page table 은 page 내에 존재

page 하나는 4KB(inner page table도 마찬가지),  entry 1개는 4Byte entry 는 총 1K 개

page offset : 4KB(페이지크기) = 2^12 

P2 : page entry 갯수 1K = 2^10

P1은 outer pager table 의 index

P2는 outer page table의 page에서의 변위(displacement)

※ Multi-Level Paging : 멀티 레벨 페이징

- Address space가 커지면 다단계 페이지 테이블 필요

- 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address변환에 더 많은 메모리 접근 필요

- TLB를 통해 메모리 접근 시간을 줄일 수 있음

Memory Protection

Page table의 각 entry 마다 아래의 bit를 둔다

1) Protection bit

 : page에 대한 read/write/read-only 권한

 ex) code영역은 read-only, data 및 stack 영역은 read/write

2) Valid-invalid bit (아래 그림 참고)

 : valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함(접근 허용)

 : invalid는 해당 주소의 frame에 유효한 내용이 없음을 뜻함

  (프로세스가 그 주소 부분을 사용하지 않거나 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우)

Inverted Page Table

- Page frame 하나당 page table에 하나의 entry 를 둔 것(system-wide:시스템에 하나만 존재)

- 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시(process-id, process의 logical address)

- 물리주소로 논리주소를 역으로 찾아야 하기 때문에(value 기준으로 key를 찾아야) 검색에 overhead가 큼(associative register 사용하여 해당 문제 해소)

- 기존의 테이블 페이지 구조와 정반대의 구조

1) 페이지 테이블 : 프로세스 페이지 번호를 기준으로 page table에서 logical address를 physical address 로 변환(정방향)

2) inverted 페이지 테이블 : page table의 entry에 physical memory 에 들어있는 logical address 주소가 들어 있음(역방향)

- 모든 process 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재(배열과 비슷한 구조), 대응하는 page가 메모리에 있든 아니든 간에 page table에는 entry로 존재와 같은 page table 의 문제점을 inverted page table은 갖지 않음.

Shared Page

- Re-entrant Code(=Pure code) : 재진입가능한 코드

- read-only로 하여 프로세스 간 하나의 code만 메모리에 올린다 

- Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 한다

Private code and data

- 각 프로세스들은 독자적으로 메모리에 올림

- private data는 logical address space의 아무곳에 와도 무방

2) Segmentation Architecture

- Logical address 는 segment-number(s), offset(d) 으로 구성

- 각각의 segment table 은 limit(segment의 길이), base(segment 의 시작 물리 주소) 를 가짐

- Segment-table base register(STBR) : 물리적 메모리에서의 segment table 위치

- Segment-table length register(STLR) : 프로그램이 사용하는 segment의 수

if (s > STLR) trap

if (limit < d)  trap

장점 : segment 는 의미 단위이기 때문에 Sharing과 protection에 있어 paging 보다 훨씬 효과적

단점 : segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들이 발생

※ 이화여대 반효경 교수님의 운영체제 강의 정리

Allocation of Physical Memory : 메모리 할당

메모리는 일반적으로 두 영역으로 나뉘어 사용

1) OS 상주 영역 : interrupt vector 와 함께 낮은 주소 영역 사용

2) 사용자 프로세스 영역 : 높은 주소 영역 사용

사용자 프로세스 영역의 할당 방법

1. Contiguous allocation (연속 할당)

: 각각의 프로세스가 메모리의 연속적인 공간에 적재

1) 고정 분할 방식

- 물리적 메모리를 몇 개의 영구적 분할로 나눈다

- 분할당 하나의 프로그램을 적재

- 내부/외부 조각이 발생

  * 외부조각 : 프로그램의 크기보다 분할의 크기가 작은 경우,

                 아무 프로그램에도 배정되지 않은 빈 공간이지만 프로그램이 올라갈 수 없는 작은 분할

  * 내부조각 : 프로그램 크기보다 분할의 크기가 큰 경우,

                 특정 프로그램에 배정되었지만 사용되지 않는 공간

2) 가변 분할 방식

- 프로그램 크기를 고려해서 할당

- 분할의 크기, 개수가 동적으로 변함

- 기술적 관리 기법 필요

  * 외부조각 발생 : B가 끝나서 비어있는 공간이 발생했지만 프로그램 D가 해당 빈 공간 보다 커서 사용할 수 없음

Hole

- 가용 메모리 공간

- 다양한 크기의 Hole 들이 메모리 여러 곳에 존재

- 프로세스가 도착하면 수용가능한 hole 을 할당

- 운영체제는 다음의 정보를 유지 

  할당 공간, 가용 공간(hole)

Hole 을 어떻게 관리 할 것인가?

: Dynamic Storage-Allocation Problem

: 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제

1) First-fit

- Size 가 n 이상인 것 중 최초로 찾아지는 hole 에 할당

2) Best-fit

- Size 가 n 이상인 가장 작은 hole을 찾아서 할당

- 많은 수의 아주 작은 hole들이 생성됨

3) Worst-fit (First-fit, Best-fit 보다 속도/공간 이용률이 비효율적)

- 가장 큰 hole에 할당

- 상대적으로 아주 큰 hole들이 생성됨

※ Compaction

- 외부 조각 문제를 해결하는 방법

- 사용 중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것

- 비용이 매우 많이 드는 방법

- 최소한의 메모리 이동으로 compaction 하는 방법

- 프로세스 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행 가능

2. Noncontiguous allocation (불연속 할당)

: 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라감

1) Paging 기법

2) Segmentation 기법

※ 이화여대 반효경 교수님의 운영체제 강의 정리

메모리의 주소를 크게 두가지로 나눌 수 있다

Logical address(=virtual address)

- 프로세스마다 독립적으로 가지는 주소 공간

- 각 프로세스마다 0번지부터 시작

- CPU가 보는 주소는 logical address

Physical address

- 메모리에 실제 올라가는 위치

주소 바인딩 : 프로그램이 실제로 메모리에 올라 갈 때 주소를 결정하는 것

Symbolic Address > Logical Address > Physical address

주소 바인딩(Address Binding) 방식의 종류

1) Compile time binding

- 물리적 메모리 주소가 컴파일시 알려짐

- 시작 위치 변경시 재컴파일

- 컴파일러는 절대 코드 생성

2) Load time binding

- loader의 책임하에 물리적 메모리 주소 부여

- 컴파일러가 재배치가능코드를 생성한 경우 가능

3) Runtime binding

- 수행이 시작된 이후에도 프로세스의 메모리상 위치를 옮길 수 있음

- CPU가 주소를 참조할 때마다 binding을 점검

- 하드웨어적인 지원이 필요(base and limit registers MMU)

Memory Management Unit (MMU)

logical address를 physical address로 매핑해 주는 Hardware device

※ MMU scheme

사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register(=relocation register)의 값을 더한다

※ user program

logical address만을 다룬다

실제 physical address를 볼 수 없으며 알 필요가 없다

1) CPU가 현재 실행중인 process p1의 논리주소 346 요청

2) process p1 은 물리주소 14000번부터 올라가 있음

3) 프로그램(process p1)이 혹여 자신의 메모리 범위(3000)가 아닌 주소를 요청할 경우를 막기위해

    limit register 의 값과 비교를 해본다.

    limit register 보다 요청 주소가 크다면 trap interrupt 발생 후 운영체제로 제어권을 넘긴다

3) 그렇지 않다면, 시작위치 물리주소인 base register(relocation register)에 논리주소를 더해 돌려줌 (14000+346)

Dynamic Loading (동적 로딩)

- 프로세스 전체를 메모리에 미리 다 올리는게 아니라 해당 루틴이 불려질 때 메모리에 load 하는 것

- memory utilization 의 향상

- 가끔씩 사용되는 많은 양의 코드의 경우 유용 ex)오류 처리 루틴

- 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능(OS는 라이브러리를 통해 지원 가능)

Overlays

- 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올린다

- 프로세스의 크기가 메모리보다 클 때 유용

- 운영체제의 지원없이 사용자에 의해 구현

- 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현(프로그래밍 매우 복잡)

Swapping

- 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것

  * backing store(=swap area) : 디스크 (많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간

Swap in / Swap out

- 일반적으로 중기 스케쥴러(swapper)에 의해 swap out 시킬 프로세스 선정

- priority-based CPU scheduling algorithm

  priority가 낮은 프로세스를 swapped out 시킨다, priority가 높은 프로세스를 메모리에 올려놓는다

- Compile time binding 혹은 load time binding 을 사용하는 경우 swapping 후 원래 주소로 복귀(Swap in)해야 하므로 효율적이지 못하다

- Runtime binding 에서 효율적이다

- swap time 은 대부분 transfer time(swap되는 양에 비례하는 시간)

※ 페이징 시스템에서 일부 페이지가 메모리에서 쫓겨날 때도 swap out 이라고 표현하지만 원칙적으로 swap out은 프로그램을 구성하는 메모리 전부가 쫓겨남을 의미

Dynamic Linking

Linking을 실행 시간(execution time)까지 미루는 기법

1) Static linking

- 라이브러리가 프로그램의 실행 파일 코드에 포함됨

- 실행 파일의 크기가 커짐

- 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비

2) Dynamic linking (=Shared library =DLL(dynamic linking library))

- 라이브러리가 실행시 연결(link)됨

- 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠

- 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴

- 운영체제의 도움이 필요

※ 이화여대 반효경 교수님의 운영체제 강의 정리

교착상태 Deadlock

일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태

Resource (자원)

- 하드웨어, 소프트웨어 등을 포함하는 개념

  ex) I/O device, CPU cycle, memory space, semaphore 등

- 프로세스가 자원을 사용하는 절차

  : Request, Allocate, Use, Release

Deadlock example 1]

시스템에 2개의 tape drive가 있고

프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다

Deadlock example 2]

Binary semaphores A and B

Deadlock 발생의 4가지 조건

1. Mutual exclusion (상호 배제)

  : 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

2. No preemption (비선점)

  : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

3. Hold and wait (보유대기)

  : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

4. Circular wait (순환대기)

  : 자원을 기다리는 프로세스간에 사이클이 형성되어야 함

Resource-Allocation Graph

좌측은 deadlock 우측은 deadlock 아님

좌측 : P1에게 R2 자원 1개 가있고, P2에게 R2 자원 1개가 가있는 상황, P3가 R2자원 하나 더 요구

        P2 은 R3 자원 요청, R3은 P3 가 가지고 있고 P1 은 R1을 요청하나 이는 P2 가 가지고 있으므로

        모든 프로세스가 자원을 반납할 수 없는 상황 즉, deadlock 상태

우측 : P1에게 R2 자원 1개 가있고, P4에게 R2 자원 1개 가있는 상황, P3가 R2 자원 요구 

        P4가 자원 반납시 문제가 없음 

그래프에 cycle이 없으면 deadlock이 아니다

그래프에 cycle이 있으면

if only one instance per resource type, then deadlock

if several instances per resource type, possibility of deadlock

Deadlock 처리 방법

1. Deadlock prevention

: 자원 할당 시 deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

ex)

비선점방식을 선점방식으로,

가지고 있으면서 대기하지 못하도록(자원 요청시 보유한 자원 반납),

자원 유형에 할당 순서를 정하여 정해진 순서대로만 할당 

2. Deadlock Avoidance

: 자원 요청에 대한 부가적인 정보(최대 요청 자원양)를 이용해서 자원 할당이 deadlock으로부터 안전한지를 동적으로 조사하여 안전한 경우에만 할당

: 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법

ex)

※ Banker's algorithm

현재 요청(Need)을 충족시킬 수 있는 자원상황(Available)이라 할 지라도 최대 요청(Max) 가능성을 염두하여 현재 자원상황을 초과할 가능성이 있다면 자원 할당하지 않음. 

3. Deadlock detection and recovery

: deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover

1) Process termination

- 데드락과 관련된 모든 프로세스를 죽인다

- 데드락이 풀릴 때 까지 데드락과 관련된 프로세스를 한 개 씩 죽인다

2) Resource Preemption

- 비용을 최소화할 victim 선정

- safe state 로 rollback 하여 process를 restart

- 동일한 프로세스가 계속해서 victim으로 선정되는 경우 starvation 문제 (cost factor에 rollback 횟수도 같이 고려)

4. Deadlock ignorance

: deadlock 을 시스템이 책임지지 않음, 현대 대부분의 OS는 해당 처리방법을 채택

- Deadlock이 매우 드물게 발생하므로 데드락 조치 자체가 더 큰 overhead 일 수 있음

- deadlock 발생하여 시스템이 비정상적일 경우 유저가 직접 process를 죽이는 방법으로 대처

※ 이화여대 반효경 교수님의 운영체제 강의 정리

1. Bounded-Buffer Problem : 공유버퍼 문제 (Producer-Consumer Problem)

Producer : 데이터를 넣어주는 생산자

Comsumer : 데이터를 사용하는 소비자

발생하는 문제

1) 복수의 생산자 동시접근

2) 복수의 소비자 동시접근

3) 버퍼가 꽉 차있을 때 생산자의 접근

4) 버퍼가 비어있을 때 소비자의 접근

Shared data]

buffer 자체 및 buffer 조작 변수(empty/full buffer의 시작 위치)

Synchronization variables]

mutual exclusion : need binary semaphore (공유데이터의 상호배제를 위해(자원 접근 넣고 빼기))

resource count : need integer semaphore (남은 full/empty buffer 수 표시를 위해(가용자원에 대한 문제))

Synchronization variables
semaphore full = 0, empty = n, mutex = 1; // lock을 거는용 mutex, 비어있는 변수 empty, 내용있는 버퍼 full

Producer
do {
   P(empty);    //빈 버퍼 확인 후 기다리거나 획득하거나
   P(mutex);    //버퍼 획득시 lock 걸기
   add x to buffer
   V(mutex);   //버퍼 반납 후 lock 풀기
   V(full);       //데이터 넣은 버퍼 갯수 증가
} while(1);

Consumer
do {
   P(full);       //데이터 있는 버퍼 확인 후 기다리거나 획득하거나
   P(mutex);   //버퍼 획득시 lock 걸기
   remove an item from buffer to y
   V(mutex);   //버퍼 반납 후 lock 풀기
   V(empty);   //비어있는 버퍼 갯수 증가
} while(1);

2. Readers-Writers Problem : 읽고 쓰기 문제

한 프로세스가 DB에 write 중일 때 다른 process가 접근하면 안된다

read는 동시에 여럿이 해도 된다

solution

- writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 reader들을 다 DB에 접근하게 해준다

- writer는 대기 중인 reader가 하나도 없을 때 DB접근이 허용된다

- writer가 DB에 접근 중이면 reader들은 접근이 금지된다

- writer가 DB에서 빠져나가야만 reader의 접근이 허용된다

Shared data]

DB 자체

readcount (현재 DB에 접근 중인 reader 의 수)

Synchronization variables]

mutex : 공유 변수 readcount를 접근하는 코드(critical section)의 mutual exclusion 보장을 위해 사용

db : reader 와 writer 가 공유 DB 자체를 올바르게 접근하게 하는 역할

Shared data
int readcount = 0;
DB 자체;
Synchronization variables
semaphore mutex=1, db=1; //mutex 는 readcount 에 대한 lock 용, db는 DB lock 용

Writer
P(db);  // Starvation 발생 가능 (Reader 가 계속 들어와서 존재할 경우 Writer 순서가 오지 않음)
writing DB is performed
V(db);

Reader
P(mutex); // readcount 도 mutex 가 보장되어야 하므로 readcount lock시킨다
readcount++;
if(readcount==1) P(db); //block writer : 최초의 reader 접근시 writer lock시킨다
V(mutex); //readers follow
reading DB is performed
P(mutex);
readcount--;
if(readcount == 0) V(db);  //enable writer (writer lock을 푼다)
V(mutex);

3. Dining-Philosophers Problem

Dead lock 의 가능성

해결방안 :

1) 최대 4명만 동시에 테이블에 앉도록

2) 젓가락을 두 개 모두 집을 수 있을 때만 젓가락을 집을 수 있게 한다

3) 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록

2번 해결방안에 대한 코드]

Semaphore의 문제점

- 코딩하기 힘들다

- 정확성(correctness)의 입증이 어렵다

- 자발적 협력(voluntary cooperation)이 필요하다

- 한번의 실수가 모든 시스템에 치명적 영향을 준다

실수의 예]

Monitor

: 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct (java 디자인 패턴에서 어댑터 패턴을 사용하여 세마포를 캡슐화한 어댑터와 비슷한 느낌)

- 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능

- 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음

- 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용

- Condition variable 은 wait과 signal 연산에 의해서만 접근 가능

x.wait()

: x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend 된다

x.signal()

: x.signal()은 정확하게 하나의 suspend 된 프로세스를 resume 한다

Suspend된 프로세스가 없으면 아무 일도 일어나지 않는다

monitor 를 사용한 bounded buffer 문제 해결 코드]

monitor bounded_buffer
{
   int buffer[N];
   condition full, empty;
   // condition var은 값을 가지지 않고 자신의 큐에 프로세스를 매달아서 sleep 시키거나
   // 큐에서 프로세스를 깨우는 역할만 함

   void produce(int x){
      empty.wait(); // if there is no empty buffer 
      full.signal(); // add x to an empty buffer
   }
   void consume(int x){
      full.wait(); // if there is no full buffer
      empty.signal(); // remove an item from buffer and store it top x
   }
}

monitor 를 사용한 dining philosopher 문제 해결 코드]

※ 이화여대 반효경 교수님의 운영체제 강의 정리

Semaphores 

임계영역 문제를 해결하기 위한 알고리즘(참고)들을 추상화 시킴

[Semaphore S]

integer variable

아래 두가지 atomic 연산에 의해서만 접근 가능

P(S) 자원 있으면 가져감

while(S<=0) do no-op;  //wait : busy-wait
S--;

V(S) 반납

S++;

[세마포를 사용한 임계영역문제 해결 : busy-wait (=spin lock)]

Synchronization variable
semaphore mutex; // mutual exclusion

do {
   P(mutex);        // if positive, decrement & enter, otherwise, wait
   critical section
   V(mutex);        // Increment semaphore
   remainder section
} while(1);

[세마포를 사용한 임계영역문제 해결 : block-wakeup]

Semaphore 정의]
여기서 value는 상호배제를 위한 flag용도가 아닌 가용한 자원의 수

typedef struct
{
   int value;             // semaphore
   struct process *L;   // process wait queue
}

block 과 wakeup을 다음과 같이 가정]

block :

커널은 block을 호출한 프로세스를 suspend 시킨다

이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다

wakeup(P) :

block된 프로세스 P를 wakeup 시킨다

이 프로세스의 PCB를 ready queue로 옮긴다

P(S)

S.value--;
if(S.value < 0){
   add this process to S.L;
   block();
}

V(S)
부등호가 <= 인 이유는,
value가 0보다 작을 경우 자원을 기다리는 프로세스가 있음을 의미하므로 value가 0보가 작을 때 wake up 함

S.value++;
if(S.value <= 0){
   remove a process P from S.L;
   wakeup(P);
}

일반적으로 Busy-wait보단 Block/wakeup를 사용

Critical section 길이가 매우 짧은 경우 Block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수도 있다

[ 두가지 유형의 Semaphores ]

1) Counting semaphore 

도메인이 0 이상인 임의의 정수값

주로 resource counting(가용한 자원 수 카운트용)에 사용

2) Binary semaphore (=mutex)

0 또는 1 값만 가질 수 있는 semaphore

주로 mutual exclusion (lock/unlock)에 사용

※ Deadlock (교착상태)

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

※ Starvation (기아)

indefinite blocking.

세마포어 큐에서 빠져나갈 수 없는 현상

(deadlock 도 일종의 starvation)

[Deadlock, Starvation의 예 : Dining-Philosophers Problem]

한 사람이 양쪽의 젓가락 한짝씩 들어서 한 쌍을 만들어야 식사가 가능하다고 할 때,

Dead lock 은 모든 사람들이 자신의 자리에서 오른쪽(왼쪽) 젓가락을 사용하여 모두가 식사를 시작하지 못하는 상황

Starvation 은 사람 A의 좌우 사람이 젓가락을 가지고 식사를 하여 A 가 식사를 시작하지 못하는 상황

※ 이화여대 반효경 교수님의 운영체제 강의 정리

[Process Synchronization]

공유 데이터(shared data)의 동시 접근(concurrent acecss)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다

일관성(consistency)를 위해 협력프로세스간의 실행순서를 정해주는 메커니즘이 필요

[Race condition]

여러 프로세스들이 동시에 공유데이터를 접근하는 상황

데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다

=> race condition을 막기 위해 concurrent process는 동기화(synchronize) 되어야 한다

Process 가 한 개 있는 경우

Process가 두 개 있는 경우

S-box(memory address space)를 공유하는 E-box(CPU process)가 여럿 있는 경우,

Race Condition의 가능성이 있다

[OS에서 race condition이 발생하는 경우]

1) interrupt handler v.s. kernel

커널모드 running 중 interrupt가 발생하여 인터럽트 처리루틴이 수행

커널모드 running 중 interrupt 가 발생하여 인터럽트 처리루틴이 수행

해결책 : 처리가 완료되기 전까지 interrupt를 받아주지 않는다

2) preempt a process running in kernel

해결책 : 커널모드에서 수행 중일 때는 CPU를 preempt(선점) 하지 않음. 커널 모드에서 사용자 모드로 돌아갈 때 preempt

3) multiprocessor

multiprocessor의 경우 위의 케이스들과 달리 interrupt enable/disable로 해결되지 않는다.

해결책 1) 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법

해결책 2) 커널 내부에 있는 각 공유데이터에 접근할 때마다 그 데이터에 대한 lock/unlock을 하는 방법

The Critical-Section problem : 임계영역 문제

n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재

problem : 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다

프로그램적 해결법의 충족 조건

1) Mutual Exclusion (상호배제)

프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다

2) Progress

아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다

3) Bounded Waiting(유한한 대기)

프로세스가 ciritical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다(starvation 방지)

[Critical Section problem 해결 알고리즘 1]

Process0 이 한 번 수행으로 끝이난 경우 Process1 은 다시 들어갈 수 없음

(타 프로세스가 turn 을 내 값으로 바꿔줘야만 내가 들어갈 수 있기 때문) : 과잉양보 발생

-> mutual exclusion 은 만족하나 progress 는 만족하지 않음

Process0]

do {
   while(turn != 0);    // my turn?
   critical section
   turn = 1;
   remainder section  // now it's your turn
} while(1)

Process1]

do { 
   while(turn != 1); // my turn?
   critical section 
   turn = 0;
   remainder section  // now it's your turn
} while(1)

[Critical Section problem 해결 알고리즘 2]

두 프로세스가 2행까지(while문) 수행 후 끊임 없이 양보하는 상황 발생 가능

(critical section 진입 후 flag를 false 로 두어 나왔음을 알리지만 2행까지 실행된 경우 두 프로세스가 loop가 돌며 계속 양보하게 되므로)

Process0, Process1]

do {
   flag[i] = true;   //pretend I am in
   while(flag[j]);    //is he also in? then wait
   critical section
   flag[i] = false;   // i am out now
   remainder section
} while(1);

[Critical Section problem 해결 알고리즘 3]

Peterson's Algorithm

Mutual Exclusion, Progress, Bounded waiting 을 모두 만족

하지만 Busy waiting(=spin lock=loop) : CPU , memory 를 계속 사용하며 wait 

Process0]

do {
   flag[0] = true;   //My intention is to enter
   turn = 1;          // set to his turn
   while(flag[1] && turn == 1);    // wait only if
   critical section
   flag[0] = false;
   remainder section
} while(1);

Process1]

do {
   flag[1] = true;  //My intention is to enter
   turn = 0;        // set to his turn
   while(flag[0] && turn == 0);     // wait only if
   critical section
   flag[1] = false;
   remainder section
} while(1);

하드웨어적으로 Test와 Modify를 atomic 하게(읽기와 쓰기를 한번에(하나의 instruction으로)) 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결

: interrupt 등으로 프로세스가 CPU를 뺏길 때, 실행 하던 instruction은 끝마치고(라인 한 줄) 뺏긴다.

instruction 을 한 줄이 아닌 두개의 instruction 으로 지원하여 instruction+flag처리를 한 번에 다룰 경우, 임계영역에 대한 처리가 간단해진다

Synchronization variable :
boolean lock = false;

do {
   while(Test_and_Set(lock)); 
   critical section
   lock = false;
   remainder section
}

※ 이화여대 반효경 교수님의 운영체제 강의 정리

CPU Scheduling 

CPU를 누구에게 줄것인가, 주고나서 뺏어올 것인가

※ CPU and I/O Bursts in program execution

사용자와의 interaction 이 많은 프로그램일 수록 I/O burst 높다

※ CPU-burst Time의 분포

I/O bound job : I/O 많이 사용, many short CPU bursts

CPU bound job : CPU 많이 사용(계산 위주의 job), few very long CPU bursts.

-> 여러 종류의 job(process)이 섞여 있기 때문에 CPU 스케쥴링이 필요.

※ CPU Scheduler & Dispatcher

- CPU Scheduler :

Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다(OS 안에서 처리됨, 별도의 하드웨어나 소프트웨어가 아님)

- Dispatcher :

CPU 제어권을 CPU scheduler 에 의해 선택된 프로세스에게 넘긴다

이 과정을 context switch(문맥 교환)라고 한다

※ CPU 스케쥴링이 필요한 경우

1. Running -> Blocked (ex: I/O 요청하는 시스템 콜) : 자진 반납(nonpreemptive)

2. Terminate : 자진 반납(nonpreemptive)

3. Blocked -> Ready (ex: I/O완료 후 interrupt) : 강제 반납(preemptive)

4. Running -> Ready (ex: 할당시간만료로 timer interrupt) : 강제 반납(preemptive)

Scheduling Criteria

: Performance Index(=Performance Measure, 성능척도)

1. CPU utillization (이용료)

: Keep the CPU as busy as possible (ex: 주방장이 일하는 시간)

2. Throughput (처리량)

: # of processes that complete their execution per time unit

(ex: 얼마나 많은 손님이 다녀갔는가)

3. Turnaround Time (소요시간, 평균시간)

: amount of time to execute a particular process

cpu 처리시간의 총합

(ex: 손님이 와서 식사 하는 시간의 총합(코스요리의 경우 먹고 쉬고 먹고 쉬고를 반복, 먹는 시간의 합))

4. Waiting time (대기 시간)

: amount of time a process has been waiting in the ready queue

(ex: 손님이 와서 기다리는 시간의 총합(코스요리))

5. Response time (응답 시간)

: amount of time it takes from when a request was submitted until the first response is produced, not output

처음으로 응답되는데 까지 걸리는 시간

(ex: 손님이 와서 밑반찬을 네주는데 걸리는 시간)

※

1, 2 는 시스템 입장에서 CPU 성능척도

3, 4, 5 는 process 입장에서의 성능척도

CPU Scheduling 종류

1. FCFS(First-Come First-Served)

프로세스 도착 순서대로 처리(비선점형 nonpreemptive)

※ 문제점

Convoy effect : short process behind long process

앞에 긴 프로세스가 존재하여 뒤에 짧은 프로세스가 처리되지 못하는 현상

2. SJF(Shortest-Job-First)

- 각 프로세스와 다음번 CPU burst time을 가지고 스케쥴링에 활용

- CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케쥴

1) Nonpreemptive

CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 뺏기지 않음

2) Preemptive

현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗긴다. 이를 SRTF(Shortest-Remaining-Time-First)라고 부른다.

- SJF is optimal(최적화) : 주어진 프로세스에 대해 minimum average waiting time을 보장

※ CPU Burst Time의 예측

- 다음번 CPU burst time 은 추정(estimate)만 가능

- 과거의 CPU burst time 을 이용해서 추정 (exponential averaging)

CPU Burst Time 예측 공식 정리가 되어있는 곳 : https://darkluster.tistory.com/43

3. Priority Scheduling

- A priority number(integer) is associated with each process

- 가장 높은 우선수위를 가진 프로세스에게 CPU 할당(smallest integer = highest priority)

- SJF 는 일종의 priority scheduling

※ 문제점

Starvation(기아현상)

: low priority processes may never execute. (낮은 우선순위 프로세스가 영원히 CPU를 얻지 못하는 것)

※ 해결책

Aging(노화)

: as time progresses increase the priority of the process (시간이 지나면 우선순위를 올려주는 것)

4. Round Robin(RR)

- 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다 (일반적으로 10-100milliseconds)

- 할당 시간이 지나면 프로세스는 선점(preempted) 당하고 ready queue와 제일 뒤에 가서 다시 줄을 선다

- n 개의 프로세스가 ready queue에 있고 할당 시간이 q time unit 인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다 (어떤 프로세스도 (n-1)q time unit 이상을 기다리지 않는다)

※ 장점

1) 응답시간이 빠르다.

2) CPU가 길게 필요하면 길게 기다리고, 짧게 필요하면 짧게 기다린다. (짧은 프로세스는 빨리 나가고 긴 프로세스는 길게(많이) 기다리게 되므로 프로세스의 waiting time 과 turnaround time 이 비례)

※ 할당시간에 따른 차이

q large (할당시간이 길다면) => FCFS

q small (할당시간이 짧다면)=> context switch 오버헤드가 커진다.

Multilevel Queue

Queue가 여러줄이며 우선순위가 높은 큐의 프로세스가 CPU 우선권을 가진다

1) Ready queue를 여러개로 분할

  - foreground (interactive(IO))

  - background(batch - no human interaction)

2) 각 큐는 독립적인 스케쥴링 알고리즘을 가진다

  - foreground - RR (빠른 응답속도)

  - background - FCFS

3) 큐에 대한 스케쥴링 필요

  - Fixed priority scheduling : starvation 문제

  - Time slice : 각 큐에 CPU time을 적절한 비유로 할당한다

    80% to foreground in RR, 20% to background in FCFS

Multilevel Feedback Queue

프로세스 처리가 끝나면 바로 나감, 처리가 끝나지 못하면 두번째 큐로 이동, 또 처리가 되지 못했다면 맨 밑의 큐로 이동

처리가 짧은 프로세스에게 우선권을 먼저 준다

※ Multiple-Processor Scheduling

CPU가 여러개인 경우

1) Homogeneous processor 인 경우

- Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가도록

- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우 문제가 복잡해진다

2) Load sharing

- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요

- 별개의 큐를 두는 방법 vs. 공동 큐를 사용하는 방법

3) Symmetric Multiprocessing(SMP)

- 각 프로세서가 각자 알아서 스케쥴링 결정

4) Asymmetric multiprocessing

- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

※ Real-Time Scheduling

1) Hard real-time systems : 정해진 시간안에 반드시 끝내도록 스케쥴링

2) Soft real-time computing : 일반 프로세스에 비해 높은 우선순위를 갖도록 해야 한다

3. Thread Scheduling

1) Local Scheduling : User level thread 의 경우 사용자 수준의 thread library에 의해 어떤 thread 를 스케쥴할 지 결정

2) Global Scheduling : Kernel level thread 의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케쥴러가 어떤 thread 스케쥴할지 결정 

※ Algoritm Evaluation 알고리즘 평가방법

1) Queueing models

확률 분포로 주어지는 arrival rate와 service rate 등은 통해 각종 performance index 값을 계산

2) Implementation (구현) & Measurement (성능 측정)

실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교

3) Simulation (모의 실험)

알고리즘을 모의 프로그램으로 작성 후 trace를 입력하여 결과 비교

※ 이화여자대학교 반효경 교수님의 운영체제 강의 정리

프로세스 생성

1. 부모 프로세스가 자식 프로세스를 생성

   (COW : Copy-On-Write 자식은 부모 자원을 그대로 공유하여 사용하고 있다가 write 발생할 경우 복사 함)

2. 프로세스의 트리 형성

3. 프로세스는 자원을 필요로 함

  - 운영체제로 부터 받는다

  - 부모와 공유한다

4. 자원의 공유

  1) 부모와 자식이 모든 자원을 공유하는 모델

  2) 일부를 공유하는 모델

  3) 전혀 공유하지 않는 모델

5. 수행(Execution)

 - 부모와 자식은 공존하며 수행되는 모델

 - 자식이 종료(terminate)될 때까지 부모가 기다리는(wait) 모델

주소 공간(Address space)

 - 자식은 부모의 공간을 복사한다

 - 자식은 그 공간에 새로운 프로그램을 올린다

ex) UNIX 

  1) fork() 시스템 콜이 새로운 프로세스 생성

    - 부모를 그대로 복사

    - 주소 공간 할당

  2) fork 다음에 이어지는 exec() 시스템 콜을 통해 새로운 프로그램을 메모리에 올린다

프로세스와 관련된 시스템 콜

1. fork() : create a child(copy)

A process is created by the fork() system call.

: creates a new address space that is a duplicate of the caller.

int main() {
   int pid;
   pid = fork();
   if(pid == 0) /* child */
      printf("\n Hello, I am child\n");
   else if (pid > 0) /* parent */
      printf("\n Hello, I am parent\n");
}

fork() 실행시 자식 프로세스가 생겨서 부모 프로세스를 그대로 복제하며

부모 프로세스 Program Counter 도 복제하여, fork() 다음의 if(pid == 0) 라인부터 실행

* 자식 프로세스는 pid = fork(); 이전 라인을 실행하지 못함

2. exec() : overlay new image

A process can execute a different program by the exec() system call.

: replaces the memory image of the caller with a new program.

int main() {
   int pid;
   pid = fork();
   if(pid == 0) { /* child */
      printf("\n Hello, I am child\n");
      execIp("echo", "echo", (char *) 0);
   } else if (pid > 0){ /* parent */
         printf("\n Hello, I am parent\n");
   }
   printf("2");
}

fork() 없이 execIp() 만 사용가능

execIp 를 만나는 순간 새로운 프로그램이 기존 프로그램을 덮어쓰게 되며 echo 가 실행되므로

printf("2"); 는 실행 될 수 없음

3. wait() : sleep until child is done

프로세스 A가 wait() 시스템 콜을 호출하면

1) 커널은 child가 종료될 때까지 프로세스 A를 sleep 시킨다 (block 상태)

2) child process 가 종료되면 커널은 프로세스 A를 깨운다 (ready 상태)

: 자식이 종료(terminate)될 때까지 부모가 기다리는(wait) 모델

main {
   int childPID;
   childPID = fork();
   if(childPID == 0){
     <code for child process>    
   } else {
      wait();
   }
}

fork 로 자식 프로세스 생성

wait() 으로 부모프로세스가 sleep,

자식 프로세스가 CPU를 얻어서 자식 프로세스의 코드(code for child process)가 실행 된 후(끝난 후)

부모 프로세스가 깨어난다.

4. exit() : frees all the resources, notify parent

프로세스의 종료

1. 자발적 종료

   1) 마지막 statement 수행 후 exit() 시스템 콜을 통해

   2) 프로그램에 명시적으로 적어주지 안하도 main 함수가 리턴되는 위치에 컴파일러가 넣어준다

2. 비자발적 종료

   1) 부모 프로세스가 자식 프로세스를 강제로 종료시킨다

     - 자식 프로세스가 한계치를 넘어선 자원을 요청할 때

     - 자식에게 할당된 task가 더 이상 필요하지 않을 때

   2) 키보드로 kill, break 등을 친 경우

   3) 부모가 종료하는 경우

     - 부모 프로세스가 종료하기 전에 자식들이 먼저 종료된다

프로세스 종료

1. 프로세스가 마지막 명령을 수행한 후 운영체제에게 이를 알려준다(exit)

 - 자식이 부모에게 output data를 보낸다 (via wait)

 - 프로세스의 각종 자원들이 운영체제에게 반납된다

2. 부모 프로세스가 자식의 수행을 종료시킴 (abort)

 1) 자식이 할당 자원의 한계치를 넘어설 때

 2) 자식에게 할당된 테스크가 더 이상 필요하지 않을 때

 3) 부모가 종료(exit)해야하는 경우

   - 운영체제는 부모 프로세스가 종료하는 경우 자식이 더 이상 수행되도록 두지 않는다

   - 딸려있는 모든 자식을 종료시킨 후 부모를 죽이는 단계적인 종료

프로세스 간 협력

1. 독립적 프로세스(Independent process)

  : 프로세스는 각자의 주소 공간을 가지고 수행되므로 원칙적으로 하나의 프로세스는 다른 프로세스의 수행에 영향을

    미치지 못한다

2. 협력 프로세스(Cooperating process)

  : 프로세스 협력 메커니즘을 통해 하나의 프로세스가 다른 프로세스의 수행에 영향을 미칠 수 있음

3. 프로세스 간 협력 메커니즘(IPC : Interprocess Communication)

1) 메시지를 전달하는 방법

- message passing : 커널을 통해 메시지 전달. 프로세스 사이에 공유 변수를 사용하지 않고 통신하는 시스템

a. Direct Communication : 통신하려는 프로세스의 이름을 명시적으로 표시 

b. Indirect Communication : mailbox(또는 port)를 통해 메시지 간접 전달

2) 주소 공간을 공유하는 방법

- shared memory : 서로 다른 프로세스 간에도 일부 주소 공간을 공유하게 하는 shared memory 메커니즘이 있음

※ thread : thread는 사실상 하나의 프로세스이므로 프로세스 간 협력으로 보기는 어렵지만 동일한 process를 구성하는 thread들 간에는 주소 공간을 공유하므로 협력이 가능

※ 이화여대 반효경 교수님의 운영체제 강의 정리

Thread

프로세스(heavyweight process) 내부에 CPU 수행 단위가 여러개 존재하는 것

CPU를 수행하는 단위

"A thread (or lightweight process is a basic unit of CPU utilication"

[Process 정보를 담고 있는 Process Control Block]

[PCB 내에서의 Thread]

data, code 등 메모리 공유가 가능한 자원은 최대한 공유(※ 공유하는 부분은 Task 라 칭함)하며,

CPU 수행과 관련된 Program Counter, registers, Stack 영역은 별도로 가진다. 

Thread 사용시 기대 효과

1) 다중 스레드로 구성된 태스크 구조에서는 하나의 서버 스레드가 blocked(waiting) 상태인 동안에도 동일한 태스크 내의 다른 스레드가 실행(running)되어 빠른 처리 가능.

2) 동일한 일을 수행하는 다중 스레드가 협력하여 높은 처리율(throughput)과 성능을 얻을 수 있다

3) 병렬성을 높일 수 있다(CPU가 여러개인 컴퓨터인 경우)

Thread 사용시 장점

- Responsiveness " if one thread is blocked, another thread continues

- Resource Sharing : n threads can share binary code, data, resource of the process

- Economy : creating & CPU switching thread rather than a process (overhead)

- Utilization of MP(Multi Processor) Architectures : each thread may be running in parallel on a different processor

Thread 구현 방식

- Kernel Threads (supported by kernel)

- User Threads (supported by library)

- Real-time Threads

※ 이화여대 반효경 교수님의 운영체제 강의내용 정리