개발자 기술면접 #1 - 운영체제

프로세스에 대해 설명하시오.

 

프로세스는 실행 중인 프로그램으로 디스크로부터 메모리에 적재되어 CPU 의 할당을 받을 수 있는 것을 말한다. 운영체제로부터 주소 공간, 파일, 메모리 등을 할당받으며 이것들을 총칭하여 프로세스라고 한다. 구체적으로 살펴보면 프로세스는 함수의 매개변수, 복귀 주소와 로컬 변수와 같은 임시 자료를 갖는 프로세스 스택과 전역 변수들을 수록하는 데이터 섹션을 포함한다. 또한 프로세스는 프로세스 실행 중에 동적으로 할당되는 메모리인 힙을 포함한다.

 

스레드에 대해 설명하시오.

 

스레드는 프로세스의 실행 단위라고 할 수 있다. 한 프로세스 내에서 동작되는 여러 실행 흐름으로 프로세스 내의 주소 공간이나 자원을 공유할 수 있다. 스레드는 스레드 ID, 프로그램 카운터, 레지스터 집합, 그리고 스택으로 구성된다. 같은 프로세스에 속한 다른 스레드와 코드, 데이터 섹션, 그리고 열린 파일이나 신호와 같은 운영체제 자원들을 공유한다. 하나의 프로세스를 다수의 실행 단위로 구분하여 자원을 공유하고 자원의 생성과 관리의 중복성을 최소화하여 수행 능력을 향상시키는 것을 멀티스레딩이라고 한다. 이 경우 각각의 스레드는 독립적인 작업을 수행해야 하기 때문에 각자의 스택과 PC 레지스터 값을 갖고 있다.

 

스택을 스레드마다 독립적으로 할당하는 이유는?

 

스택은 함수 호출 시 전달되는 인자, 되돌아갈 주소값 및 함수 내에서 선언하는 변수 등을 저장하기 위해 사용되는 메모리 공간이므로 스택 메모리 공간이 독립적이라는 것은 독립적인 함수 호출이 가능하다는 것이고 이는 독립적인 실행 흐름이 추가되는 것이다. 따라서 스레드의 정의에 따라 독립적인 실행 흐름을 추가하기 위한 최소 조건으로 독립된 스택을 할당한다.

 

PC Register를 스레드마다 독립적으로 할당하는 이유는?

 

PC 값은 스레드가 명령어의 어디까지 수행하였는지를 나타나게 된다. 스레드는 CPU 를 할당받았다가 스케줄러에 의해 다시 선점당한다. 그렇기 때문에 명령어가 연속적으로 수행되지 못하고 어느 부분까지 수행했는지 기억할 필요가 있다. 따라서 PC 레지스터를 독립적으로 할당한다.

 

프로세스 제어 블록에 대해 설명하시오,

 

PCB 는 특정 프로세스에 대한 중요한 정보를 저장 하고 있는 운영체제의 자료구조이다. 운영체제는 프로세스를 관리하기 위해 프로세스의 생성과 동시에 고유한 PCB 를 생성 한다. 프로세스는 CPU 를 할당받아 작업을 처리하다가도 프로세스 전환이 발생하면 진행하던 작업을 저장하고 CPU 를 반환해야 하는데, 이때 작업의 진행 상황을 모두 PCB 에 저장하게 된다. 그리고 다시 CPU 를 할당받게 되면 PCB 에 저장되어있던 내용을 불러와 이전에 종료됐던 시점부터 다시 작업을 수행한다.

 

PCB 에 저장되는 정보

 

프로세스 식별자(Process ID, PID) : 프로세스 식별번호

프로세스 상태 : new, ready, running, waiting, terminated 등의 상태를 저장

프로그램 카운터 : 프로세스가 다음에 실행할 명령어의 주소

CPU 레지스터

CPU 스케쥴링 정보 : 프로세스의 우선순위, 스케줄 큐에 대한 포인터 등

메모리 관리 정보 : 페이지 테이블 또는 세그먼트 테이블 등과 같은 정보를 포함

입출력 상태 정보 : 프로세스에 할당된 입출력 장치들과 열린 파일 목록

어카운팅 정보 : 사용된 CPU 시간, 시간제한, 계정번호 등

 

사용자 수준 스레드와 커널 수준 스레드의 차이를 설명하시오.

 

커널 레벨 스레드

- 커널 스레드는 가장 가벼운 커널 스케쥴링 단위다. 

- 하나의 프로세스는 적어도 하나의 커널 스레드를 가지게 된다. 

- 커널 영역에서 스레드 연산을 수행하게 된다.

- 커널이 스레드를 관리하기 때문에 커널에 종속적이다.

- 프로그래머 요청에 따라 스레드를 생성하고 스케줄링하는 주체가 커널이면 커널 레벨(Kernel Level) 스레드라고 한다.

 

커널 레벨 스레드 장점

- 프로세스의 스레드들을 몇몇 프로세서에 한꺼번에 디스패치 할 수 있기 때문에 멀티프로세서 환경에서 매우 빠르게 동작한다.

- 다른 스레드가 입출력 작업이 다 끝날 때까지 다른 스레드를 사용해 다른 작업을 진행할 수 있다. 

- 커널이 각 스레드를 개별적으로 관리할 수 있다. 

- 커널이 직접 스레드를 제공해 주기 때문에 안정성과 다양한 기능이 제공된다.

 

커널 레벨 스레드 단점

- 스케줄링과 동기화를 위해 커널을 호출하는데 무겁고 오래걸린다.(저장한 내용을 다시 불러오는 과정이 필요)

- 즉, 사용자 모드에서 커널 모드로의 전환이 빈번하게 이뤄져 성능 저하가 발생한다.

- 사용자가 프로그래밍할 때 구현하기 어렵고 자원을 더 많이 소비하는 경향이 있다.

 

사용자 레벨 스레드

- 사용자 영역에서 스레드 연산을 수행한다. 

- 사용자 영역에서 스레드 연산을 수행하기 때문에 운영체제에 투명하다. 

- 커널에 의존적이지 않은 형태로 스레드의 기능을 제공하는 라이브러리를 활용하는 방식이 사용자 레벨(User Level) 스레드다.

 

사용자 레벨 스레드 장점

- 운영체제에서 스레드를 지원할 필요가 없다. 

- 스케줄링 결정이나 동기화를 위해 커널을 호출하지 않기 때문에 인터럽트가 발생할 때 커널 레벨 스레드보다 오버헤드가 적다.

- 즉, 위의 말은 사용자 영역 스레드에서 행동을 하기에 OS Scheduler의 context switch가 없다(유저레벨 스레드 스케줄러를 이용).

- 커널은 사용자 레벨 스레드의 존재조차 모르기 때문에 모드 간의 전환이 없고 성능 이득이 발생한다

 

사용자 레벨 스레드 단점

- 시스템 전반에 걸친 스케줄링 우선순위를 지원하지 않는다. (무슨 스레드가 먼저 동작할 지 모른다.)

- 프로세스에 속한 스레드 중 I/O 작업등에 의해 하나라도 블록이 걸린다면 전체 스레드가 블록된다.

 

문맥교환(context switching)에 대해 설명하시오.

 

멀티프로세스 환경에서 CPU가 어떤 하나의 프로세스를 실행하고 있는 상태에서 인터럽트 요청에 의해 다음 우선 순위의 프로세스가 실행되어야 할 때 기존의 프로세스의 상태 또는 레지스터 값(Context)을 저장하고 CPU가 다음 프로세스를 수행하도록 새로운 프로세스의 상태 또는 레지스터 값(Context)를 교체하는 작업을 Context Switch(Context Switching)라고 한다.

질문에 대한 답변은 이정도로 하고 좀 더 명확하게 이해해본다.

* Context Switching을 문맥 교환으로 번역하지 말자.

Context는 무엇인가?

사용자와 다른 사용자, 사용자와 시스템 또는 디바이스간의 상호작용에 영향을 미치는 사람, 장소, 개체등의 현재 상황(상태)을 규정하는 정보들을 말한다.

android나 servlet등에서도 context가 있지만 OS에서 Context는 CPU가 해당 프로세스를 실행하기 위한 해당 프로세스의 정보들이다.

이 Context는 프로세스의 PCB(Process Control Block)에 저장된다.

그래서 Context Switching 때 PCB의 정보를 읽어(적재) CPU가 전에 프로세스가 일을 하던거에 이어서 수행이 가능한 것이다.

PCB의 저장정보

- 프로세스 상태 : 생성, 준비, 수행, 대기, 중지

- 프로그램 카운터 : 프로세스가 다음에 실행할 명령어 주소

- 레지스터 : 누산기, 스택, 색인 레지스터

- 프로세스 번호

* 참고로 Context Switching 때 해당 CPU는 아무런 일을 하지 못한다. 따라서 컨텍스트 스위칭이 잦아지면 오히려 오버헤드가 발생해 효율(성능)이 떨어진다.

Context가 뭔지 알았고 멀티프로세싱하기 위해 CPU를 나눠서 사용하기 위해 Context를 교체하는 것이 Context Switching임을 알았다. 그리고 PCB에 Context가 저장됨도 알았다.

남은 것은 인터럽트 요청이 뭐고 어떤 종류가 있는지 + 서브로 우선 순위에 대한 이야기다.

Context Switching - 인터럽트(Interrupt)

인터럽트는 CPU가 프로그램을 실행하고 있을 때 실행중인 프로그램 밖에서 예외 상황이 발생하여 처리가 필요한 경우 CPU에게 알려 예외 상황을 처리할 수 있도록 하는 것을 말한다.

어떤 인터럽트 요청이 와야 Context Switching이 일어날까?

1. I/O request (입출력 요청할 때)

2. time slice expired (CPU 사용시간이 만료 되었을 때)

3. fork a child (자식 프로세스를 만들 때)

4. wait for an interrupt (인터럽트 처리를 기다릴 때)

+ 더 있겠지만 자세한 것은 생략.

* 우선 순위는 해당 OS의 스케줄러가 우선 순위 알고리즘에 의해 정해지고 수행하게 되어있다.

라운드로빈 스케줄링(Round Robin Scheduling)은 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나다.

쉽게 설명하면 순서대로 시간단위(Time Quantum)을 CPU에 할당하는 방식이다.

꽤 효율적인 스케줄링 알고리즘이지만 이 시간단위를 작게 설정하면 CPU가 조금 일하고 Context Switching을 반복하므로 아까 말했듯이 효율이 떨어진다.

* Context Switch를 하는 주체 = OS 스케줄러

 

멀티 스레딩의 장단점을 설명하시오.

 

장점

프로세스를 이용하여 동시에 처리하던 일을 스레드로 구현할 경우 메모리 공간과 시스템 자원 소모가 줄어들게 된다. 스레드 간의 통신이 필요한 경우에도 별도의 자원을 이용하는 것이 아니라 전역 변수의 공간 또는 동적으로 할당된 공간인 Heap 영역을 이용하여 데이터를 주고받을 수 있다. 그렇기 때문에 프로세스 간 통신 방법에 비해 스레드 간의 통신 방법이 훨씬 간단하다. 심지어 스레드의 context switch 는 프로세스 context switch 와는 달리 캐시 메모리를 비울 필요가 없기 때문에 더 빠르다. 따라서 시스템의 throughtput 이 향상되고 자원 소모가 줄어들며 자연스럽게 프로그램의 응답 시간이 단축된다. 이러한 장점 때문에 여러 프로세스로 할 수 있는 작업들을 하나의 프로세스에서 스레드로 나눠 수행하는 것이다.

 

단점

멀티 프로세스 기반으로 프로그래밍할 때는 프로세스 간 공유하는 자원이 없기 때문에 동일한 자원에 동시에 접근하는 일이 없었지만 멀티 스레딩을 기반으로 프로그래밍할 때는 이 부분을 신경써줘야 한다. 서로 다른 스레드가 데이터와 힙 영역을 공유하기 때문에 어떤 스레드가 다른 스레드에서 사용중인 변수나 자료구조에 접근하여 엉뚱한 값을 읽어오거나 수정할 수 있다.

그렇기 때문에 멀티스레딩 환경에서는 동기화 작업이 필요하다. 동기화를 통해 작업 처리 순서를 컨트롤 하고 공유 자원에 대한 접근을 컨트롤 하는 것이다. 하지만 이로 인해 병목현상이 발생하여 성능이 저하될 가능성이 높다. 그러므로 과도한 락으로 인한 병목현상을 줄여야 한다.

 

멀티 프로세스와 멀티 스레드의 차이를 설명하시오.

 

멀티 스레드는 멀티 프로세스보다 적은 메모리 공간을 차지하고 문맥 전환이 빠르다는 장점이 있지만, 오류로 인해 하나의 스레드가 종료되면 전체 스레드가 종료될 수 있다는 점과 동기화 문제를 안고 있다. 반면 멀티 프로세스 방식은 하나의 프로세스가 죽더라도 다른 프로세스에는 영향을 끼치지 않고 정상적으로 수행된다는 장점이 있지만, 멀티 스레드보다 많은 메모리 공간과 CPU 시간을 차지한다는 단점이 존재한다. 이 두 가지는 동시에 여러 작업을 수행한다는 점에서 같지만 적용해야 하는 시스템에 따라 적합/부적합이 구분된다. 따라서 대상 시스템의 특징에 따라 적합한 동작 방식을 선택하고 적용해야 한다.

 

상호배제(mutual exclusion)란?

 

상호배제는 병행 프로세스에서 프로세스 하나가 공유 자원을 사용할 때 다른 프로세스들이 동일한 일을 할 수 없도록 하는 방법이다. 즉, 공유 자원에 있는 데이터에 접근하는 다른 프로세스를 이미 사용중인 프로세스 하나가 해당 데이터에 접근할 수 없게 하는 것을 상호배제(Mutual exclustion,Mutex)라고 한다. 물론 읽기 연산은 공유 데이터에 동시에 접근해도 문제가 발생하지 않지만, 변수나 파일은 프로세스 별로 하나씩 차례로 읽거나 쓰도록 해야한다. 예를 들면 하나의 프로세스가 순차적으로 파일을 읽는 작업을 하는 도중에 다른 프로세스가 파일의 내용을 변경해버리면 읽어오는 값이 예상과 다를 수 있기에 이러한 상황을 제어하는 동기화 작업이 필요한 것이다.

 

동기화(synchronization)란?

 

시스템의 자원은 한정적인데 이 한정적인 자원에 여러 스레드가 동시에 접근해서 사용하려하면 문제가 발생할 수도 있습니다. 이런 문제를 방지하기 위해 스레드들에게 하나의 자원에 대한 처리 권한을 주거나 순서를 조정해주는 기법입니다.

임계영역(critical section)이란?

 

임계구역은 다중 프로그래밍 운영체제에서 여러개의 프로세스가 공유하는 데이터 및 자원에 대하여 어느 한 시점에서는 하나의 프로세스만 자원 또는 데이터를 사용하도록 지정된 공유 자원을 의미합니다.

 

임계영역이 만족해야 하는 세 가지 조건을 설명하시오.

 

1) 상호배제 : 어떤 프로세스가 임계 영역에서 작업 중이면 다른 프로세스는 임계 영역으로 들어 갈 수 없다.

 

2) 진행 : 임계 영역에 프로세스가 없는 상태에서 여러 프로세스가 들어가려고 할 때는 어떤 프로세스가 들어갈지 적절히 결정해야 한다.

 

3) 한정 대기 : 다른 프로세스가 임계 영역을 무한정 기다리는 상황을 방지하려면 임계 영역에 한 번 들어갔던 프로세스는 다음에 임계 영역에 다시 들어갈 때 제한을 둔다.

 

세마포어와 뮤텍스란 무엇인지 설명하시오.

 

여러 쓰레드들은 자원을 공유하고, 프로세스간 메시지를 전송하면서 간혹 문제가 발생할 수 있습니다.

즉, 공유된 자원에 여러 프로세스 , 쓰레드가 동시에 접근하면서 문제가 발생합니다. 

공유된 자원 속 하나의 데이터는 한번에 하나의 프로세스만 접근할 수 있도록 제한해 두어야 할 필요성이 있는데

이를 위해 고안된 것이 Semaphore(세마포어)입니다.

 

유명한 화장실 예제로 쉽게 설명해보겠습니다.

공중 화장실은 한번에 1명만 사용할 수 있다고 가정하겠습니다.

어떤 사람이 사용하고 있는데 다른 누군가가 갑자기 들어와서 같이 쓰자고 하면... 생각만해도 이상하지요..?

이를 막기 위해 화장실 열쇠를 만들 수 있습니다.

열쇠를 가지고 있는 한 사람만 화장실을 이용하고, 열쇠가 없는 사람은 밖에서 대기를 하죠.

여기서 열쇠는 세마포어와 같은 역할을 한다고 할 수 있습니다.

 

그럼 세마포터와 뮤텍스 각각 어떤 의미를 가지고 있을까요?

 

Semaphore(세마포어)

 

공유된 자원의 데이터를 여러 프로세스가 접근하는 것을 막는 것!

그리고 세마포어는 리소스의 상태를 나타내는 간단한 카운터라고 할 수 있습니다.

일반적으로 비교적 긴 시간을 확보하는 리소스에 대해 이용하게 되며, 유닉스 시스템의 프로그래밍에서 세마포어는 운영체제의 리소스를 경쟁적으로 사용하는

다중 프로세스에서 행동을 조정하거나 또는 동기화 시키는 기술입니다.

위 화장실 예제로 다시 살펴보면, 세마포어는 1개 이상의 열쇠라고 할 수 있습니다.

만약 화장실 칸이 4개이고 열쇠가 4개라면, 4명까지는 대기없이 바로 사용할 수 있고 

그 다음 부터는 대기를 해야하죠. 이것이 바로 세마포어입니다.

그러므로 몇개의 세마포어로 구성해서 운영체제의 리소스를 경쟁적으로 사용할지는 꽤 중요한 이슈입니다.

그림으로 표현하면 아래와 같습니다.

 

 

Mutex(뮤텍스, 상호배제)

공유된 자원의 데이터를 여러 쓰레드가 접근하는 것을 막는 것!

즉, *Critical Section을 가진 쓰레드들의 Running tme이 서로 겹치지 않게 각각 단독으로 실행되게 하는 기술입니다. 

다중 프로세스들이 공유 리소스에 대한 접근을 조율하기 위해 locking과 unlocking을 사용합니다.

간단히 말해, Mutex객체를 두 쓰레드가 동시에 사용할 수 없다는 말입니다.

위 화장실 예제로 다시 살펴보면, 뮤텍스는 무조건 1개의 열쇠만 가질 수 있습니다!

그림으로 표현하면 아래와 같습니다.

세마포어와 뮤텍스의 차이?

 

세마포어는 뮤텍스가 될수 있지만, 뮤텍스는 세마포어가 될 수 없습니다.

뮤텍스는 항상 열쇠 1개이고, 세마포어는 여러개 가질 수 있기 때문에 

세마포어의 열쇠가 1개라면 뮤텍스와 같습니다.

 

세마포어는 파일시스템 상 파일형태로 존재, 뮤텍스는 프로세스 범위입니다.

즉, 프로세스가 사라질 때 뮤텍스는 clean up 됩니다.

세마포어는 소유할 수 없는 반면, 뮤텍스는 소유할 수 있습니다.

 

뮤텍스의 경우, 뮤텍스를 소유하고 있는 쓰레드가 이 뮤텍스를 해제할 수 있습니다.

반면, 세마포어의 경우, 세마포어를 소유하고 있지 않은 쓰레드도 이 세마포어를 해제할 수 있습니다.

 

모니터란 무엇인지 설명하시오.

 

동기화 문제를 해결하기 위해서 우리는 세마포라는 도구를 사용하였다. 하지만 동기화 문제를 해결하는데 세마포만이 사용되지는 않는다. 사실 세마포의 경우 오래된 동기화 도구라고 할 수 있다. 현재 사용되는 도구 중 하나가 모니터이다. 특히 자바 프로그램에서는 모니터에 대한 활용이 높다. 세마포가 어셈블리 언어에 적합한 도구라면 모니터는 그보다 고수준인 언어의 도구라고 할 수 있다.

 

공유자원과 공유자원에 대한 접근함수가 존재한다. 이러한 구역을 임계구역이라고 한다. 모니터의 경우 두 개의 queue가 있는데 각각 배타동기와 조건동기의 역할을 한다. 배타동기의 queue는 하나의 쓰레드만 공유자원에 접근할 수 있게 하는 작용을 하는 공간이다. 특정 쓰레드가 공유자원을 사용하는 함수를 사용하고 있으면 다른 쓰레드는 접근을 할 수 없고 대기해야 한다. 조건 동기의 queue는 진입 쓰레드가 블록되면서 새 쓰레드가 진입가능하게 하는 공간이다. 새 쓰레드는 조건동기로 블록된 쓰레드를 깨울 수 있다. 깨워진 쓰레드는 현재 쓰레드가 나가면 재진입할 수 있다.

 

교착 상태(deadlock)이란 무엇인지 설명하시오.

 

교착상태(Dead Lock)은 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미합니다.

 

교착 상태의 발생 조건을 설명하시오.

 

교착상태가 발생하기 위해서는 다음의 네가지 조건이 충족되어야 하는데, 이 네가지 조건중 하나라도 충족되지 않으면 교착상태가 발생하지 않습니다.

 

상호배제(Mutual Exclusion)

한번에 한개의 프로세스만이 공유 자원을 사용할 수 있어야 합니다. 

 

점유와 대기(Hold and Wait) 

최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 이해 대기하는 프로세스가 있어야 합니다.

 

비선점(Non-preemption)

다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야합니다.

 

환형 대기(Circular Wiat) 

공유자원과 공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 합니다.

 

다음 스케줄링 알고리즘을 설명하시오

 

1) FCFS (First In First Out)

 

먼저 온 고객을 먼저 서비스해주는 방식, 즉 먼저 온 순서대로 처리.

비선점형(Non-Preemptive) 스케줄링
일단 CPU 를 잡으면 CPU burst 가 완료될 때까지 CPU 를 반환하지 않는다. 할당되었던 CPU 가 반환될 때만 스케줄링이 이루어진다.

 

문제점

convoy effect
소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다.

 

2) SJF (Shortest Job First)

 

다른 프로세스가 먼저 도착했어도 CPU burst time 이 짧은 프로세스에게 선 할당

비선점형(Non-Preemptive) 스케줄링

 

문제점

starvation
효율성을 추구하는게 가장 중요하지만 특정 프로세스가 지나치게 차별받으면 안되는 것이다. 이 스케줄링은 극단적으로 CPU 사용이 짧은 job 을 선호한다. 그래서 사용 시간이 긴 프로세스는 거의 영원히 CPU 를 할당받을 수 없다.

 

3) SRT (Shortest Remaining time First)

 

새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.

선점형 (Preemptive) 스케줄링
현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다.

 

문제점

starvation

새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용시간)을 측정할 수가 없다.

 

4) Priority Scheduling

 

우선순위가 가장 높은 프로세스에게 CPU 를 할당하겠다. 우선순위란 정수로 표현하게 되고 작은 숫자가 우선순위가 높다.

선점형 스케줄링(Preemptive) 방식
더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점한다.

비선점형 스케줄링(Non-Preemptive) 방식
더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 Head 에 넣는다.

 

문제점

starvation

무기한 봉쇄(Indefinite blocking)
실행 준비는 되어있으나 CPU 를 사용못하는 프로세스를 CPU 가 무기한 대기하는 상태

 

해결책

aging

아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주자.

 

5) Round Robin

 

현대적인 CPU 스케줄링

각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다.

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

RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적

RR이 가능한 이유는 프로세스의 context 를 save 할 수 있기 때문이다.

 

장점

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

프로세스가 기다리는 시간이 CPU 를 사용할 만큼 증가한다.
공정한 스케줄링이라고 할 수 있다.

 

주의할 점

설정한 time quantum이 너무 커지면 FCFS와 같아진다. 또 너무 작아지면 스케줄링 알고리즘의 목적에는 이상적이지만 잦은 context switch 로 overhead 가 발생한다. 그렇기 때문에 적당한 time quantum을 설정하는 것이 중요하다.

 

단기 스케줄링, 중기 스케줄링, 장기 스케줄링의 차이를 설명하시오.

 

장기 스케줄링(Long-term scheduler) : 메모리와 디스크 사이의 스케줄링을 담당.

실행할 작업을 준비 큐(입력 큐)에서 꺼내 메인 메모리에 적재함. 디스크에서 메모리로 적재될 프로그램을 선정한다. 쉽게 말하면 메모리 문지기 역할이다. (작업 스케줄러 라고도 불린다)
단순히 문을 열고 닫는 문지기 역할에서 그치는게 아니라 메인 메모리에 있는 프로세스의 양을 판단하고 결정하는 역할도 한다. 
만약 메인 메모리에 적재된 프로세스들이 너무 많아 실행이 빈번하게 발생되고 메인 메모리에 프로세스들이 넘쳐나면 더 이상 프로세스들을 메인 메모리에 적재 시키지 않는다. - 멀티프로그래밍의 정도를 결정

 

프로세스의 상태
new -> ready(in memory)

 

중기 스케줄링(Mid-term scheduler) : 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러. cpu를 할당받고 프로그램이 실행중 일 때 멀티 프로그래밍 정도에 따라 프로그램들을 관리해 주는 역할을 한다. (= swapper)

여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄. (swapping)
프로세스들이 CPU를 서로 차지하려고 할 때 프로세스를 기억장소(메인 메모리)에서 잠시 빼내고 다시 메인 메모리에 들여보내 실행시킬 수 있는 교체(Swapping)기법을 사용한다.

 

프로세스의 상태
ready -> suspended

단기 스케줄링(Short-term scheduler) : CPU 와 메모리 사이의 스케줄링을 담당. 메인 메모리의 준비 상태에 있는 작업 중 실행할 작업을 선택하여 CPU를 할당. (프로세서 스케줄러 라고도 불린다)
하지만 CPU는 프로그램을 실행 시키기 전에 먼저 실행 시키기 위한 데이터 확보가 필요하다.
CPU에게 그 필요한 데이터를 확보 시켜주고 CPU를 할당하는 역할을 이 단기 스케줄링이 한다.
그리고 준비 큐에 있는 프로그램들(프로세스)중 먼저 도착한 프로세스에게 CPU를 할당 시켜준다. = 디스패쳐

프로세스의 상태
ready -> running -> waiting -> ready

 

장기 스케줄링과 중기 스케줄링, 단기 스케줄링의 차이?
먼저 장기 스케줄링과 단기 스케줄링의 차이는 실행 빈도이다.
단기 스케줄링은 실행할 프로세스를 수시로 선택해야 해서 실행시간이 100만 분의 수초 정도이다.
반대로 장기 스케줄링은 시스템에 새로운 작업이 들어오는 것은 분 단위이므로 단기 스케줄링에 비해 상대적으로 덜 수행하는 것이다.
그 때문인지 작업이 시스템에 들어오는 정도가 일정하다면 작업의 도착 정도와 작업의 끝냄 정도가 비슷하다. 
장기 스케줄러의 실행은 작업이 시스템을 나갈 때만 실행되기 때문에 실행 간격이 상대적으로 길다 그래서 실행시간이 좀 길어도 영향을 적게 받는다.
중기 스케줄링은 장기 스케줄러의 비중이 적거나 아예 없는 시스템에서 중기 스케줄러를 추가하여 사용하는데 가상 메모리체제나 시분할 기법을 사용하는 시스템이 그 (예)이다. 중기 스케줄러는 프로세스들이 CPU를 서로 차지하려고 할 때, 프로세스를 기억장소(메인 메모리)에서 빼고 다시 넣을 수 있어서 다중 프로그래밍의 정도를 줄일 수 있다.

 

선점 스케줄링과 비선점 스케줄링의 차이점을 설명하시오. 엄격한 비선점식 스케줄링을 사용하지 않는 이유도 설명하시오.

 

선점스케줄링은 높은 우선순위의 프로세스가 들어올 경우 현재 프로세스를 중지시키고, 높은 우선순위의 프로세스를 처리.

비선점 스케줄링은 한번 할당하면 끝날때가지 다른 프로세스가 들어오지 못하는 스케줄링.

엄격한 비선점식 스케줄링을 사용하지 않는 이유는 짧은 프로세서가 오랫동안 대기하게 될 경우 비효율적이고, 기아상태가 발생할 수 있다.

 

논리적 주소와 물리적 주소 차이를 설명하시오.

 

논리적 주소

주소 프로그램이 실행되는 동안 CPU에 의해 생성 된 것을 논리적 주소 라고합니다. 논리 주소는 물리적으로 존재하지 않으므로 가상 주소입니다. 따라서 가상 주소 라고도합니다. 이 주소는 실제 메모리 위치를 액세스하기위한 참조로 사용됩니다. 프로그램 관점에서 생성 된 모든 논리 주소 집합을 논리 주소 공간 이라고합니다.

논리 주소는 메모리 관리 장치라는 하드웨어 장치에 의해 해당 물리적 ​​주소에 매핑됩니다. MMU에서 사용되는 주소 바인딩 방법은 컴파일 타임 및 로드 시간 동안 동일한 논리 및 실제 주소를 생성 합니다 . 그러나 실행 시간 동안 주소 바인딩 방법은 다른 논리 및 실제 주소를 생성합니다.

 

물리적 주소

물리적 주소 는 메모리의 물리적 위치를 식별합니다. MMU ( Memory-Management Unit) 는 해당 논리 주소의 실제 주소를 계산합니다. MMU는 논리 주소 계산 물리 주소를 사용합니다. 사용자는 실제 주소를 결코 취급하지 않습니다. 대신, 물리적 주소는 사용자에 의해 해당 논리 주소에 의해 액세스됩니다. 사용자 프로그램은 논리 주소를 생성하고 프로그램이이 논리 주소에서 실행되고 있다고 생각합니다. 그러나이 프로그램은 실행을위한 물리적 메모리가 필요합니다. 따라서 논리 주소는 사용되기 전에 실제 주소에 매핑되어야합니다.

논리 주소는 메모리 관리 장치 라는 하드웨어를 사용하여 실제 주소에 매핑됩니다. 논리적 주소 공간에서 논리적 주소에 해당하는 모든 물리적 주소 세트를 물리적 주소 공간 이라고합니다.

 

논리 주소와 실제 주소의 주요 차이점

 

1. 논리 주소와 실제 주소의 기본적인 차이점은 프로그램의 관점에서 CPU가 논리 주소를 생성한다는 것입니다. 한편, 물리 어드레스는 메모리 유닛에 존재하는 위치이다.

 

2. 프로그램에 대해 CPU에 의해 생성 된 모든 논리 주소 집합을 논리 주소 공간이라고합니다. 그러나 해당 논리 주소에 매핑 된 모든 물리 주소 집합을 실제 주소 공간이라고합니다.

 

3. 논리 주소는 메모리 장치에 물리적으로 존재하지 않으므로 논리 주소는 가상 주소라고도합니다. 물리적 주소는 물리적으로 액세스 할 수있는 메모리 장치의 위치입니다.

 

4. 동일한 논리 주소 및 실제 주소는 컴파일 타임 및로드 시간 주소 바인딩 방법에 의해 생성됩니다.

 

5. 런타임 주소 바인딩 방법이 서로 다른 동안 생성 된 논리 및 실제 주소입니다.

 

6. 논리 주소는 프로그램이 실행되는 동안 CPU에 의해 생성되는 반면 물리적 주소는 MMU (Memory Management Unit)에 의해 계산됩니다.

 

다음 메모리 할당 알고리즘을 설명하시오.

 

1) 최초 적합

가용공간 중 수용가능한 첫번째 기억공간을 할당하는 방법

사용 가능한 공간을 검색하여 첫 번째로 찾아낸 곳을 할당하는 방식

맨앞(또는 지난번 탐색이 끝난 곳)에서부터 수용가능한 첫번째 공간을 선택

장점: 가용공간 정렬 불필요

단점: 큰 공간을 쪼개어 사용하게 될 수 있음

 

2) 최적 적합

모든 공간 중에서 수용가능한 가장 작은 곳을 선택

사용가능한 공간들 중에서 가장 작은 것을 선택하는 방식

가용공간을 정렬하여 필요한 크기 이상의 공간 중 가장 작은 것을 할당하는 방법

장점: 큰 공간을 쪼개어 쓰는 일이 적음

단점: 정렬 필요. 작은 틈새 공간이 많이 발생

 

3) 최악 적합

모든 공간 중에서 수용가능한 가장 큰 곳을 선택

사용 가능한 공간들 중에서 가장 큰 것을 선택하는 방식

가용공간을 정렬하여 수용가능한 공간 중 가장 큰 곳을 할당하는 방법

장점: 남은 공간이 큼직큼직함. 1순위에 할당하므로 선택이 빠름

단점: 기억공간 정렬 필요, 공간 낭비 발생

 

공간효율성: 최적적합 > 최초적합 ≫ 최악적합

시간효율성: 최초적합 > 최적적합 ≒ 최악적합

최악적합은 잘 사용되지 않음

 

내부 단편화와 외부 단편화의 차이를 설명하시오.

 

단편화 (Fragmentation) : 프로세스들이 메모리에 적재되고 제거되는 일이 반복되다보면, 프로세스들이 차지하는 메모리 틈 사이에 사용 하지 못할 만큼의 작은 자유공간들이 늘어나게 되는데, 이것이 단편화 이다.

 

외부단편화 : 프로그램을 할당하고 난 다음 아주 작은 크기로 남은 조각들이 생겨 사용할 수 없는 작은 공간들이 많이 생길 수 있습니다. 이 공간들을 합치면 요구되는 공간을 할달할 수 있음에도 불구하고 연속적인 공간이 아니라서 할당하지 못하는 상황을 외부 단편화라고 합니다.

 

내부 단편화: 프로세스가 사용하는 메모리 공간 에 포함된 남는 부분. 예를들어 메모리 분할 자유 공간이 10,000B 있고 Process A 가 9,998B 사용하게되면 2B 라는 차이 가 존재하고, 이 현상을 내부 단편화라 칭한다.

 

압축 : 외부 단편화를 해소하기 위해 프로세스가 사용하는 공간들을 한쪽으로 몰아, 자유공간을 확보하는 방법론 이지만, 작업효율이 좋지 않다.

 

페이징과 세그먼테이션에 대해 설명하시오.

 

Paging(페이징)

 

물리메모리를 사용할 때, 페이지를 고정크기의 프레임단위로 나눕니다.

논리메모리도 같은 프레임단위인 페이지로 나누어 프레임과 페이지를 대응하게 하여

연속적인 물리메모리가 아니더라도 원하는 크기의 프레임을 사용할 수 있도록 하는 기능입니다. 

 

프레임(Frame) : 물리 메모리를 일정한 크기로 나눈 블록

페이지(Page) : 가상 메모리를 일정한 크기로 나눈 블록

 

물리메모리(프레임)와 가상메모리(페이지)를 대응하기 위해 page mapping 과정이 필요합니다. 

이를 위해 Paging table을 설정해야 합니다.

페이징 기법을 사용하면 연속적이지 않은 공간도 활용할 수 있기 때문에 외부단편화(External fragmentation)을 해결할 수 있고, 코드를 쉽게 공유할 수 있다는 장점이 있습니다. 

그리고 페이지 단위를 작게하면 내부 단편화(Internal fragmentation) 역시 해결할 수 있지만

(페이지에 공간을 할당한 후, 남는 공간이 적어지기 때문에) 그 만큼, page mapping 과정이 증가하므로 서로  trade off 관계에 있습니다.

 

Segmentation(세그멘테이션)

 

페이징 기법에서는 가상메모리를 같은 크기의 단위로 분할했으나 

세크멘테이션 기법에서는 가상메모리를 서로 크기가 다른 논리적 단위인 세그먼트(Segment)로 분할하고 

메모리를 할당하며 주소 변환을 하게 됩니다. 

(각각의 세그먼트들은 연속적인 공간에 저장되어있습니다)

 

세그먼트들의 크기가 서로 다르기 때문에 메모리를 페이징 기법처럼 미리 분할해 둘 수 없고,

메모리에 적재될 때 빈 공간을 찾아 할당하는 사용자 관점의 가상메모리 관리 기법입니다.

 

페이징기법과 마찬가지로 mapping을 위해 세그먼트 테이블을 필요로 합니다.

이 기법은 하나의 세그먼트 단위로 통제가 가능한 장점이 있습니다.

즉 내부단편화가 발생하지 않습니다.

그러나 서로 다른 크기의 세그먼트들에 대해 필요시에 메모리에 올리고 필요없을 경우

내리는 작업을 반복하다보면 외부 단편화가 생기는 문제점이 있습니다.

 

페이징 시스템에서 페이지 테이블이 어떤 기능을 하는지 설명하시오.

 

특정 프로세스의 페이지 테이블은 메모리의 특정 페이지 번호에 대응하는 물리적 메모리에 있는 페이지의 번호를 포함한다. 논리 주소를 물리 주소로 변환하는 메모리 관리 장치로 사용된다.

 

가상 메모리와 요구 페이징(Demand Paging)이란 무엇인지 설명하시오.

 

지금까지의 메모리 관리 기법 방식은 

프로세스 전체가 실행되기 전에 메모리로 올라와야 한다는 것을 전제로 하고 있다. 

프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법을 가상메모리라 한다.

가상 메모리는 물리 메모리로부터 사용자 관점의 논리 메모리를 분리시켜 주 메모리를 균일한 크기의 저장 공간으로 구성된 엄청나게 큰 배열로 추상화 시켜 준다. 

따라서 작은 메모리를 가지고도 큰 가상 주소 공간을 제공한다.

 

장 점 

 - 사용자 프로그램이 물리 메모리보다 커져도 된다는 점이다. 
   즉, 메모리 크기의 제약으로부터 자유로워진다.

 - 각 사용자 프로그램이 더 작은 메모리를 차지하므로 더 많은 프로그램을 동시에 수행할 수 있다. 
   이에 따라 응답시간은 늘어나지 않으면서 CPU 이용률과 처리율이 높아진다.

 - 프로그램을 메모리에 올리고 스왑(swap)하는데 필요한 입/출력 횟수가 줄어든다.
   따라서 프로그램들이 보다 빨리 실행된다.

 - 가상메모리 파일의 공유를 쉽게 해주고 공유 메모리 구현을 가능하게 한다.

 - 프로세스 생성을 효율적으로 처리할 수 있는 메커니즘도 제공한다.

 

단 점

 - 구현이 어렵고, 잘못 사용 시 성능이 현저히 저하 될 수 있다.

 

 요구 페이징 (Demand Paging)

 - 실행 프로그램을 디스크에서 메모리로 적재할 때 프로그램 전부를 물리메모리에 적재한다고 하면,
   프로그램 전체를 메모리에 둘 필요가 있을까?? 
   가상 메모리 시스템에서 많이 사용하는 요구 페이징 기법을 알아보자 
   요구 페이징이란 초기에 필요한 것들만 적재하고, 페이지들이 실행 과정에서 실제로 필요할 때 적재하는 기법이다. 
   즉, 한번도 접근되지 않는 페이지는 물리 메모리에 전혀 적재되지 않는다.

 

장 점

- 실제 필요한 페이지들만 메모리로 읽어오므로 사용되지 않는 페이지를 메모리로 가져오지 않음으로써
  시간 낭비와 메모리 공간 낭비를 줄일 수 있다.

- 프로세스가 메모리에 존재하는 페이지들만 접근하는 한 실행은 정상적으로 진행된다. 

  하지만 프로세스가 메모리에 올라와 있지 않는 페이지를 접근하려고 하면 어떤 일이 발생할까?
   -> 페이지 테이블 항목이 무효로 설정되어 있으므로 페이지 부재 트랩(page-fault trap)을 발생시킨다.

 

페이지 부재를 처리하는 과정

1. 프로세스에 대한 내부 테이블을 검사해서 그 메모리 참조가 유효(valid)/무효(invalid) 인지를 알아낸다.

2. 만약 무효한 페이지에 대한 참조라면 그 프로세스는 중단된다.
    만약 유효한 참조인데 페이지가 아직 메모리에 올라오지 않았다면, 그것을 디스크로부터 가져와야 한다.

3. 빈 공간 즉, 자유 프레임을 찾는다. (예를 들면, 페이지 프레임 리스트에서 하나 가져옴)

4. 디스크에 새로이 할당된 프레임으로 해당 페이지를 읽어 들이도록 요청한다.

5. 디스크 읽기가 끝나면, 이 페이지가 이제는 메모리에 있다는 것을 알리기 위해 페이지 테이블을 갱신하며,
   프로세스가 유지하고 있는 내부 테이블을 수정한다.

6. 트랩에 의해 중단되었던 명령을 다시 수행한다.
    이제 프로세스는 마치 그 페이지가 항상  메모리에 있었던 것처럼 해당 페이지를 접근할 수 있다.

 

페이지 부재(Page Fault)란 무엇인지 설명하시오.

 

페이지 부재란 프로세스(프로그램)가 메인 메모리(RAM)에 저장되지 않은 페이지를 사용하려는 현상입니다. 즉, 프로세스가 사용하려고 하는 페이지가 메인 메모리에 없는 경우를 맙합니다. 

 

페이지 교체란 무엇인지 설명하시오.

 

페이지 교체는 페이지 부재가 발생하면 메인 메모리에 있으면서 사용하지 않는 페이지를 디스크로 내보내고 새로운 페이지로 바꾸는 과정이다. 내보낼 페이지를 고를 때는 시스템의 효율성에 영향을 주므로 페이지 부재 비율이 가장 낮은 알고리즘을 선택한다.

 

다음 페이지 교체 알고리즘을 설명하시오.

 

1) FIFO (First In First Out)

 

가장 간단한 페이지 교체 알고리즘으로 FIFO(first-in first-out)의 흐름을 가진다. 즉, 먼저 물리 메모리에 들어온 페이지 순서대로 페이지 교체 시점에 먼저 나가게 된다는 것이다.

 

장점

- 이해하기도 쉽고, 프로그램하기도 쉽다.

 

단점

- 오래된 페이지가 항상 불필요하지 않은 정보를 포함하지 않을 수 있다(초기 변수 등)

- 처음부터 활발하게 사용되는 페이지를 교체해서 페이지 부재율을 높이는 부작용을 초래할 수 있다.

- Belady의 모순: 페이지를 저장할 수 있는 페이지 프레임의 갯수를 늘려도 되려 페이지 부재가 더 많이 발생하는 모순이 존재한다.

2) OPT (Optimal)

 

Belady의 모순을 확인한 이후 최적 교체 알고리즘에 대한 탐구가 진행되었고, 모든 알고리즘보다 낮은 페이지 부재율을 보이며 Belady의 모순이 발생하지 않는다. 이 알고리즘의 핵심은 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 것이다. 주로 비교 연구 목적을 위해 사용한다.

 

장점

- 알고리즘 중 가장 낮은 페이지 부재율을 보장한다.

 

단점

- 구현의 어려움이 있다. 모든 프로세스의 메모리 참조의 계획을 미리 파악할 방법이 없기 때문이다.

 

3) LRU (Least Recently Used)

 

최적 알고리즘의 근사 알고리즘으로, 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체한다.

 

특징

-대체적으로 FIFO 알고리즘보다 우수하고, OPT알고리즘보다는 그렇지 못한 모습을 보인다.

4) LFU (Least Frequently Used) 

 

참조 횟수가 가장 적은 페이지를 교체하는 방법이다. 활발하게 사용되는 페이지는 참조 횟수가 많아질 거라는 가정에서 만들어진 알고리즘이다.

 

특징

- 어떤 프로세스가 특정 페이지를 집중적으로 사용하다, 다른 기능을 사용하게되면 더 이상 사용하지 않아도 계속 메모리에 머물게 되어 초기 가정에 어긋나는 시점이 발생할 수 있다

- 최적(OPT) 페이지 교체를 제대로 근사하지 못하기 때문에, 잘 쓰이지 않는다.

5) MFU (Most Frequently Used)

 

MFU: Most Frequently Used
참조 회수가 가장 작은 페이지가 최근에 메모리에 올라왔고, 앞으로 계속 사용될 것이라는 가정에 기반한다.

 

특징

- 최적(OPT) 페이지 교체를 제대로 근사하지 못하기 때문에, 잘 쓰이지 않는다.

 

스래싱이란 무엇인지 설명하시오.

 

1. 스래싱이란?

페이지 부재율이 높은 것을 의미 

스레싱은 심각한 성능 저하를 초래 

충분한 프레임을 할당 받지 못한 프로세스에 대해 생각해보자

 

활발하게 사용되는 페이지 집합을 지원해 줄 만큼 프레임이 충분히 할당 받지 못한 프로세스는  
페이지 부재가 발생하게 된다.

 

이때 페이지 교체가 필요하지만 이미 활발하게 사용되는  페이지들만으로 이루어져 있으므로

어떤 페이지가 교체되든지 바로 다시 페이지 교체가 필요 하게 될 것이다.

 

결과적으로 바로 바로 반복해서 페이지 부재가 발생하며 교체된 페이지는 다시 얼마 지나지 않아

읽어올 필요가 생긴다.

이러한 과도한 페이징 작업을 쓰레싱 이라 한다.

 

 

2. 쓰레싱의 원인

- 다중 프로그래밍 정도가 높아짐에 따라 CPU 이용률이 높아진다. 

CPU이용률이 최대값에 도달하였을때, 다중 프로그래밍의 정도가 그 이상으로 더 커지면

쓰레싱이 일어나게 되고 CPU 이용률은 급격히 떨어진다.

- 운영체제는 CPU 이용률을 감시하면서, CPU 이용률이 너무 낮아지면 새로운 프로세스를 시스템에 더 추가해서 

다중 프로그래밍의 정도를 높인다.  이 때 전역 페이지 교체 알고리즘을 사용하여 어떤 프로세스의 페이지인지에 대한 고려 없이 교체를 수행한다.

 

이제 어떤 프로세스가 새로운 실행 단계로 진입하여 더 많은 프레임을 필요로 한다고 가정하자.

페이지 부재가 발생하면서 다른 프로세스로부터 프레임들을 가져오게 될 것이다.

그런데 교체된 페이지들이 해당 프로세스에서 필요로 하는 것이었다면,

그 프로세스 역시 페이지 부재를 발생시키고  또 다른 프로세스에서 프레임을 가져온다.

이러한 프로세스들이 페이지 스왑 인, 스왑 아웃을 위해 페이징 장치를 사용해야 한다.

페이징 장치에 대한 큐잉이 진행되면서 준비 완료 큐는 비게 된다.

프로세스들이 페이징 장치를 기다리는 동안 CPU이용률은 떨어진다.

CPU 스케줄러는 이용률이 떨어지는 것을 보고, 이용률을 높이기 위하여 새로운 프로세스를  추가하여 

다중 프로그래밍의 정도를 더 높인다.

새로 시작하는 프로세스는 실행중인 프로세스들로부터 프레임을 가져오고자 하며 

더 많은 페이지 부재와 더 긴 페이징 장치 대기 시간을 야기한다.

 

결과적으로 CPU 이용률은 더욱 떨어지고, CPU스케줄러는 다중프로그래밍 정도를 더욱 높이려고 한다. 

결국 쓰레싱이 일어나게 되어 시스템의 처리율은 대단히 낮아지고 페이지 부재는 상당히 늘어난다. 

실질 메모리 접근 시간은 증가하고 프로세스들은 페이징 하는데 시간을 다 소비 하게 되어 아무런 일도 

할 수 없게 된다. 

 

3. 쓰레싱은 지역교환 알고리즘이나 우선순위 교환 알고리즘을 사용하여 제한할 수 있음

지역교환 알고리즘 하에서는 한 프로세스가 쓰레싱을 유발하더라도 다른 프로세스로부터 프레임을 뺏어 올 수

없으므로,  다른 프로세스는 쓰레싱으로 부터 자유로울 수 있다.

 

4. 쓰레싱 현상을 방지하기 위해서?

각 프로세스가 필요로하는 최소한의 프레임 개수를 보장해주어야 한다.

지역성이란 무엇인지 설명하시오.

 

지역성은 실행 중인 프로세스에서 나타나는 특성이다. 동일한 값이나 관련 저장 위치를 자주 액세스하는 현상, 즉 한번 참조한 데이터(동일한 값)를 짧은 시간 안에 다시 참조하거나 한번 참조한 데이터의 근처(관련 저장 위치)에 있는 데이터를 짧은 시간 안에 참조하는 현상을 의미한다. 다시 말해, 프로세스는 어느 실행 단계 동안 메모리의 정보를 균일하게 액세스하는 것이 아니라 선호하는 특정 페이지만 집중적으로 참조하느 현상으로 국부성이라고도 한다.

 

시간 지역성

시간 지역성은 특정 자원들을 상대적으로 짧은 시간안에 재사용한다는 것을 의미한다. 한 순간 한 지점에서 특정 메모리 위치를 참조할 때 동일한 위치에서 가까운 미래에 다시 참조할 가능성이 높다. 즉, 최근에 액세스한 항목은 오래지 않아 다시 액세스할 가능성이 있다는 것이다. 순환(루프), 서브 프로그램, 스택, 계산이나 합계에 사용하는 변수는 시간 지역성에 적용하는 예이다.

 

공간 지역성

공간 지역성은 프로세스가 메모리의 어떤 위치를 참조하면 그 근처를 이후에도 계속 참조할 가능성이 높다는 것이다. 상대적으로 가까운 위치에서 데이터 요소를 사용한다는 것을 의미한다. 메모리의 특정 위치를 특정 시간에 참조할 때 가까운 미래에 가까운 메모리 위치를 참조할 가능성이 높다. 데이터 정렬과 1차원 배열의 요소 탐색과 같이 선형 액세스할 때를 순차적 지역성이라고 한다. 이는 공간 지역성의 특수한 경우이다. 배열 검색(순회), 순차적 코드의 실행, 근처의 관련 변수 선언 등이 공간 지역성을 적용하는 예이다.

 

캐시의 지역성 원리

캐시 메모리는 속도가 빠른 장치와 느린 장치간의 속도차에 따른 병목 현상을 줄이기 위한 범용 메모리이다. 이러한 역할을 수행하기 위해서는 CPU 가 어떤 데이터를 원할 것인가를 어느 정도 예측할 수 있어야 한다. 캐시의 성능은 작은 용량의 캐시 메모리에 CPU 가 이후에 참조할, 쓸모 있는 정보가 어느 정도 들어있느냐에 따라 좌우되기 때문이다.

이 때 적중율(Hit rate)을 극대화 시키기 위해 데이터 지역성(Locality)의 원리를 사용한다. 지역성의 전제조건으로 프로그램은 모든 코드나 데이터를 균등하게 Access 하지 않는다는 특성을 기본으로 한다. 즉, Locality란 기억 장치 내의 정보를 균일하게 Access 하는 것이 아닌 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성인 것이다.