SLENDER ANKLES's 개발블로그

프로세스(Process) 

"메모리에 로드되어 실행중인 프로그램"

Register set = 프로세스 실행을 위해 필요한 데이터들로 채워진다.

실행해야 할 프로세스 여러개라면 멀티 프로세스는 모든 프로세스를 일단 실행시킨 후 운영체제의 스케줄러에 의해 프로세스들을 관리한다.

일반적으로 프로그램은 많은 시간을 I/O(입출력)에 할당한다. 

프로그램이 I/O 를 하고 있을때 CPU는 일을 하지 않고 가만히 있는다.

(이때 스케줄러가 다른 프로세스로 교체를 하여 CPU를 쉬지 않게 하는것이 멀티 프로세스 기반이다)

다음은 이러한 CPU 자원을 사용하는 프로세스의 상태변화 메커니즘이다.

1. S(Start) : 프로세스 생성 -> Ready

프로세스는 생성과 동시에 Ready 상태로 들어간다.

Ready 상태에 있는 프로세스는 CPU(정확히 말하면 운영체제의 스케줄러)에 의해 실행되기를 기다린다.

2. Ready -> Running

Ready 상태에 있는 프로세스들은 스케줄러에 의해 관리된다.

스케줄러는 Ready 상태에 있는 프로세스중 하나를 선택해서 CPU에 의해 실행될 수 있도록 한다. (스케줄링 알고리즘 기반)

스케줄러에 의해 선택된 프로세스는 Running 상태가 되어 실행된다.

3. Running -> Ready

일의 중요도에 따라 프로세스들은 생성시 우선순위(Priority)가 매겨진다.

우선순위가 더 높은 프로세스가 Ready 상태에 있다면 스케줄러는 실행중인 프로세스를 Ready상태로 내리고 실행시킨다. Ready 상태로 간 프로세스는 우선순위가 더 높은 프로세스가 종료되기만을 기다린다.

4. Runnimg -> Blocked

실행 중에 있는 프로세스가 실행을 맘추는 상태(Blocked)로 들어간다.

I/O 에 관련된 일을 하는 경우(CPU에 의해 더이상 실행될 수 없다) 스케줄러는 Blocked 상태로 프로세스를 내리고 Ready 상태인 프로세스 중 하나를 실행시킨다.

5. Blocked -> Ready

Blocked 상태는 스케줄러에 의해서 선택될 수 없다.

따라서 Blocked 에 있는 프로세스는 다시 실행될 수 있는 Ready 상태로 간다.

예) :  I/O 가 완료된 프로세스

6. Blocked -> E(Exit)

프로세스를 종료시킬 경우 Blocked 상태를 거쳐 E(Exit)상태로 간다.

컨텍스트 스위칭(Context Switching)

CPU 내에 존재하는 레지스터들은 현재 실행 중에 있는 프로세스 관련 데이터들로 채워진다.

스케줄러에 의해 실행중인 프로세스가 변경되면 CPU 내의 존재하는 레지스터들도 컨텍스트 

스위칭에 의해 데이터를 변경한다.

(참고 : 실행되는 프로세스의 변경과정에서 발생하는 컨텍스트 스위칭은 레지스터 갯수가 많을수록 프로세스별로 관리되어야 할 데이터 종류가 많을수록 시스템에 많은 부담을 준다)

참조 : http://dakuo.tistory.com/80

공유자원을 활용한 로직의 문제는 어떤 것들이 있나?

다음과 같은 문제가 있다.

스레드1이 A에 분명 10을 할당했는데, 후에 바로 스레드2가 20을 할당해버리므로

예상치 못한 결과를 얻어낸다.

공유 자원에 대한 접근 문제 

= Critical Section(임계 구역)에 대한 접근 문제

공유자원을 사용하는 메커니즘에 LOCK이 있다.

이 메커니즘을 이해하기 위해서 뮤텍스와 세마포어에 대한 개념을 알아야한다.

뮤텍스와 세마포어의 차이는 무엇인가?

공유자원에 대한 접근권한, Lock이라는 키를 한 개만 가지고 있는 것은 뮤텍스(mutex)이다.

반면에, Lock이라는 키를 여러 개 가질 수 있는 것은 세마포어(Semaphore)이다.

뮤텍스란 무엇인가?

일종의 Locking 매커니즘이다. lock을 가지고 있을 때만 공유 데이터에 접근이 가능하다.

화장실에 갈 때 키를 가진 사람만이 갈 수 있다. 일을 다 본 후에는 키를 반납하고 그 다음 사람이 갈 수 있다. 이러한 메커니즘을 말한다. 

유의할 점은 lock에 대한 소유권이 있다는 점. 열쇠를 획득한 사람만 반납 할 수 있다.

세마포어란 무엇인가?

세마포어는 동시에 리소스에 접근 할 수 있는 “허용 가능한 counter의 개수”를 말한다.

예를 들면 병원에 있는 어느 한 병실에 5명까지 들어 갈 수 있다고 한다면, 5명까지 들어 갈 때 counting을 하고 5명 이후에는 밖에서 기다려야 한다. 한 사람이 나오게 되면 다음 사람이 들어 갈 수 있게 되는 것이다.

그 count수에 따라서 1개이면 binary semaphore, 여러 개이면 counting semaphore라고 한다.

binary semaphore는 뮤텍스와 개념적으로 같다.

모니터(monitor)란 무엇인가?

뮤텍스(mutex)와 Condition Valuable(Queue라고도 함)을 가지고 있는 Synchronization 메커니즘이다.

예를 들어 자바에서 모든 객체는 Object 클래스를 상속 받는다. 이 Object 클래스에는 wait(), notifyAll(), notify() 메소드를 가지고 있는데 이게 바로 Condition Variables 역할이라고 보면 된다. 고로 모든 자바 객체는 Monitor를 가지고 있다.

자바에서는 Mutual Exclusion 해결을 위한 구현체로 Synchronized 키워드가 있다. 예를 들어 Synchronized가 메소드에 선언되어있고, 쓰레드A가 이미 Lock을 획득해서 Critical Section(메소드)을 수행중이라고 가정하자. 쓰레드B가 동일한 메소드를 수행하기 위해 해당 Object의 Lock을 획득해야 할 것이다. 이 Lock이 반환될 때까지 대기를 해야하는데 그 때 사용되는게 바로 Monitor다. 쓰레드A가 Lock을 반환하면 쓰레드B는 기다렸다가 Lock을 획득하게 된다. 그리고 Critical Section인 메소드를 수행할 수 있게 된다. 물론 Synchronized 키워드를 사용했을 때 자동적으로 수행되는 내부 동작이고, 별도로 명시적인 Monitor를 구현할 수도 있다.(이건 길어질거 같으니 별도 포스팅으로….) 아무튼 Monitor는 이렇게 Mutex(Lock)과 Condition Variables을 이용해서 Mutual Exclustion을 해결하고 있다. 그 외 Monitor의 다른 정의로는 공유자원에 안전하게 접근하기 위해 Mutual Exclusion가 랩핑된 Thread-Safe한 클래스, 객체, 모듈들을 의미하기도 한다.

레이스 컨디션(race condition)이란 무엇인가?

경합조건이라고 하며, 유닉스 계열의 시스템에서 여러개의 프로세스가 동시에 실행될 때, 서로 CPU에 대한 우선권을 차지하기 위해 경쟁하게 되는데, 그것이 바로 레이스 컨디션이다. 이것은 규칙적인것이 아니라 불규칙하게 이루어진다. 이를 이용해 해킹에 사용되기도 한다.

스핀락이란 무엇인가?

스핀락은 위 CriticalSection의 한가지 단점을 극복하는데서 착안된 동기화 기법이다.

그것은 바로 쓰레드가 임계 영역을 획득하지 못하게 되면(Lock을 못잡게 되면) 쓰레드가 블로킹되는 것이다. 쓰레드 블로킹은 이후 쓰레드 컨텍스트 스위칭을 불러오게 되며 성능의 하락을 유발시킨다.

이 단점을 극복하기 위해 스핀락은 락을 점유하지 못할 때 쓰레드가 Back-off 되어 다른 쓰레드에게 넘기는 것이 아니라, Loop를 돌면서 해당 쓰레드를 Busy-Waiting 상태로 만들어 버린다.

그러면, 쓰레드 스위칭이 발생하지 않게 되어 컨텍스트 스위칭이 발생하지 않게 되는 것이다.

하지만!!!

임계 영역에서의 작업이 다소 시간이 오래 걸리는 일이라면?

결과는 오히려 CriticalSection을 사용할 때보다 훨씬 더 안 좋아지게 된다.

곧 끝날거라 기대하며 기다리느라 쓰레드가 헛돌고 있다보면 CPU 점유율이 올라가고, 오히려 다른 쓰레드가 컨텍스트 스위칭을 하더라도 일을 더 많이 할 수 있다면 낭비가 되는 것이다.

바쁜 대기(busy waiting)이란 무엇인가?

대기중인 스레드가 여전히 활성 상태긴 하지만 실제로는 아무 일도 하지 않는 것을 말한다.

생산자 소비자 문제란 무엇인가?(동시성을 처리하는 방법에 대한 문제)

철학자들의 저녁식사 문제란 무엇인가?(동시성을 처리하는 방법에 대한 문제)

컨텍스트 스위칭(Context Switching) 이란 무엇인가?

CPU는 동시에 한 개씩의 스레드만  실행시킬 수 있습니다. 

스레드가 여러개가 생성되면 CPU는 각각의 스레드를 시분할하여 각각의 스레드를 번갈아가며 

실행하게 되는데, 이때 이전 스레드의 문맥 정보 (레지스터 값, 실행중인 스택 정보 등)을 백업받고 

백업받아놓았던 다음 스레드의 문맥정보를 로딩하는 과정을 거치게 됩니다. 

이 과정을 Context Switching(문맥 교환이라고 번역하더군요) 이라고 하는데, 이러한 스레드가 

많아질 수록 Context Switching 에 많은 부하가 걸리기 때문에 오히려 퍼포먼스는 떨어지게 됩니다.

컨텍스트 스위칭이 자주 일어나면 근데 왜 부하가 발생한다는 건가?

메모리와 레지스터 사이의 데이터 이동도 I/O이다. 

즉, 컨텍스트 스위칭 과정에서 I/O가 발생한다. 빈번한 I/O 발생은 overhead를 발생시킨다. 

실행되는 process의 수가 많고, 빈번한 컨텍스트 스위칭이 발생한다면, 이는 성능을 떨어뜨린다. 

하지만 I/O가 발생할 때, 멍~하게 기다릴 수도 없는 노릇이다. 

I/O가 발생할 때, CPU를 게속 사용하려면 컨텍스트 스위칭은 피할 수 없다.

메모리 구조에서 그 차이가 있다.

멀티 프로세스가 멀티 스레드에 비해 속도가 느린 이유는 프로세스의

코드영역과 스택영역, 힙영역(데이터영역)을 모두 복사하기 때문이다.

그에 비해 멀티스레드는 스택영역이 스레드 개수만큼 분할되고 힙영역 등은 공유해서 사용하기 때문에

경량화된 프로세스라고 할 수 있는 것이다. 

데드락이란 무엇인가?

두 프로세스가 로직을 수행하기 위해 A, B라는 락을 획득해야 할 때 1번 프로세스가 락 A를 획득한 채 B를 기다리고, 2번 프로세스가 락 B를 획득한 채 A를 기다리고 있을 때 영원히 빠져 나올 수 없는 상태가 되는데 이를 데드락이라고 한다.

두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로 아무것도 완료 될 수 없는 상태를 말한다. 

데드락의 발생조건은 무엇인가?

4개의 조건이 모두 만족해야 데드락이 발생한다. 그러나 4개의 조건이 모두 만족하여도 데드락이 일어나지 않을 수도 있다.

1) Mutual Exclusion(상호배제)

한 시점에서는 한 프로세스만 사용 가능

2) Hold and Wait(점유와 대기)

추가적인 자원을 요구하며 대기

3) Non-Preemtion(비선점)

Operation 도중 선점 불가능 ex) 프린트 작업, 파일 쓰기

4) Circular Wait(환형대기)

서로 상대방을 기다리는 사이클이 발생한다. 

데드락이 발생했을 때는 어떻게 처리해야되나?

데드락의 회피조건은 무엇인가?( 데드락을 안걸리게 할려면 어떻게 해야되나?)

데드락의 발생 원인을 제거함으로써 데드락 상태를 예방한다.

1) 상호배제의 부정

크리티컬 섹션의 진입에는 상호배제가 필수적이므로 현실적으로 불가능하다.

2) 모든 자원을 실행 전에 확보한다. (필요한 락을 실행전에 모두 획득하거나 그렇지 못하면 모두 획득하지 않는다.)

당장 쓰지 않는 자원을 미리 점유해 놓으므로 리소스 낭비가 심하다.

3) 비선점의 부정(Denying non-preemption)

선점은 상태의 보존과 이의 복구가 필요

4) 환형대기를 피한다(Denying Circular-wait)

각 자원 형태에 증가하는 순서의 번호를 부여한다.

프로세스에서 자원을 증가하는 순으로만 자원을 요청하면 환형 대기 방지(즉, 사이클을 막을 수 있다)

P1과 P2의 경우 자원의 요청이 각 자원의 할당된 번호가 증가하는 순으로 요청이 이루어져

정상적으로 처리가 되지만, P3에서 자원의 할당된 번호가 역순으로 진행되어 deadlock의 위험을 감지 할 수 있다.

생산자 소비자 문제

철학자들의 저녁식사

"디스크에 대한 입출력은 굉장히 느리다."

왜 느린가?

Access Time = SeekTime + LatencyTime + Transmission Time

- Seek time

디스크 암(Disk Arm)의 헤드가 실린더가 포함하는 원하는 트랙으로 이동하는 시간을 의미한다. 

- Rotational latency (회전지연시간)

디스크 암의 헤드가 특정 트랙까지 이동한 후 디스크가 회전하여 트랙에 포함되어 있는 특정 섹터가 디스크암의 헤드까지 도달하는데 걸리는 시간

- Transmission Time(전송시간)

디스크 암의 헤드가 Access한 Sector와 주기억장치 간의 자료 전송에 걸리는 시간

* 트랙(Track) : 디스크 표면에서 회전축(스핀들 모터)을 중심으로 데이터가 기록되는 동심원

* 섹터(Sector) : 트랙들을 일정한 크기로 구분한 부분이며, 정보 기록의 기본 단위임

* 실린더(Cylinder) : 서로 다른 면들에 있는 동일 위치의 트랙들의 모임으로, 실린더의 수는 한 면의 트랙 수와 동일함

이러한 디스크에 대한 효율적인 시간 사용을 위하여 디스크 스케쥴링이 필요하다.

디스크 스케쥴링 기법

1) FCFS(First Come First Served)

들어오는 순서대로 이동하는 것이다. 

2) SSTF(Shortes Seek Time First)

현재의 헤드 포지션으로부터 최소한의 Seek-Time이 가능한 곳을 먼저 요청한다.

정리해보자면

 - 들어온 순서대로가 아닌 가까운 순서대로 접근한다.

 - 양 끝은 starvation에 고통 받을 수 있다. 

 - SSTF는 Minimum Avg SeekTime으로써 퍼포먼스는 좋다.

 - Small Disk Load System에는 좋다. 하지만, Heavy Disk Load System에는 좋지 않다.(startvation때문이다.)

3) SCAN(Elevator Algorithm)

디스크 암(Disk Arm)이 한 쪽 끝에서 시작해서 한 쪽 끝으로 움직인다. 

다른 쪽 끝에 도달하면 다시 거꾸로 끝까지 서비스를 계속한다. (왔다갔다 한다는 말이다)

이 것을 엘레베이터 알고리즘이라고도 부른다.

4) C-SCAN

SCAN방식과 유사하다.

한쪽 끝에서 시작해서 반대편 끝으로 이동하면서 SEEK한다. 

차이점은 반대편 끝에 도달해서는 다시 처음으로 돌아와서 시작한다.

디스크 스케쥴링 알고리즘의 퍼포먼스(성능)에 대해서 이야기 해보자.

누가 더 빠른가?(Avg Seek Time)

FCFS < C-SCAN < SCAN < SSTF

누가 더 공정한가?

FCFS > C-SCAN > SCAN > SSTF

SSTF에서 등장한 문제점인 STARVATION이란 무엇인가?

우선순위가 낮아 할당받지 못하는 상태를 무한 연기라고 하며,

무한 연기되어 결국에는 디스크 IO를 완료하지 못하는 것을 startvation이라고 합니다.

CPU 스케쥴링의 대상은 누구인가?

프로세스와 스레드

멀티 태스킹은 어떻게 가능한가?

CPU가 여러 프로세스들에게 시간을 분할(시분할, Time Slice)하여 

자원을 사용하게끔 동작하여 마치 동시에 실행되고 있는 것과 같이 동작 할 수 있다.

시간을 어떻게 분할하는지에 대한 연구가 CPU 스케쥴링이다.

선점형 스케쥴링? 비선점형 스케쥴링?

선점형 스케쥴링

- 한 프로세스가 CPU를 차지하고 있을 때 우선순위가 높은 다른 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 차지할 수 있는 경우

- 높은 우선순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유용 

장점 : 빠른 응답시간을 요구하는 시분할 시스템에 유용 

단점 : 높은 우선순위 프로세스들이 자주 들어오는 경우 오버헤드를 초래 

비선점형 스케쥴링

- 한 프로세스가 CPU를 할당받으면 다른 프로세스는 CPU를 점유못함(빼앗을 수 없음)

장점 : 모든 프로세스들에게 공정하고 응답시간의 예측이 가능 

단점 : 짧은 작업을 수행하는 프로세스가 긴 작업이 종료될 때까지 기다려야 함 

CPU 스케쥴링의 방법들

선점형 스케쥴링

하나의 프로세스가 CPU를 점유하고 있을 때 다른 프로세스가 CPU를 빼앗을 수 있는 방법. 

1) Round-Robin 기법

FCFS(First Come First Served)에 의해서 프로세스들이 할당됨

서로 다른 프로세스들은 같은 시간을 할당받음

할당된 시간이 지나면 작업이 완료되지 않더라도 중단되고, 다시 큐로 이동

장점 : 시분할 방식에 효과적이며, 골고루 서비스가 가능하고  대화식 시스템에 유리하다.

단점 : 타임 슬라이스 그러니까 시분할이 작으면 문맥교환에 많은 비용이 들어 퍼포먼스가 떨어지게 된다.

2) SRT(Shortest Remaining Time) 스케쥴링

가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행한다.

작업하는 중이라도 남은 큐 중에 더 짧게 소요 될 수 있다고 판단되는 프로세스가 준비되면

문맥교환 후 그 작업을 수행한다.

단점 : 긴 작업은 SJF(Shortes Job First)보다 오래 걸린다.

3) 다단계 큐(Multi Level Queue) 스케쥴링

- 작업들을 여러 종류의 그룹으로 나누어 여러개의 큐를 이용하는 기법

- 일반적으로 프로세스 우선순위에 따라 시스템 프로세스, 대화형 프로세스, 편집 프로세스, 일괄 처리 프로세스 등의 큐로 나누는 것

- 각 준비상태 큐는 독자적으로 스케쥴링을 할 수 있으므로 특성에 맞는 스케쥴링 기법을 각각 사용 할 수 있다. 

(예를 들어 foreground 작업은 라운드 로빈 스케줄링 방식의 큐에, 일괄처리 작업은 FCFS 스케줄링 방식의 큐에 둔다. 라운드 로빈 스케줄링 방식의 큐에 많은 CPU 시간을 할당할 수 있다.)

- 프로세스가 특정 준비 상태 큐로 이동하게 되면 다른 준비 상태 큐로 이동 할 수는 없다.

- 하위 단계에 있는 프로세스가 작업을 수행 중이더라도 상위 단계에 있는 큐에 작업이 들어오게 되면 컨텍스트 스위칭하여 CPU를 상위단계 큐의 프로세스에 할당해야 합니다.

4) 다단계 피드백 큐(Multi level Feedback Queue) 스케쥴링

다단계 큐 스케쥴링의 다른 큐 사이의 이동이 불가능한 점을 개선하여 만든 스케쥴링

- 각 준비 상태 큐마다 다른 시간 할당량을 부여하며 시간안에 완료되지 못한 작업들은 다음 단계의 큐로 넘어가게 됩니다. (즉, 실행 시간이 긴 작업에게 벌칙을 주는 방식이다. )

- 상위 단계일수록 우선순위가 높고 시간할당량이 작습니다.

- 요구하는 시간이 적은 프로세스, 입출력 중심의 프로세스, 낮은 우선순위에서 너무 오래 기다린 프로세스을 기준으로 높은 우선순위를 할당하게 됩니다.

- 하위 단계의 프로세스가 작업중이더라도 상위 단계의 큐에 작업이 들어오게 되면 중단하고 상위 단계 작업을 수행하게 된다.

- 가장 최하위 단계의 큐에서는 라운드 로빈(RR) 스케쥴링 기법을 사용합니다.

- 맨 아래에서 너무 오래 머물면 aging 방식 사용

장점 : 적응(adaptive) 메커니즘 (각 큐의 CPU 할당 시간 정할 수 있다)

          가장 널리 사용되고, 일반적인 방법

단점 : 최상의 스케줄러를 정의하기 위한 요소를 찾기 어렵다.

비선점형 스케쥴링

프로세스에게 이미 할당된 CPU를 강제로 빼앗을 수 없고, 사용이 끝날 때까지 또는 

CPU를 할당 받은 프로세스가 스스로 넘길 때까지 기다려야 하는 방법. 

1) FCFS(First Come First Served) 스케줄링 = FIFO(First In First Out) 

대기 큐에 먼저 들어온 작업에게 CPU를 먼저 할당. 가장 간단한 스케쥴링 방법

2) SJF(Shortest Job First) 스케줄링

작업 시간이 가장 적은 프로세스에게 CPU를 먼저 할당하는 기법. 

- 장점 : 가장 짧은 평균 대기 시간을 제공

- 단점 : 실행시간이 긴 프로세스는 실행시간이 짧은 프로세스에게 밀려 무한 연기 상태가 발생         할 수 있다. 

3) HRN(Highest Response ratio Next) 스케줄링

실행시간이 긴 프로세스에게 불리한 점을 보완하여 실행시간+대기시간을 고려한 스케쥴링 기법

- 우선 순위 계산 공식을 활용하여 실행시간이 짧거나, 대기시간이 긴 프로세스에게 먼저 CPU자원을 할당(긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법)

- 짧은 작업이나 대기시간이 긴 작업은 우선순위가 높아진다

                  (대기시간 + 서비스를 받을 시간)

☞ 우선순위 = ------------------------------

                       서비스를 받은 시간

4) 기한부(DeadLine) 스케쥴링

프로세스에게 일정한 시간을 주어 그 시간안에 완료되도록 하는 메커니즘이다.

만약 그 시간안에 완료되지 못하면 다시 처음부터 작업을 시작해야 한다. 

5) 우선순위(Priority) 스케쥴링

준비 상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당해주어야 한다.

우선순위가 동일할 경우 FCFS 스케쥴링 기법을 활용한다.

우선순위는 프로세스의 종류나 특성에 따라 다르게 부여 될 수 있다.

가장 낮은 순위를 부여받은 프로세스는 무한 연기 또는 기아 상태(starvation)가 될 수 있다.

스케쥴링의 목표

# 모든 시스템

* 공정성 (Fairness) : 모든 프로세스들에게 공정히 CPU 시간 할당

* 효율성 (Balance) : CPU의 사용률 극대화

 - CPU이용률과 처리량을 최대화하고 총 처리 시간, 대기 시간, 응답 시간을 최소화 하는게 바람직한 스케줄링의 기준이 된다.

# Batch 시스템

- 높은 처리량 (High Throughput) : 시간당 처리되는 작업의 수 높임

- 짧은 반환시간 (Short turnaround time) : 작업이 시스템에 도착해서 완료 되는데 까지의 시간 최소화

# 대화식 시스템

- 짧은 응답시간 (Short Response Time) : 대화식 작업에 빠르게 CPU 할당

# 실시간 시스템

- 데드라인 만족 : 주어진 시간 안에 프로세스가 실행될 수 있게 함

# 상호 모순성

- 스케쥴링의 목표는 상호모순 일 수 있음

- 예를 들어 짧은 응답 시간과, 데드라인 만족은 서로 공존할 수  없음.

- 따라서 어떤 스케쥴링 목표를 세울지는 시스템의 특성에 따라 결정

페이지 교체 알고리즘

앞써 설명한 바와 같이 

가상 메모리 시스템에서는 MMU를 통해 가상 주소를 실제 주소로 바꾸어주어 동작하게 한다. 

이로 인해 프로그램의 전체 크기만큼 메모리가 필요하지 않고, 실제 동작하는데 필요한 최소한의 메모리만으로도 프로그램을 동작시키게 해주는 것이다. 이 때 MMU가 관리하는 메모리를 페이지단위로 관리한다고 했다. 

메모리를 효율적으로 사용하기 위해서는 페이지가 계속 사용된다면 메모리에 놔두어야 하고, 그렇지 않으면 메모리에서 내리는 동작을 취해야 한다.

이러한 것을 페이지 교체 알고리즘을 통해서 처리한다. 

페이지 교체 알고리즘에 대해서 알아보면

1) FIFO 페이지 교체(First In First Out Page Replacement)

2) 최적 페이지 교체(Optimal Page Replacement, OPT)

3) LRU 페이지 교체(Least-Recently-Used Page Algorithm)

4) LRU 근사 페이지 교체(Least-Recently-Used approximation page algorithm)

5) 계수-기반 페이지 교체(Counting-Based Page Algorithm)

6) 페이지 버퍼링 알고리즘(Page-Buffering Algorithm)

각각의 알고리즘에 대해서 설명해보겠다.

1) FIFO 페이지 교체(First In First Out Page Replacement)

개념 : 

페이지 교체 시, 메모리에 올라온지 가장 오래된 페이지를 내쫓는다.

장점 : 

가장 간단한 페이지 교체 알고리즘이다.

단점 :

* 가장 오래된 페이지가 초기화 모듈이라면 성능이 저하될 수 있음

* Belady의 모순(Belady's Abnomaly)

: 프로세스에게 프레임을 더 주었는데 오히려 페이지 부재율이 더 증가하는 현상

2) 최적 페이지 교체(Optimal Page Replacement, OPT)

개념 : 

"앞으로 가장 오래 동안 사용되지 않을 페이지를 찾아 교체하라"

장점 : 

* 모든 알고리즘보다 낮은 페이지 부재율

* Belady의 모순 발생하지 않음

단점 :

* 구현 어려움(프로세스가 앞으로 메모리를 어떻게 참조할 것인지 미리 알아내기 힘들기 때문)

3) LRU 페이지 교체(Least-Recently-Used Page Algorithm)

개념 : 

페이지 교체 시에 가장 오래 사용되지 않은 페이지를 교체

최적 페이지 교체 알고리즘에 근사한 알고리즘으로 각 페이지마다 마지막 사용시간을 유지

(미래시간 대신 과거시간에 대해 적용한 최적 교체 알고리즘이라 판단할 수 있음)

4) LRU 근사 페이지 교체(Least-Recently-Used approximation page algorithm)

개념 :

하드웨어가 지원하지 못할 경우 참조 비트(Reference bit)를 이용하여 사용된 페이지와 사용되지 않은 페이지를 구분 할 수 있음

5) 계수-기반 페이지 교체(Counting-Based Page Algorithm)

- 참조 횟수를 가지고 교체될 페이지를 선정

(1) LFU 알고리즘(Least Frequently Used Algorithm)

개념 : 참조횟수가 가장 적은 페이지를 교체

(2) MFU 알고리즘(Most Frequently Used Algorithm)

개념 : 참조 횟수가 가장 많은 페이지를 교체

가장 작은 참조 횟수를 가진 페이지가 가장 최근에 참조됐기 때문에 가장 적게 참조됐고, 앞으로 사용될 것이라는 판단에 근거한 알고리즘이다.

- 대개 LFU, MFU 알고리즘은 잘 쓰지 않는다.

그 이유는 구현시 비용이 많이 들고, 최적(OPT)페이지 교체 정책에 제대로 근사하지 않기 때문

6) 페이지 버퍼링 알고리즘(Page-Buffering Algorithm)

여러 개의 자유 프레임을 풀(Pool)에 넣어 가지고 있다가 페이지 교체가 필요할 때 자유 프레임에 새로운 페이지를 읽어 들이고, 희생될 프레임을 찾은 뒤 프레임을 디스크에 기록하고 자유 프레임 풀(Pool)에 추가한다.

가상 메모리 시스템(Virtual Memmory System)과 페이지 폴트(Page Fault)

가상메모리(Virtual Memory)란?

가상 메모리는 메모리를 관리하는 방법의 하나로, 

각 프로그램에 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식을 말한다.

이러한 방식은 멀티태스킹 운영 체제에 흔히 사용되며,  실제 주기억장치(RAM)보다 큰 메모리 영역을 제공하는 방법으로 사용된다. 

가상 메모리 개념의 배경

"RAM은 결코 충분하지 않다"

가상 메모리의 개념을 사용하지 않는 시스템에서 어플리케이션 수행 시 10000바이트의 용량을 차지하

는 프로그램이 있다고 가정해보면, 시스템의 메모리는 최소 10000바이트 이상이 되어야 할 것이다. 

만일, 1바이트라도 모자란 9999바이트 용량의 RAM으로는 "메모리부족" 오류가 날 것이다.

즉, 한 시스템에서 돌아가는 가장 큰 실행 어플리케이션 용량보다 메모리가 더 커야한다는 것이다.

여기에 두 개이상의 프로그램이 멀티태스킹 된다면 상황은 더 안 좋아질 것이다.

가상 메모리는 프로그램이 차지 하는 주소공간(Address Space)의 개념에 대해 조금 다르게 접근한다.

가상 메모리를 사용하는 운영체제는 

"프로그램을 실행하는데 얼마나 많은 메모리가 필요한가?"에 집중하지 않고,

"프로그램을 실행하는데 필요한 최소한의 메모리는 얼마인가?"

에 대해 고민하기 시작한다.

메모리 접근은 순차적이고 지역화되어 있다는 특성 때문에, 어플리케이션을 실행하는데 완전한 

10000바이트가 필요한 것처럼 보이지만, 사실 이 어플리케이션을 실행하는데 필요한 메모리 용량은 

10000바이트보다 훨씬 적게된다. 

즉, 위에서 말한 10000바이트의 프로그램이 실행하는데 필요한 최소한의 처리 순서를 다음과 같이 가정해보자.

1) 메모리에서 명령어를 읽어온다.

2) 명령어가 필요로하는 데이터도 메모리에서 읽어온다.

3) 명령이 완료된 후, 결과가 메모리에 기록된다.

예를 들어, 이 각각의 명령처리에 100바이트 씩의 메모리가 할당되어야 한다면, 고작 300바이트만으로 프로그램을 실행 시킬 수 있다는 것이다. 즉, 프로그램 실행과 상관있는 300바이트만 메모리에 올리면 된다는 뜻이다.

그렇다면 프로그램의 나머지 기능을 수행할 코드나 데이터부분의 처리를 위한 메모리 할당은 어떻게 해야 되나?

바로, 보조기억장치(하드디스크 등)이다.

현재 필요하거나 향후 필요한 어플리케이션의 일부분을 필요한만큼 계속 RAM에 올려놓도록 가상 메모리 하부 시스템을 구축하여 동작 할 수 있다면, 하드디스크를 RAM의 보조기억장치로 쓰는데 아무 문제가 없는 것이다.

이러한 방식은 빠르고 작은 기억장치를 크고 느린 기억장치와 병합하여 하나의 크고 빠른 기억장치처럼 작동하게 한다는 면에서 캐시(Cache)와 RAM의 관계와도 유사하다고 할 수 있다. 

* 가상 주소 공간(Virtual Address Space)

가상 주소 공간이란 어플리케이션이 사용 가능한 최대 주소 공간을 말한다.

(가상 메모리 시스템에서 사용하는 주소공간이란 의미가 있다)

CPU아키텍처에 따라 주소지정을 위해 필요한 비트수가 달라지기 때문에 가상 주소 공간은 아키텍처에 따라 달라지게 된다. CPU 아키텍처는 레지스터(Register)의 크기와 관련이 있다.

예를 들어, 32비트 CPU 2^32 = 4294967296 로 0 ~ 4294967296까지의 주소공간을 나타낼 수 있다.

여기에 메모리의 가장 작은 단위는 Byte이기 때문에 4GByte가 되는 것이다.

때문에 각 어플리케이션들은 4GB의 주소 공간을 가질 수 있고, 32비트 시스템의 운영체제에서 RAM이 4GB까지 인식 못하는 이유도 여기에 있다.

또한, 운영체제에 따라서도 달라지게 된다. 

32비트 윈도우에서는 기본적으로 응용프로그램에 4GB의 가상 주소 공간이 주어진다.

이중에서 2GB(0x00000000 ~ 0x7FFFFFFFF)는 

사용자모드공간(USER MODE SPACE, 응용프로그램마다 독립적으로 사용가능한 공간)이고,

나머지 2GB(0x80000000 ~ 0xFFFFFFFFF)는 

운영체제에서 사용하는 커널가상주소공간(KERNEL MODE SPACE)이다.

반면, 리눅스에서는 각 응용 프로그램이 4GB의 가상 주소 공간을 갖는 것은 같지만, 

3GB의 사용자공간과 1GB의 커널공간을 갖게 된다. 커널 공간은 모든 프로세스들이 공유하게 된다.

프로그래머들이 프로그램을 만들 때 사용하는 주소들은 가상 주소 공간의 가상 주소들이고 

실제 물리적인 메모리의 주소는 아니다. 이 것을 가능하게 해주는 녀석이 MMU 다.

**참고**

다음은 프로세스 및 커널의 가상 공간 구성에 대한 그림이다.

- Text Area

CPU가 실행하는 명령어로 구성되는 영역으로 읽기 전용으로만 접근이 허용되므로 프로세스의 실행 중 변화가 없다. 메모리 퇴출 시에도 디스크 파일에 존재한다. 

- Data Area

초기화된 데이터 영역과 초기화되지 않은 데이터 영역으로 구분되며 메모리 적재 후 변화된 부분은 메모리 퇴출 시에 swap공간으로 가게 된다. 

- Heap Area

프로세스 실행 중에 malloc, new 등의 동적 메모리 할당 요구를 수용하는 데이터 영역 공간이다. break. 값에 의해 그 끝을 나타내며 공간 부족 시에 주소가 커지는 방향으로 확장된다. 

- Stack Area

함수 내에서 할당되는 automatic 변수들이나 함수 호출 시에 run-time stack frame(함수가 호출 될 때의 반환주소, 환경정보 등) 등으로 할당되는 공간이다. 주소가 작아지는 방향으로 확장된다. 

가상 주소(Virtual Address)와 

MMU(Memory Management Unit, 메모리 관리 장치)

가상 주소(Virtual Address)는 논리 주소(logical Address)라고도 하며, 

실제 메모리 상에서 유효한 주소는 물리 주소(Physical Address)또는 실주소(Real Address)라고 한다.

가장 주소 공간의 가상 주소는 MMU에 의해서 실제 물리 주소로 변환된다. 

이 덕분에 프로그래머는 가상 주소 공간상에서 프로그램을 짜게 되어 프로그램이나 데이터가 주메모리 상에 어떻게 존재하는지를 의식 할 필요가 없다.

메모리 관리 하드웨어인 MMU가 없다면, CPU가 RAM에 접근 할 때 메모리 주소 123은 물리 메모리의 123 주소에 접근하게 될 것이다.

하지만 MMU를 사용하게 되면 메모리 주소 123은 물리 메모리 23892에 접근 할 수도 있고, 다음에는 12934에 접근할 수도 있다는 것이다.

그러나 수억만 바이트에 이르는 메모리를 하나씩 가상 주소에서 물리적 주소로 변역하게 되면 작업부하가 너무 높아지므로, MMU는 RAM을 여러 부분, 즉 일정한 크기를 가진 블록인 페이지(PAGE)로 나누어 각 페이지를 하나의 독립된 항목으로 처리하게 된다.

앞에서 설명한 대로, 10000바이트 가상 주소 공간을 가진 가상 어플리케이션의 첫 번째 명령어가 주소 12374에 저장된 데이터에 접근한다고 가정해보자.

그러나 컴퓨터는 오직 12000바이트의 물리적인 RAM만 존재하는 경우 CPU가 주소 12374에 접근을 시도한다면 어떠한 결과가 발생할까?

이러한 현상을 페이지 폴트(Page Fault)라고 부르는 것이다.

페이지 폴트(Page Fault)

페이지 폴트란 프로그램이 자신의 주소 공간(가상메모리공간)에는 존재하지만 

시스템의 RAM에는 현재 없는 데이터나 코드에 접근 시도하였을 경우 발생하는 현상을 말한다.

페이지 폴트가 발생하면 운영체제는 그 데이터를 메모리로 가져와서 마치 페이지 폴트가 전혀 발생하지 않은 것처럼 프로그램이 계속적으로 동작하게 해준다.

앞에서 설명한 바와 같이 CPU는 우선 원하는 주소(12374)를 MMU에게 보내게 된다. 

그러나 MMU는 주소 변환 과정에서 페이지 테이블(Page Table)에 이 주소에 대한 항목이 없다고 표시할 것이다.

그 다음 MMU는 CPU를 인터럽트 한 후, 페이지 폴트 처리기라는 소프트웨어가 실행되도록 한다. 

이 페이지 폴트 처리기가 원하는 페이지를 디스크 상 어디에 위치하는지 찾은 후 읽어오게 하는 작업을 한다. 

작업 세트(Working set)

현재 특수 프로세스 전용으로 할당된 물리적 메모리 페이지 그룹을 그 프로세스의 작업세트라고 한다.

메모리 완전 부족 현상을 방지하기 위해서는 프로세스의 작업 세트에서 페이지를 삭제하여 나중에 사용 가능한 여유 공간으로 변경시켜야 하는데, 운영 체제는 다음과 같은 방법을 사용하여 프로세스의 작업 세트를 줄여준다.

-수정된 페이지를 대용량 기억장치의 전용 공간(보통 스와핑(Swapping) 또는 페이징(Paging)공간이라고 부름)에 기록하기

-수정되지 않은 페이지는 여유 페이지로 표시함(이 페이지는 변경되지 않았으므로 디스크로 가져와 기록할 필요가 없다.)

또한, 운영체제는 모든 프로세스에 적절한 작업 세트를 할당하기 위하여 모든 페이지에 대한 사용 정보를 기록해야 하는데, 이렇게 함으로써

- 운영 체제는 어느 페이지가 자주 사용되었으며(이러한 페이지는 메모리에 계속 두어야 한다.)

- 어느 페이지가 사용되지 않았는지(따라서 메모리에서 삭제 할 수 있다) 결정할 수 있게 된다.

대부분의 경우 프로세스 작업 세트에서 최근 가장 자주 사용되지 않은 페이지를 찾아서 삭제하게 되어 있다.

 # 참고로 페이지 하나의 크기는 x86, x64와 amd64에서는 4KB, ia64에서는 8KB의 크기를 가진다.

 # 페이지의 동적 주소 변환

 페이징 기법이 적용된 시스템에서 가상주소는 순서쌍(p,d)로 나타낼 수 있고, p는 가상 메모리 내에서 참조될 항목에 속해 있는 페이지 번호(page number)이고,

 d는 페이지 p 내에서 참조될 항목이 위치하고 있는 곳의 거리(distance)이다. 

 과정은 다음과 같다.

  1) 수행 중인 프로세스가 가상주소 V(p,d)를 참조한다.

  2) 페이징 기법을 통해 페이지 p가 페이지 프레임 p'에 있음을 알아낸다.

  3) 실주소 r = p' + d를 구한다.

 # 스와핑(Swapping)

 스와핑은 수정된 페이지를 하드 디스크와 같은 보조기억 장치 내부의 시스템 스왑 페이지에 기록하는 작업을 한다. 

 과정은 다음과 같다.

 1) 프로세스에서 페이지가 스와핑 됨

 2) 프로세스가 실행 가능 상태가 되어 스왑된 페이지에 접근 시도함

 3) 페이지 폴트로 메모리로 다시 기록됨(이 때, 대부분의 경우 다른 프로세스 페이지가 스와핑되어 나가게 됨)

 4) 얼마 지나지 않아 이 페이지가 다시 스와핑 됨

이러한 상황이 너무 자주 발생하면 더 많은 CPU 및 입/출력 작업을 무리하게 요구 당하게 되며, 프로그램의 처리 속도가 급격히 떨어지게 된다.

극단적인 경우엔 시스템은 아무런 작업도 실행하지 못 한채, 페이지를 메모리에서 가져오고 빼내는 작업에만 모든 자원을 소모하게 되는 경우도 발생할 수 있다.

이와 같은 경우를 쓰레싱(Thrashing)이라고 하며, 현재 작업을 실행하는데 RAM이 부족하다는 것을 나타낸다.

참조 : http://combiz119.tistory.com/entry/%EA%B0%80%EC%83%81= %EB%A9%94%EB%AA%A8%EB%A6%ACVirtual-Memory%EB%9E%80