4. 프로세스 관리 + 3. 주기억장치 관리

동기화 알고리즘(synchronization algorithm): 임계 구역(Critical Section)에 한 순간에 한 프로세스 만 접근이 가능하도록 보장하는 알고리즘

동기화 알고리즘의 목표는 상호배제(Mutual Exclusion), 진행 조건(Progress), 한정 대기(Bounded Waiting) 이 3가지를 만족시키는 것이다

상호 배제(Mutual Exclusion): 한번에 하나의 프로세스만 공유 자원을 사용하는 것

진행 조건(Progress): 임계구역에 들어갈 프로세스가 없다면 누가 들어갈지 결정하는 과정에서 불필요한 대기가 없음

한정 대기(Bounded Waiting): 특정 프로세스가 무한정 기다리지 않음

 

* busy waiting

어떤 프로세스가 임계구역에 접근하기 위하여 CPU를 가진 상태에서 임계 구역 접근이 허용될 때까지 무한 루프를 수행하는 상태

장점: 임계 구역 코드 길이가 짧을 경우 효과적인 수행이 될 수 있다

단점: CPU 자원을 낭비하게 되는 요인이 된다

 

소프트웨어 기반 동기화 알고리즘: 피터슨 알고리즘(Peterson's Algorithm), 데커 알고리즘(Dekker's Algorithm) 

하드웨어 기반 동기화 알고리즘: Test-and-Set(TAS)

 

세마포어(Semaphore) 알고리즘: 운영체제(OS)에서 프로세스/스레드 간의 동기화와 상호배제를 제공하는 가장 기본적이고 강력한 매커니즘

세마포어(Semaphore): 공유 자원에 접근할 수 있는 프로세스 수를 제어하기 위한 정수 변수이다 P, Y

이 변수를 조작하는 두가지 원자적 연산 P(), Y()로 구성된다

P(S)는 S = S - 1을 하고, 만약에 S < 0 이면 프로세스는 S에서 슬립한다

자원을 사용하고 싶을 때 호출하고 세마포어 값이 충분하면 감소시키고 계속 진행하지만 부족하면 슬립을 해서 대기한다는 것이다

V(S)는 S <= 0 이면 대기 큐에서 프로세스를 깨우고 자원을 바로 넘긴다. 아니라면 S = S + 1 을 해서 자원을 반납한다

 

생산자-소비자(Producer-Consumer) 문제는 운영체제와 병렬 프로그래밍에서 가장 대표적인 동기화 문제이다. 프로세스간 통신(IPC: InterProcess Communicaiton)의 대표적인 보기이며 데이터 처리를 하는 프로그램에서 주로 사용한다. 

여러 프로세스 또는 스레드가 공유 버퍼(Shared Buffer)를 사용하면서 충돌이나 데이터 손상을 막는 것이 핵심 목표

기본 구성은 생산자 프로세스(Producer), 소비자 프로세스(Consumer), 공유 버퍼(Shared Buffer)

동시에 접근하면 경쟁 조건(Race Condition)이 발생하며 데이터 손상이 일어나므로 동시에 접근하면 

 

교착상태(Dead Lock)는 두 개 이상의 프로세스가 자신이 가진 자원은 계속 가지고 있으면서 서로 상대방이 가진 자원을 요구하게 되는 상태

교착 상태 발생의 4가지 조건

1. 상호배제 조건

프로세스들이 필요로 하는 자원에 대해 베타적인 통제권을 요구하는 것

2. 대기 조건

할당된 자원을 가진 상태에서 다른 자원을 기다리는 경우

3. 비중단 조건

프로세스에 할당된 자원은 사용이 끝날 때까지 프로세스로부터 제거할 수 없다

4. 환형 대기 조건

자원할당 그래프 내에서 환형 대기가 발생하는 것

이 4가지 조건이 동시에 만족되면 교착상태가 발생한다

 

이 조건 중 하나를 원칙적으로 깨뜨려서 교착상태가 발생하지 않도록 만드는 것이 예방 방법

 

1. 상호배제 조건은 자원 특성상 동시에 사용 불가능하기 때문에 방지할 수 없거나 커널의 데이터에 대해서 무결성이 보장되지 않으므로 불가능함.

2. 대기 조건을 방지하면 모든 자원을 일시에 요구해야 하며 자원의 심한 낭비를 초래하게 되거나 컴퓨터에 자원이 무한정으로 공급되어야 하므로 현실적으로 불가능.

3. 비중단 조건을 방지하면 프로세스는 자원 요구를 거절 당할 경우 자신이 가지고 있는 자원을 모두 반납하게 된다. 자원이 회수된 프로세스는 다음 번에 처음부터 시해해야 하는 문제가 발생한다.

4. 환형 대기 조건의 방지는 자원 할당 그래프 내의 circular wait가 발생하지 않도록 하는 것이다. 가장 현실적인 방법이지만 프로세스의 개수가 아주 클 경우 NP-hard problem으로 풀기 어려운 문제가 된다. 자원 요청 순서 설계가 복잡해져서 각 프로세스가 사용할 자원 세트가 다르면 모든 자원에 대해 순서를 정하거나 또 잘못 설계 했을 시 일부 프로세스가 불필요하게 대기하거나 자원을 못 쓱 될 수도 있다.

 

3장 주기억장치 관리

계층적인 기억 장치

- 캐시 저장 장치(cache storage device)

- 주기억장치(main memory)

- 보조기억장치

 

프로그램의 실행 과정

- CPU는 실행할 프로그램을 주 기억 장치로 가져와야(load program into main memory) 실행이 가능

- 주기억 장치로 실행할 프로그램을 가지고 오는 과정

 

컴파일(compile)

컴파일러(compiler)는 소스 프로그램을 이용하여 목적 코드를 생성하는 역할 수행

 

주소 연결(Adress Binding)

프로그램은 일반적으로 상대주소(relative address)의 개념을 가짐

프로그램이 사용하는 주소(논리 주소)를 실제 메모리의 물리 주소와 연결(binding) 시키는 과정

 

재배치(relocation)

- 운영체제가 프로그램을 메모리의 다른 위치로 옮기거나 프로그램 코드 안의 주소들을 다른 실제 주소에 맞게 다시 계산해주는 과정

- symbol table에 있는 symbol(variable)들에 대해서 실제 주소로 binding (linkage editor, loader)

 

OS에서는 보통 address binding이 언제 결정되느냐에 따라 3가지 종류

컴파일 시간 바인딩(compile time binding): 프로세스가 기억 장치 내에 적재될 위치를 결정하여 컴파일러는 절대 코드를 생성

장점: 성능이 빠르다

단점: 주기억장치 공간 낭비가 심하다

 

적재 시간 바인딩(load time binding): 프로세스가 기억 장치 내의 어디에 상주할 것인지를 컴파일 시간에 알 수 없을 경우 최종 바인딩은 적재 시간이 될 때까지 연기

장점: 주기억장치 공간을 효율적으로 사용 가능

단점: 성능이 느리다

 

수행 시간 바인딩(execution time binding): 프로세스의 주기억장치 주소 공간 할당(주소 계산)이 수행시간에 이루어짐

장점: 공간 사용이 효율적이다

단점: 성능이 느리다

 

동적 연결(Dynamic Linking)이란

라이브러리를 실행 중에 연결하는 것

- 시스템 라이브러리에서 주로 사용하는 개념

- 윈도우 운영체에서 DLL (Dynamic Linking Library) 개념

* DLL (Dynamic Link Library): Windows에서 사용하는 동적 라이브러리 표준, 확장자 .dll

- DLL은 동적 연결의 구현체

 

*정적 연결(static linking)

컴파일/링크 시점에 라이브러리 코드가 실행 파일 안에 포함되는 것

 

address binding은 언제 주소를 정할지 결정하는 것, relocation은 그 결정된 방식대로 실제 주소를 계산하는 것

 

중첩(overly): 동시에 주기억장치에 적재될 필요가 없는 프로세스의 경우에 같은 기억 공간을 사용하는 것

 

스와핑(swapping)

swap out: 주 기억 장치에서 보조 기억 장치로 이주

swap in: 보조 기억 장치에서 주기억 장치로 이주

 

1. 단일 분할 할당(single-partition allocation)

가장 간단한 기억 장치 관리 기법

사용자가 주기억장치 관리에 대한 모든 권한을 소유

단점

- 운영체제가 관리할 수 있는 것이 없다

- 사용자가 운영체제(kernel) 공간에 접근할 수 있어서 보안이 취약해진다 (Vulnerability)

 

다중 프로그래밍(mulitprogramming)

여러 개의 프로그램이 동시에 주기억장치에 상주하면서 CPU가 사용 가능할 경우 즉시 실행할 수 있도록 하는 것

CPU의 우휴 시간(idle time)을 줄이고 시스템 자원을 최대한 활용하는 것이 목표다

장점: CPU 활용이 극대화되고 시스템이 전반적으로 성능이 빨라진다

단점: 바로 실행되지 않는 프로그램이 메모리 공간을 차지하여 주기억장치의 낭비가 발생한다

multiprogramming degree

-> 컴퓨터가 가지고 있는 주기억장치 공간에 따라서 주기억장치에 상주하는 프로그램 개수를 결정

 

2. 고정 분할 다중프로그램

고정 크기 주기억장치 공간 할당 

-> 잘 사용하지 않음,

단점: 비어 있는 주기억장치 공간이 있어도 활용 불가능

 

3. 가변 분할 다중프로그램

프로세스가 필요한 만큼의 기억 공간을 동적으로 할당

사용을 하고 난 공간은 반납(release)

장점: 공간을 효율적으로 사용 가능

단점: fragment가 발생하여 주기적으로 이러한 fragment를 수집해야 한다

 

compaction 

(꼭 필요한 경우에만 사용)

여러 개의 작은 빈 공간을 합쳐서 하나의 큰 공간으로 합치는 작업

: garbage collection

장점

공간을 효율적으로 사용 가능

단점

이 연산의 수행 동안 모든 작업을 중지해서 자원 낭비가 심하다

주기억장치 내에서 프로그램의 이동으로 인하여 새로운 주소 계산이 필요

 

가상기억장치(Virtual Memory)

가상기억장치는 실제 물리적 메모리보다 더 큰 메모리를 사용할 수 있도록 운영체제가 제공하는 기법

프로그램 실행 시 필요한 부분만 주기억장치에 적재하여 효율적인 메모리 사용을 가능하게 한다

 

프로그램 동작이 지역성(locality)을 가지기 때문에 아무리 큰 프로그램도 특정 시점에 특정 프로그램 코드만 주기억장치에 상주하면 프로그램이 실행하는데 아무 문제가 없다는 것에 착안한 개념

가상 기억 장치는 페이징(paging) 기법, 세그먼트(segment) 기법이 있다

장점: 적은 메모리 공간으로 프로그램을 실행할 수 있다 효율적인 주기억장치 사용이 가능하다

단점: 페이지 부재(page fault)로 인한 성능 저하가 발생 가능하다

*page: 가상 메모리를 일정한 고정 크기로 나눈 블록 단위

 

가상 저장 장치

가상 주소 공간과 실 주소 공간 사이의 맵핑이 필요

사용자는 프로그램과 데이터가 실제 저장장치의 어느곳에 위치하는가를 걱정하지 않아도 된다

커널에서 모든 주기억장치 주소 공간을 관리한다

 

블록 사상(block mapping)

운영체제 또는 파일 시스템에서 논리적 주소(블록)를 물리적 주소(블록)로 연결시키는 알고리즘, 구조를 말한다 

디스크에 파일을 저장할 때 파일의 내용은 여러 블록 단위로 끊어 저장된다 파일은 논리적 블록 번호로 접근하고 디스크는 물리적 번호로 저장된다 그렇기에 둘 사이를 매핑해야 한다

매핑 정보를 너무 많이 저장하면 메모리 낭비와 성능 저하가 크기에 map table에 저장되는 정보 양을 줄여야 한다

블록(페이지)가 너무 작으면 개수가 너무 많아져서 관리 정보가 폭증하기 때문에 블록 크기를 가능한 한 크게 해서 과의 단위를 줄여야 한다

map table은 block mapping의 결과를 표 형식으로 저장한 실제 자료구조

 

블록 크기를 일정하게 할 경우: Paging 기법

주 기억장치 공간을 일정한 크기로 나눈다. 이 일정하게 나눈 크기를 페이지(page)라고 한다. 메모리 할당을 페이지 단위로 수행하는 것이 페이지 기법.

장점: 주기억장치 할당 및 주소 계산이 아주 간단해서 성능이 우수하다

단점: 항상 일정한 크기로 메모리를 할당하기 때문에 페이지에 사용되지 않는 공간 낭비가 발생한다

 

블록 크기를 다르게 할 경우: Segment 기법

가변적인 크기로 주기억장치 할당

저장 장치를 보호하는 것이 복잡하다 (보안에 취약하다)

장점: 효율적인 메모리 사용을 보장한다

단점: 기억 장치 내의 빈 공간들이 많이 발생한다

 

<페이징 시스템에서 주소 매핑 기법>

1. 직접 사상(direct mapping)에 의한 페이지 주소 변환

page map table 정보를 일반 주기억장치 공간(RAM)에 탑재시키고 주소 변환을 수행

장점: 비용이 저렴하다

단점: 성능이 떨어진다

CPU가 계속 RAM에 접근해야 함 그래서 느림

 

2. 연관 사상(associative mapping)에 의한 페이지 주소 변환

associative memory에 페이지 map table 정보를 둔다

contents addressable memory (CAM)을 사용, 주소값을 사용하지 않는다

장점: 성능이 아주 빠르다

단점: 비용이 비싸다

CPU에 TLB(CAM으로 구현, 내용 기반 주소 지정 메모리)를 둬서 자주 쓰는거를 순차로 찾는게 아니라 병렬로 비교

 

3. associative/direct을 결합한 페이지 주소 변환

가격이 비싸지 않으면서 빠른 사상 방법

최근에 사용한 페이지는 조만간 다시 사용될 가능성이 높다는 사실에 근거하여 최근 참조한 페이지를 associated memory에 둔다

장점: 비용을 적게 들이고 성능을 향상시킬 수 있다

단점: 비용이 소모되고 성능도 좋지 않은 경우가 발생될 가능성이 있다

자주 사용하는 page map table 정보는 일반 메모리에 탑재

자주 사용하지 않는 page map table은 일반 메모리에 탑재

장점: 비용을 적게 들이고 성능을 향상

단점: 비용이 소모되고 성능도 좋지 않은 경우가 발생될 가능성이 있다

 

페이지 교체 알고리즘(Page Replacement, Algorithm)

주기억 장치에 빈 공간이 없을 경우 커널은 공간 확보를 어떻게 할 것인가?

-> 커널은 기존 주기억장치를 차지하고 있는 페이지를 대체시켜서 공간 확보

페이지 교체 알고리즘

 

FIFO 페이지 교체 알고리즘

주기억장치에 가장 오래 있었던 페이지 교체

가장 오래된 페이지의 판단 기준?

- time stamp 정보를 이용해서 sorting 한다

장점: 구현이 간단

단점: 주기억장치 공간을 늘려도 오히려 page fault가 더 자주 발생

 

FIFO 기법의 모순

프로세스에 더 많은 페이지들을 할당(즉 주기억장치 공간을 늘릴 경우에)할 경우에 오히려 페이지 부재(page fault)가 더 많이 발생

 

1. LRU(Least Recently Used) 페이지 교체 알고리즘

- 가장 오랫동안 사용되지 않은 페이지를 교체

페이지들의 사용한 시간을 기록, 관리(time stamp 정보를 관리)

장점: 구현이 간단하다

단점: 최근에 사용되지 않은 페이지 중 다음에 자주 사용될 가능성이 있는 페이지가 swap out 되는 경우가 발생

 

2. LFU(Least Frequently Used) 페이지 교체 알고리즘

- 호출 빈도가 가장 적은 페이지가 교체

페이지들의 사용 빈도수 정보를 관리

장점: 구현이 간단하다

단점: 최근에 사용된? 페이지가 swapout 되는 경우가 발생

 

3. 재기회(second chance) 페이지 교체 알고리즘

페이지가 참조되면 R 비트를 조사

만약 R비트가 0이면 오래된 것으로 간주하여 페이지 교체

만약 R비트가 1이면 R비트를 0으로 바꿈

 

구역성(locality)

프로그램의 동작은 확률적으로 특정한 시점에 특정한 프로그램 코드를 집중적으로 참조하는 특성을 가짐

구역성을 활용하면 큰 프로그램 코드의 일부분만 주기억장치에 탑재시켜도 동작이 가능

구역성은 사용자 프로그램의 순차적인 수행으로 인해 발생되는 현상

 

시간 구역성(Temporal Locality)

최근에 사용한 데이터나 명령어는 가까운 미래에 다시 사용될 가능성이 높다

- 순환(loop)

- subroutine 

- stack

 

공간 구역성(Spatial Locality)

어떤 메모리 주소를 접근하면 그 근처 주소들도 곧 접근할 가능성이 높다

- 배열

 

워킹 셋(Working Set)

하나의 프로세스가 자주 참조하는 페이지들의 집합

working set은 계속적으로 주기억 장치에 유지 관리시켜주는 것이 좋은데 그 이유는 프로그램이 수행하는데 필요한 페이지들이 주기억장치에 상주함으로써 IO 연산 등이 발생하지 않기 때문에 (성능이 우수)

페이지 교체를 효율적으로 관리하기 위해 사용되며 운영체제의 메모리 관리에서 중요한 역할을 수행

working set은 프로세스가 정상적인 속도로 실행되려면 디스크가 아니라 RAM에 있어야 함

 

요구 페이징(demand paging)

프로그램 실행시 페이지가 명백히 참조될 때에만 보조기억장치에서 주기억장치로 이송

프로그램의 실행 순서를 정확히 예측이 불가능하기 때문에 이 방법이 우수하다

수행중인 프로그램에서 필요한 데이터나 코드(페이지)를 실제 필요한 시점에 주기억장치로 읽어들이는 것

장점: 주기억장치의 효율적인 사용이 가능(비용 절감)

단점: CPU가 필요한 페이지를 사용할려고 할 때 페이지가 주기억장치에 없기 때문에 이 페이지를 주기억장치로 읽어들이는데 시간이 소요 (성능이 저하)

 

예상 페이징(Anticipatory Paging, Prepaging)

미리 예측하여 프로세스가 필요로 할 페이지를 주기억장치에 로드하는 방식의 가상 메모리 관리 기법

장점: CPU가 필요한 페이지를 사용하고자 할 경우 입출력 등의 부담이 없이 바로 사용이 가능 (성능 우수)

단점: 예상이 빗나가게 되면 페이지를 미리 읽어들이는 데 따른 부담이 발생(비용 증가)