os.md

🫁 OS QnA

Process, Thread

프로세스가 무엇인가요? (Context, Context Switching, Blocked 상태와 Suspended 상태 차이)

프로세스란 디스크에 실행 파일로 존재하던 프로그램이 메모리에 적재되어 실행되기 시작하면 프로세스라 부릅니다.

프로세스 컨택스트란 CPU 스케쥴링에 의해 CPU 점유권을 빼앗겼다가 다시 획득하게 되었을때 이전의 상태를 재현하기 위해 필요한 모든 정보를 말합니다.

• 프로세스 문맥은 크게 3가지로 나뉩니다.
  • CPU 의 수행 상태를 나타내는 하드웨어 컨택스트 = PC값, 레지스터값
  • 프로세스의 주소 공간 = code, data, stack
  • 프로세스 관련 커널 자료구조인 PCB

컨택스트 스위칭이란 CPU 점유권이 현재 프로세스에서 다음 프로세스로 넘어가는 과정에서 점유권을 빼앗기는 프로세스는 현재 컨택스트를 기억하기 위해 PCB에 CPU의 pc값과 레지스터 값을 저장해두고, 점유권을 얻는 프로세스는 이전의 컨택스트를 복원하기 위해 PCB의 pc값과 레지스터 값을 CPU에 복원합니다.

blocked 상태는 프로세스가 cpu 점유권을 가지고 명령어를 수행하다가 io작업과 같은 시간이 오래 걸리는 작업을 할경우의 상태입니다. 해당 프로세스는 cpu 점유권을 반환하고, io작업을 마치면 ready 상태가 되어 ready queue에 대기하여 cpu 스케쥴러에게 스케쥴링 당하길 기다립니다.

suspended 상태는 CPU 또는 외부(사람, 중기 스케쥴러)에 의해 강제로 정지당한 프로세스의 상태입니다. 이 상태의 프로세스는 메모리를 빼앗겨 디스크로 swap out되기 때문에 외부에서 재개 해줘야 active한 상태가 됩니다.

스케쥴러에 대해 아시나요? (스케쥴러 종류)

어떤 프로세스에게 자원을 할당해줄지 결정하는 운영체제의 커널 코드를 지칭합니다.

3가지 스케쥴러가 있습니다.

• 장기 스케쥴러 (job 스케쥴러)

  메모리 자원을 어떤 new 상태의 프로세스에게 할당할지 결정하는 스케쥴러입니다.

  이 스케쥴러는 메모리에 동시에 올라갈 프로세스의 수를 제어합니다. 보통 시분할 시스템에서는 장기 스케쥴러가 없습니다. (new 상태의 프로세스는 메모리를 할당받아 곧바로 ready 상태가 됩니다)

  따라서 메모리에 동시에 올라갈 프로세스의 수를 결정하는 것은 중기 스케쥴러에 의해 수행됩니다.

• 중기 스케쥴러 (swapper)

  중기 스케쥴러는 메모리에 동시에 많은 프로세스가 올라갈 경우, 일부 프로세스를 골라 메모리를 빼앗고 디스크로 swap out 시키는 역할을 합니다.

  중기 스케쥴러에 의해 메모리를 빼앗긴 프로세스는 suspended 상태가 됩니다.

• 단기 스케쥴러 (cpu 스케쥴러)

  cpu 점유권을 어떤 프로세스에게 할당할지 결정하는 스케쥴러입니다.

  스케쥴링이 일어나는 단위가 밀리세컨드로 굉장히 자주 일어납니다.

스레드가 무엇인가요?

스레드란 프로세스가 할당받은 자원을 이용하는 실행 단위입니다.

프로세스 하나에 CPU 수행 단위만 여러개 두었을 때 그 각각을 스레드라 합니다.

• 스레드마다 별도로 cpu 수행에 필요한 정보인 pc값과 레지스터 값이 필요합니다.
• 스레드는 프로세스의 주소 영역중 code, data 영역은 공유하지만 stack 영역은 독립적으로 가지고 있습니다. code 영역을 수행하다 함수 호출이 일어나면, 해당 함수에 관련된 정보를 stack에 쌓아 두기 때문에 스레드 마다 독립적인 stack 영역이 필요합니다.

만약 스레드가 없다면

• 동일한 작업을 수행하기 위해 여러 프로세스를 생성하면, 각각의 메모리 주소 공간과 PCB가 독립적으로 만들어져 메모리 공간 낭비가 심해집니다.

멀티 프로세스, 멀티 스레드의 장단점에 대해 설명해보세요

멀티 프로세스는

• 하나의 프로그램을 다수의 프로세스로 구성하여 각 프로세스가 병렬적으로 작업을 수행하는 것입니다.
• 장점
  • 각 프로세스 마다 독립된 메모리 공간을 가지기 때문에 하나의 프로세스에 오류가 발생해도 다른 프로세스에 영향이 없습니다.
• 단점
  • 독립된 메모리 영역을 가지기 때문에 컨택스트 스위칭이 자주 일어나 오버헤드가 발생합니다.
  • 프로세스 간에 통신이 원칙적으로 제한되어 있지만, 그럼에도 불구하고 별도의 통신을 IPC를 통해 수행합니다. 예를 들어 shared memory 방식을 사용하면 커널로부터 프로세스끼리 공유할 메모리를 할당받고, 공유 메모리 공간을 통해 통신을 할 수 있습니다. 다만 공유 자원에 대한 동기화 문제를 해결해야 합니다.

멀티 스레드는

• 하나의 프로세스에 여러 스레드로 자원을 공유하며 작업을 나누어 수행하는 것입니다
• 장점
  • 일단 하나의 프로세스의 메모리 공간 code, data과 자원을 공유하기 때문에 효율적인 자원활용이 가능합니다. 또한 프로세스의 IPC와 같은 통신을 위한 기술이 필요하지 않습니다.
  • 응답성이 높습니다. 웹 브라우저의 하나의 탭에서 하나의 스레드가 웹 페이지를 다운 받으면, 그와 동시에 다른 스레드가 다운 받은 html을 화면에 출력하는 상황처럼 응답성을 높힐 수 있습니다.
• 단점
  • 여러 스레드끼리 자원을 공유하기 때문에 그에 따른 동기화 문제가 발생할 수 있습니다. 동기화 문제는 뮤텍스, 세마포어 방식을 활용하여 해결할 수 있습니다.
  • 하나의 스레드에 문제가 생기면 전체 프로세스가 영향을 받습니다.

IPC에 대해서 설명해보세요

IPC란 프로세스간에 통신 기법입니다.

프로세스 끼리의 통신은 원칙적으로 제한되어있지만 IPC 기법을 통해 통신을 할 수 있습니다.

대표적으로 shared memory, message passing 기법이 있습니다.

message passing

• 프로세스가 커널을 통해 메시지를 주고 받으며 통신하는 방법입니다.
• 통신하려는 프로세스의 이름을 명시적으로 표시하여 전달하는 direct communication방식과
• mailbox또는 port를 통해 메시지를 간접적으로 전달하는 indirect communication 방식이 있습니다.

shared memory 방식을 사용하면

• 커널로부터 프로세스끼리 공유할 메모리를 할당받고, 공유 메모리 공간을 통해 통신을 할 수 있습니다. 다만 공유 자원에 대한 동기화 문제를 해결해야 합니다.

CPU 스케줄러 & 스케쥴링 알고리즘

CPU 스케줄링이 무엇인지와 목적을 설명해주세요.

CPU 스케줄러는 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드입니다. CPU를 사용하는 패턴이 상이한 여러 프로그램이 동일한 시스템 내부에서 함께 실행되기 때문에 효율적인 CPU 사용을 위해 필요합니다.

비선점방식과 선점방식을 설명해주세요.

비선점 방식은 프로세스가 CPU를 점유하고 있는 경우 다른 프로세스가 CPU를 빼앗지 못하는 방식입니다. 비선점방식은 CPU를 중간에 가로채지 않기 때문에 응답시간 예측이 용이하다는 장점이 있지만 중요한 작업이 오래 기다리는 경우가 발생할 수 있다는 단점이 있습니다. 선점 방식은 프로세스가 CPU를 점유하고 있어도 우선 순위가 높은 프로세스가 오면 CPU를 빼앗을 수 있는 방식입니다. 선점방식은 우선 순위가 높은 프로세스가 빠르게 처리할 수 있다는 장점이 있지만 잦은 Context Switching으로 오버헤드가 증가한다는 단점이 있습니다.

스케줄링 기법 중 FCFS의 단점과 해결 방법을 설명해주세요.

FCFS 는 대기 큐에 도착한 순서에 따라 CPU를 할당합니다. 그래서 긴 작업이 짧은 작업을 오랫 동안 기다릴 수 있습니다. 단점을 해결하는 방법으로는 준비 큐에서 기다리고 있는 프로세스 중 가장 CPU 요구량이 적은 것을 먼저 실행시켜 주는 SJF(Shortest Job First)가 있습니다.

Process Synchronization

프로세스를 동기화 해야하는 이유가 무엇인가요?

공유 데이터에 두 개 이상의 프로세스가 동시에 접근하면 data inconsistency가 발생하기 때문입니다.

• 동기화를 하기 위해서 어떤 이슈를 해결해야하나요??

첫 번째로 어떻게 한 프로세스가 다른 프로세스에게 정보를 넘길 것인지 정해야하고, 두 번쨰로 어떻게 두개 이상의 프로세스가 하나의 데이터에 동시에 접근하지 않도록 할 것인지와 의존 관계가 존재할 때 어떻게 적절한 순서를 부여할 것인지 정해야합니다.

Race condition은 무엇인가요?

하나의 공유 데이터에 여러 process가 접근하려 하는 상황이 race condition이라고 한다. 마지막 결과는 정확히 어떤 프로세스가 언제 수행되는지에 따라서 결정됩니다.

• race condition은 언제 발생하나요?

첫 번째는 커널 작업을 수행 중에 인터럽트가 발생할 때와 프로세스가 system call을 하여 커널모드로 진입하여 수행하는 도중 context switch가 발생할 때, 마지막으로 멀티 프로세서에서 공유 메모리 내의 커널 데이터에 접근할 때 입니다.

Critical region은 무엇인가요?

• Criticla region 문제를 해결하기 위한 세 가지 조건을 말해주세요
  mutual exclusion, progress, bound waiting입니다. mutual exclusion은 하나의 프로세스가 임계구역에 있을 때 다른 프로세스는 들어갈 수 없는 것이고, progress는 임계구역에 들어간 프로세스가 없다면 어느 프로세스가 들어갈 것인지 적절히 선택해줘야하는 것입니다. 마지막으로 bound waiting 는 그 어떤 프로세스도 임계구역에 들어가기 위해 영원히 기다려서는 안된다는 것입니다.

• 이 문제를 해결하기 위한 대표적인 방법에는 무엇이 있나요?

  semaphore, mutex, monitor가 있습니다.

• Semaphore, mutex, monitor이 무엇인가요?

  mutex는 임계 구역을 보호하고 경쟁상태를 방지하기 위한 방법으로 mutex lock을 사용합니다. 프로세스는 임계구역에 들어가기 전에 반드시 락을 획득해야하고, 임계구역을 빠져나올 때 락을 반환해야합니다. mutual exclusion을 제공하지만 bounded waiting 조건을 위배합니다. 왜냐하면 특정 프로세스가 임계구역내에 있을 때 while문을 통해서 반복문에서 빠져나오지 못하기 때문입니다. 프로세스의 시간이 짧을 때 mutex는 유용합니다.

  semaphore는 자원의 개수를 뜻합니다. 동시에 자원에 접근할 수 있는 허용가능한 counter의 개수 입니다. 세마포어는 여러 프로세스들에 의해 공유되는 변수로 정의하고 이 변수는 오직 P, V라는 atomic한 연산에 의해서만 접근 가능합니다.

  monitor는 mutex와 condition variable을 가지고 있는 동기화 메커니즘으로 상호배제를 함으로써 임계구역에 하나의 프로세스만 들어갈 수 있습니다. monitor는 실제 프로그램에서 세마포어를 구현한 것입니다. 상호 배제를 위한 데이터 및 프로그램 모듈, 운영체제 내부의 프로그램을 모니터라고 한다.

Mutex vs. Semaphore vs. Monitor를 말해주세요

• Mutex vs. Semaphore

세마포어는 뮤텍스가 될 수 있지만 무텍스는 세마포어가 될 수 없다. 또 세마포어는 소유할 수 없지만 뮤텍스는 소율할 수 있고 소유한 사람이 반드시 원상태로 돌려놓아야한다. 뮤텍스의 경우 뮤텍스를 소유하고 있는 스레드가 이 뮤텍스를 해제할 수 있다. 하지만 세마포어는 소유하지 않고 있는 다른 스레드가 세마포어를 해제할 수 있다. 뮤텍스는 동기화대상이 1개 세마포어는 동기화 대상이 여러 개일 때 사용한다.

• Semaphore vs. monitor

자바에서는 모니터를 모든 객체에게 기본적으로 제공하지만 c에서는 사용할 수 없다. 세마포어는 카운터라는 변수값으로 프로그래머가 상호배제나 정렬의 목적으로 사용 시 매번 값을 따로 지정해줘야하는 번거로움이 있다. 반면에 모니터는 이러한 일들이 캡슐화되어 있어서 개발자는 카운터 값을 0 또는 1로 주어야하는 고민을 할 필요가 없다.

• monitor vs. mutex

뮤텍스는 다른 프로세스나 스레드 간에 동기화를 위해 사용된다. 모니터는 하나의 프로세스 내에서 다른 스레드 간에 동기화할 때 사용한다. 반면에 모니터는 하나의 프로세스 내에서 다른 스레드 간에 동기화할 때 사용한다. 뮤텍스는 운영체제 커널에 의해서 제공되기 때문에 system call로 인하여 속도가 느리고 그에 반해 모니터는 프레임 워크나 라이브러리 그 자체에서 제공되기 때문에 속도가 빠르다.

동기와 비동기 & 블로킹과 논블로킹

비동기, 동기, 블로킹, 논블로킹의 개념에 대해서 설명해주세요

처리해야할 작업들을 어떠한 흐름으로 처리할 것인지에 따라 동기와 비동기로 나눌 수 있습니다.

• 2개 이상의 주체가 작업을 동시에 시작하거나, 동시에 끝내거나, 한 주체가 작업을 끝냄과 동시에 다른 주체가 작업을 시작하는 흐름을 동기라고 합니다.
• 비동기란 2개 이상의 주체가 각자 별도의 시작시간 또는 종료 시간을 가지며 작업을 처리하는 흐름입니다.

처리되어야 하는 하나의 작업이 전체적인 작업의 흐름을 막는지 안막는지에 따라 블로킹과 논블로킹으로 나눌 수 있습니다.

• 블로킹이란 함수를 호출한 주체가 제어권을 함수에게 넘겨주기 때문에 전체적 작업 흐름이 멈추고, 함수가 작업 결과를 반환해야 작업을 이어갈 수 있습니다.
• 논블로킹이란 함수를 호출한 주체가 제어권을 가지기 때문에 함수의 작업 결과를 받을 때까지 대기하지 않고 전체적 작업 흐름을 이어갑니다.

비동기, 동기, 블로킹, 논블로킹의 각 조합의 특징을 말해주세요

동기 + 블로킹

• 흔하게 접할 수 있는 동기 작업 방식입니다.
  • 동기이기 때문에 2개 이상의 주체가 작업 흐름을 맞춥니다. 기능A가 먼저 개발된 후에야 기능B를 개발해야 하는 상황을 예시로 들 수 있습니다.
  • 블로킹이기 때문에 기능A를 개발하는 동안 완료될 때까지 전체적인 작업의 흐름이 멈춥니다. 기능A와 기능B를 동시에 개발할 수 없고, 기능A의 개발이 완료된 후에야 기능B의 개발을 시작할 수 있습니다.

동기 + 논블로킹

• 모든 실행과 흐름이 순차적이기 때문에 제어하기 쉬운 조합입니다.

  • 동기이기 때문에 기능A와 기능B의 개발 순서가 정해져 있습니다.

  • 논블로킹이기 때문에 기능A를 개발하는 동안 전체적인 작업 흐름이 멈추지 않습니다. 다만 기능A의 개발이 완료되었는지 주기적으로 확인하는 polling 작업이 필요합니다.

    동시에 동기적인 작업이라 기능A가 개발되는 동안 기능B를 개발할 수 없습니다. 기능 개발의 순서는 A→ B이기 때문입니다.

비동기 + 블로킹

• 작업의 흐름을 비동기로 설계했지만 블로킹이기 때문에 동기 + 블로킹과 같은 흐름을 가집니다. 이는 가장 비효율적인 모델로 의도치 않게 동작합니다. 또는 직관적인 코드 흐름을 유지하면서 작업을 병렬적으로 처리하고자 사용하기도 합니다.
  • 비동기이기 때문에 기능A와 기능 B의 개발 순서가 없습니다. 아무렇게나 개발해도 됩니다.
  • 블로킹이라 기능A를 개발하는 동안에는 기능 B를 개발할 수 없습니다. 기능A의 개발이 완료되고 나서 기능 B를 개발할 수 있습니다.

비동기 + 논블로킹

• 성능과 자원의 효율 측면에서 가장 우수한 조합입니다.
  • 비동기이기 때문에 기능A와 기능 B의 개발 순서가 없습니다.
  • 논블로킹이기 때문에 기능A를 개발하는 동안 기능B를 개발할 수 있습니다.

어떤 조합이 가장 효율적이라 생각하시나요? 그 이유는?

비동기 + 논블로킹 조합이 가장 효율적이라고 생각합니다.

개발 순서에 구애받지 않고 기능 개발을 할 수 있습니다. (비동기) 또한 기능을 개발하는 동안 작업 흐름이 멈추지 않기 때문에 동시에 다른 기능을 개발할 수 있습니다. (논블로킹)

어떤 조합이 가장 비효율적이라 생각하시나요? 그 이유는?

비동기 + 블로킹 조합이 가장 비효율적이라 생각합니다.

개발 순서에 구애 받지 않고 개발을 할 수 있지만, 하나의 기능이 개발되는 동안 작업 흐름이 멈춰 동시에 다른 개발을 할 수 없게 됩니다. 결국 기능을 개발하는 순서에 따라 전체적인 작업 흐름이 의도치 않게 정해집니다.

Deadlock

deadlock이란 무엇인가요?

데드락은 프로세스간에 서로가 가진 자원을 기다리며 block된 상태입니다. 자원을 동시 충족할 수 없기 때문에 발생합니다.

deadlock 발생 조건 4가지가 무엇인가요?

발생 조건에는 상호 배제, 비선점, 점유 대기, 순환 대기가 있습니다. 상호 배제는 두 개 이상의 프로세스가 동시에 공유자원에 접근할 수 없는 것입니다.

비선점 조건은 프로세스가 자원을 내놓을 뿐 강제로 빼앗기지 않는 것입니다.

그 다음으로 점유대기는 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는 것입니다.

마지막으로 순환대기는 자원을 기다리는 프로세스 간에 사이클이 형성되어야 합니다.

위 4가지 조건이 동시에 성립할 때 deadlock이 발생합니다.

4가지를 전부 이어서 생각해보면 서로 상호배제 하고 있는 프로세스가 서로의 자원을 원하면 사이클이 발생한 것이고 다른 자원을 기다리면서 자원을 놓지 않고 계속 가지고 있고 또 비선점으로 프로세스 자원을 빼앗지 않기 때문에 이렇게 되면 교착 상태가 발생할 수 밖에 없는 것입니다.

deadlock 처리 방법에는 무엇이 있나요?

deadlock 처리 방법에는 deadlock prevention, deadlock avoidance, deadlock detection and recovery, deadlock ignorance가 있습니다.

• deadlock prevention은 무엇인가요?

자원 할당 시 데드락의 4가지 필요 조건 중 어느 하나를 만족하지 않게 하는 것입니다. 우선 mutual exclusion을 부정하면 공유해서는 안되는 자원에 mutual exclusion을 보장하지 않습니다.

hold and wait를 부정하게 되면 프로세스 시작 시 모든 필요한 자원을 할당 받게 하는 방법과 자원이 필요할 경우 보유 자원을 모두 내놓고 다시 요청하게 하는 방법이 있습니다.

비선점 부정의 경우 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점되게 하거나 모든 필요한 자원을 얻을 수 있을 때 그 프로세스를 다시 시작시키는 방법이 있습니다.

순환 대기 부정은 자원에 고유한 번호를 할당하고 번호 순서대로 자원을 요구하도록 하는 방법입니다.

예방기법을 사용하게 되면 성능 저하와 starvation 문제를 유발합니다.

• deadlock avoidance는 무엇인가요?

교착상태 회피는 교착 상태가 발생하면 피해나가는 방법입니다. 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아 있게 되는지를 검사하여 교착 상태를 회피하는 기법입니다. 안정 상태에 있으면 자원을 할당하고 그렇지 않으면 다른 프로세스들이 자원을 해제할 때까지 대기합니다. 시스템이 안전상태에 있으면 데드락이 발생하지 않고, 불안전 상태에 있으면 데드락의 가능성이 있습니다.

회피의 경우 자원의 유형 당 인스턴스의 개수에 따라 사용하는 알고리즘이 다릅니다. 1개 인스턴스라면 자원 할당 그래프 알고리즘을 이용하고 2개 이상의 인스턴스라면 banker’s 알고리즘을 사용합니다.

• 자원할당 그래프 알고리즘은 무엇인가요?

자원 할당 그래프를 그려서 미래 자원 할당시 그래프가 사이클이 생기는 경우가 있다면 요청 자원을 할당하지 않는 방법입니다.

• banker’s algorithm은 무엇인가요?

프로세스와 자원 형태에 따라서 최대 자원을 파악하여 특정 순서에 맞춰 할당했을 때, deadlock이 발생하지 않는지 확인하는 방법입니다. 프로세스가 자원을 모두 사용하면 자원을 반납하기 때문에 그렇게 새로 확보된 자원이 점점 늘어나 자원을 많이 사용하는 프로세스까지 모두 완료할 수 있습니다. 자원을 지금 당장 줄 수 있음에도 만약 불안정 상태가 발생할 수 있다면 자원을 주지 않습니다. 이것을 판단하는 기준은 최대 자원 요청과 현재 가용 자원의 충족 여부입니다.

• deadlock detection and recovery가 무엇인가요?

데드락 탐지 및 회복도 회피와 비슷하게 동작합니다. 하지만 데드락 발생은 허용하지만 그에대한 탐지 루틴을 두어서 데드락이 발견되면 회복되는 방식을 채택하고 있습니다.

탐지는 single instance의 경우 wait-for graph를 multiple instance라면 bankers algorithm을 이용합니다.

• deadlock recovery는 어떤 방식으로 할 수 있나요?

두가지 방법이 있는데 첫 번째로 process를 끝내는 방식과 자원 선점을 하는 방식이 있습니다. 프로세스를 끝내는 방식은 모든 교착 상태의 프로세스를 중단하기 때문에 사이클을 인위적으로 없애는 방식입니다.

두 번째 방법은 자원을 선점하게 두는 것인데 안전상태로 rollback하여 process를 재시작합니다. 그렇게되면 기아 문제가 발생할 수 있습니다. 왜냐하면 동일한 프로세스가 계속해서 희생 프로세스로 선정될 수 있기 때문입니다.

• deadlock ignorance가 무엇인가요?

deadlock이 시스템이 책임지지 않는 것입니다. 현대 운영체제는 이방법을 채택하고 있습니다. 전원 끄기가 이 방법 중에 하나 입니다.

Paging

사용자 프로세스 영역의 할당 방법의 종류에 대해 설명해주세요. -> (연속 할당, 불연속 할당) 각각의 종류 특징 설명

사용자 프로세스 영역의 할당 방법에는 먼저 크게 연속 할당과 불연속 할당이 있습니다. 연속 할당은 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 할당이고 불연속 할당은 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라가는 할당입니다. 연속할당에는 고정 분할 방식과 가변 분할 방식이 존재하는데요. 고정 분할 방식은 메모리를 주어진 개수만큼의 영구적인 파티션으로 미리 나누어두고 각 파티션에 하나의 프로세스를 적재해 실행합니다. 그에 반해 가변 분할 방식은 메모리에 적재되는 프로그램의 크기에 따라 파티션의 크기, 개수가 동적으로 변하는 방식입니다. 불연속 할당에는 paging, segmenting, paged segmentation 방식이 존재합니다.

Paging 기법에 대해 설명해주세요.

페이징 기법은 프로세스의 주소 공간을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지를 저장하는 방식입니다. 물리적 메모리도 페이지와 동일한 크기의 프레임으로 미리 나누어 둡니다. 메모리에 올리는 단위가 동일한 크기의 페이지 단위이므로 외부 단편화가 발생하지 않고, 동적 메모리 할당 문제도 고려할 필요가 없습니다.

Paging의 장단점에 대해 설명해주세요.

메모리에 올리는 단위가 동일한 크기의 페이지 단위이므로 먼저 외부 단편화가 발생하지 않고, 동적 메모리 할당 문제도 고려할 필요가 없다는 장점이 있습니다. 두번쨰로 Swapping이 용이해진다는 장점이 있습니다. 그에 반해 프로그램의 크기가 항상 페이지 크기의 배수가 된다는 보장이 없으므로 프로세스의 주소 공간 중 제일 마지막에 위치한 페이지에서는 내부 조각이 발생할 수 있고 메모리에 접근하기 위해서 페이지 테이블에 먼저 접근해야하기 때문에 실제적으로 2번의 메모리 접근이 필요합니다. 또 각 프로세스마다 페이지 테이블을 가지고 있어 페이지 테이블의 크기가 방대해지는 문제가 생깁니다.

Cache Locality

캐시의 지역성에 대해 설명하세요.

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

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

이 데이터 지역성은 대표적으로 시간 지역성(Temporal Locality)과 공간 지역성(Spatial Locality)이 있습니다.

시간 지역성은 최근에 참조된 주소의 내용은 곧 다음에 다시 참조되는 특성이고, 공간 지역성은 대부분의 실제 프로그램이 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성입니다.

캐시 라인을 사용하는 이유는 무엇인가요?

캐시에 저장되어있는 데이터를 빠르게 접근하여 출력할 수 있도록 캐시에 데이터를 저장할때 캐시라인을 사용합니다.

Virtual Memory2

페이지 교체가 왜 필요한가요?

CPU가 참조하려는 데이터가 포함된 페이지가 현재 메모리에 적재되어 있지 않다면 page fault가 발생합니다.

page fault가 발생하면 디스크에서 해당 페이지를 메모리의 page frame으로 불러 들입니다.

비어있는 page frame이 없을 경우가 존재합니다. 이때 기존에 적재된 page frame과 사용할 page frame을 교체가 필요합니다.

페이지 교체 알고리즘에는 무엇이 있나요? 각각의 특징은?

페이지 교체 알고리즘에는 Optimal, FIFO, LRU, LFU, Clock 알고리즘이 있습니다.

• Optimal

  • 미래에 참조될 페이지 정보를 미리 알고 있다는 가정이 전제된 알고리즘으로 가장 먼 미래에 참조될 페이지를 victim 페이지로 선택합니다.

    페이지 부재율이 가장 작은 알고리즘으로 모든 페이지 교체 알고리즘 성능의 upper bound를 제공하지만, 실제 시스템에서 사용하지 못합니다.

• FIFO

  • 먼저 swap in 된 페이지를 victim 페이지로 선택하는 알고리즘입니다.

    프로세스에 할당된 page frame이 늘어나면 오히려 페이지 부재율이 높아지는 FIFO Anomaly가 존재합니다.

• LRU

  • 가장 오래전에 참조된 페이지를 victim 페이지로 선택하는 페이지 교체 알고리즘입니다.

    페이지 부재가 발생한 시점 이전의 페이지 참조 이력을 참고하여 victim 페이지를 선택합니다.

• LFU

  • 페이지의 참조 횟수가 가장 적은 페이지를 victim 페이지로 선택하는 교체 알고리즘입니다.

    가장 적은 참조 횟수를 가진 페이지가 여러개 있다면, 임의로 victim 페이지를 선정합니다.

• Clock

  • 페이지에 reference bit를 두어 포인터를 시계방향으로 이동시키면서 reference bit가 0인 페이지를 victim 페이지로 선택하는 알고리즘입니다.

    포인터를 총 두번 회전시킵니다. 첫 번째 회전에서는 페이지의 reference bit가 1인 것을 0으로 변경합니다. 두 번째 회전에서 페이지의 reference bit가 0인 것을 victim 페이지로 선정합니다.

    만약 페이지에 Write 연산이 이루어졌다면 modified bit가 1이 됩니다. reference bit가 0이면서 modified bit가 1인 페이지는 disk 로 swap out할 때 변경된 내용을 디스크에 반영하기 때문에 IO 작업이 동반됩니다.

    성능을 위해 reference bit가 0인 페이지들 중 modified bit가 0인 페이지를 우선적으로 victim 페이지로 선정하는 방식이 있습니다.

FIFO와 LRU의 차이점은 무엇인가요?

FIFO 알고리즘은 가장 먼저 들어온 페이지를 교체하기 때문에 1번째로 들어온 페이지가 최근까지 참조됐음에도 불구하고 victim 페이지로 선정됩니다.

LRU 알고리즘은 가장 오래전에 참조된 페이지를 교체하기 때문에 1번째로 들어온 페이지를 가장 최근에 참조했다면 해당 페이지는 victim 페이지 대상에서 멀어집니다.

LRU와 LFU을 비교해보세요. LRU와 LFU 알고리즘은 어떻게 구현되었는지 아시나요? 각 알고리즘의 시간 복잡도를 말해보세요

LRU와 LFU 비교

• LRU 알고리즘은 페이지 부재가 발생한 직전의 페이지 참조 시점만 확인하지만, LFU는 장기적인 시간 규모를 확인하여 victim 페이지를 선정하기 때문에 페이지의 인기도(참조 횟수)를 정확히 반영합니다.
• LFU는 페이지 참조 시점의 최근성을 반영하지 못합니다. 최근에 거의 참조되지 않은 페이지일지라도 과거에 많이 참조되었다면 victim 페이지로 선정될 가능성이 적어집니다.
• LFU 알고리즘은 LRU 알고리즘보다 구현이 복잡합니다.

LRU, LFU 알고리즘의 구현

• LRU

  • 참조 시점이 가장 오래된 페이지를 victim으로 고르기 때문에 LinkedList로 구현합니다. 가장 최근에 참조된 페이지를 tail에 가장 오래전에 참조된 페이지를 head에 둡니다.

    페이지가 재참조 되면, 해당 페이지의 참조 시점은 가장 최근이 됩니다. 따라서 LinkedList의 마지막(tail)으로 이동합니다. 이때 시간 복잡도는 O(1)입니다.

    victim 페이지를 선정할 때 LinkedList의 head에 위치한 페이지를 선택하면 됩니다. 따라서 이때 시간 복잡도는 O(1)입니다.

• LFU

  • 참조 횟수가 적은 페이지를 victim으로 선정하기 때문에 Heap 자료구조로 구현합니다.

    페이지가 재참조되면, 해당 페이지의 참조 횟수가 증가합니다. 이후 Heap 구조를 재구성하기 때문에 O(logN)의 시간복잡도를 가집니다.

    victim 페이지를 선정할 때, root 노드를 선택하면 됩니다. 이때의 시간 복잡도는 O(1)입니다. 이후 heapify를 통해 Heap 구조를 재구성하는 시간복잡도는 O(logN)이므로 총 O(logN)의 시간복잡도를 가집니다.

페이징 시스템에서 LRU, LFU 알고리즘을 적용할 수 있나요? 그 이유는? 그럼 어떤 알고리즘을 페이징 시스템에 적용할까요?

페이징 시스템에서 LRU, LFU 알고리즘을 적용할 수 없습니다. 왜냐하면 페이지 교체 알고리즘을 수행하는 주체가 운영체제인데, LRU, LFU 알고리즘에 사용될 페이지 정보를 운영체제가 정확하게 알 지 못합니다.

• 페이지 부재가 발생하면, CPU 점유권이 프로세스에서 운영체제로 넘어갑니다. 운영체제는 페이지 교체를 수행하면서, 페이지의 참조 시점 정보를 알 수 있습니다.
• 하지만 참조하려는 페이지가 메모리에 존재하면, 페이지 테이블을 통해 하드웨어적으로만 주소 변환이 이뤄집니다. 따라서 페이지의 참조 시점이나 참조 횟수를 운영체제가 알지 못합니다.

운영체제가 반 쪽짜리 페이지 정보를 가지기 때문에 실제 페이징 시스템에서 LRU, LFU 알고리즘을 적용할 수 없습니다.

실제 페이징 시스템에서 적용가능한 알고리즘은 Clock 알고리즘입니다

Clock 알고리즘의 동작방식을 말해주세요

페이지에 reference bit를 두어 포인터를 시계방향으로 이동시키면서 reference bit가 0인 페이지를 victim 페이지로 선택하는 알고리즘입니다.

포인터를 총 두번 회전시킵니다. 첫 번째 회전에서는 페이지의 reference bit가 1인 것을 0으로 변경합니다. 두 번째 회전에서 페이지의 reference bit가 0인 것을 victim 페이지로 선정합니다.

만약 페이지에 Write 연산이 이루어졌다면 modified bit가 1이 됩니다. reference bit가 0이면서 modified bit가 1인 페이지는 disk 로 swap out할 때 변경된 내용을 디스크에 반영하기 때문에 IO 작업이 동반됩니다.

성능을 위해 reference bit가 0인 페이지들 중 modified bit가 0인 페이지를 우선적으로 victim 페이지로 선정하는 방식이 있습니다.

Thrashing이 무엇인가요? 이를 예방하는 방법에 대해 설명해주세요

쓰레싱이란 프로세스의 페이지 부재율이 계속해서 높아지는 악순환을 말합니다.

1. 메모리에 올라온 프로세스의 수가 많으면 각 프로세스마다 page frame이 적게 할당되어 페이지 부재율이 높아집니다.
2. 페이지 부재가 발생하면 페이지가 swap out, swap in될 때 IO 작업이 동반되기 때문에 CPU 이용률이 낮아집니다.
3. 운영체제는 낮은 CPU 이용률을 보고 메모리에 올라온 프로세스의 수를 늘리게 됩니다.

결국 이는 프로세스의 페이지 부재율을 더욱 높혀 상황을 악화 시킵니다. 이와 같은 상황을 쓰레싱이라고 합니다.

쓰레싱을 예방하기 위해서 Working Set알고리즘, PFF(Page Fault Frequency) 알고리즘을 사용합니다.

Page 사이즈가 작으면 어떻게 될까요? 크면 어떻게 될까요?

페이지 사이즈가 작으면

• 페이지 개수가 많아지고, 페이지 테이블의 크기가 커져 메모리 공간을 많이 차지합니다.
• 내부 조각의 개수가 감소합니다.
• 페이지에 필요한 정보의 비율이 높기 때문에 메모리 이용이 효율적입니다

페이지 사이즈가 크면

• 참조된 주소의 인접 주소를 다시 참조할 가능성이 크다는 공간 지역성 활용 측면에서 좋습니다.
• 한 번의 디스트 헤더 움직임으로 많은 양의 데이터를 읽어오기 때문에 Disk Transfer 효율성 측면에서 좋습니다.

Segmentation

Virtual Memory1

FileSystem