Job Interview

Operating system

1. 프로세스와 스레드의 차이(Process vs Thread)

프로세스

프로세스는 컴퓨터에서 실행되고 있는 프로그램을 말합니다. 프로그래밍 언어로 제작되어 정적인 상태로 HDD 또는 SSD에 저장된 프로그램을 실행하면 운영체제로부터 주소공간, 파일, 메모리 등을 할당받으며 이것들을 총칭하여 프로세스라고 합니다.

프로세스는 실행할 프로그램의 코드를 읽어오는 코드 영역, 전역 변수들을 수록하는 데이터 영역, 함수의 매개변수, 로컬 변수와 복귀주소와 같은 임시 자료를 저장하는 stack 영역, 프로세스 실행중에 동적으로 할당되는 메모리인 heap 영역을 가지고 있습니다.

프로세스 제어 블록(Process Control Block, PCB)

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

PCB에 저장되는 정보는 다음과 같습니다.

프로세스 식별자(Process ID, PID): 프로세스 식별번호
프로세스 상태: new or Create, ready, running, waiting, terminated 등의 상태를 저장
프로그램 카운터(PC) : 프로세스가 다음에 실행할 명령어의 주소
CPU 레지스터
CPU 스케줄링 정보: 프로세스의 우선순위, 스케줄 큐에 대한 포인터 등
메모리 관리 정보: 페이지 테이블 또는 세그먼트 테이블 등과 같은 정보를 포함
입출력 상태 정보: 프로세스에 할당된 입출력 장치들과 열린 파일목록
accounting 정보: 사용된 CPU 시간, 시간제한, 계정번호 등

스레드(Thread)

스레드는 한 프로세스 내에서 실행되는 여러 실행 흐름의 단위라고 할 수 있습니다. 하나의 프로세스를 다수의 실행 단위로 구분하여 자원을 공유하고 자원의 생성과 관리의 중복성을 최소화하여 수행 능력을 향상시키는 것을 멀티스레딩이라 합니다. 한 프로세스 안에서 코드 영역, 데이터 영역, 힙영역을 공유하고 있지만 스레드 ID, 프로그램 카운터, 레지스터 집합 그리고 스택 영역은 별도로 할당받습니다.

스택을 독립적으로 할당하는 이유
스택 메모리 공간을 독립적으로 할당하여, 각 스레드마다 독립적인 함수호출을 가능하게 하여, 실행 흐름의 독립성을 유지할 수 있게 합니다.

PC 레지스터를 스레드마다 독립적으로 할당하는 이유
PC 레지스터는 스레드가 다음에 실행할 명령어의 주소를 저장하며, 스레드도 CPU를 할당받고, 스케줄러에 의해 다시 선점당하기 때문에 각 스레드마다 PC 레지스터는 독립적으로 할당되어야 합니다.

2. 멀티 프로세스 대신 멀티 스레드를 사용하는 이유

멀티 스레드의 장점

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

멀티 스레드의 단점

멀티 스레딩을 구현하는 경우, 서로 다른 스레드가 데이터와 힙 영역을 공유하기 때문에 어떤 스레드가 다른 스레드에서 사용중인 변수나 자료구조에 접근하여 엉뚱한 값을 읽어오거나 수정할 수 있습니다. 그렇기에 동기화 작업을 통헤 작업 처리 순서, 공유 자원에 대한 접근을 관리해야 합니다. 하지만 이로 인해 병목현상이 발생하여 성능이 저하될 가능성이 높습니다. 따라서 threadpool을 제한하여 과한 멀티스레딩 작업은 피해야 합니다.

멀티 스레드 vs 멀티 프로세스

멀티 스레드는 멀티 프로세스보다 적은 메모리 공간을 차지하고 context switching이 빠르다는 장점이 있지만, 오류로 인해 하나의 스레드가 종료되면 전체 스레드가 종료될 수 있다는 점과 동기화 작업의 필요를 단점으로 가지고 있습니다. 반면 멀티 프로세스 방식은 하나의 프로세스가 죽더라도 다른 프로세스에는 영향을 끼치지 않고 정상적으로 수행된다는 장점이 있지만, 멀티 스레드보다 많은 메모리 공간과 CPU시간을 차지한다는 단점을 가지고 있습니다. 이 두가지 방법 모두 여러 작업의 병렬처리를 가능케하지만, 각자의 장단점을 가지고 있습니다. 적용해야 하는 시스템에 따라 적합한 동작 방식을 선택하여 적용해야 합니다.

3. Context Switching이 무엇인지 설명하고 과정을 나열해주세요

context switching은 CPU를 할당받아 작업중인 프로세스로부터 다른 프로세스로 CPU의 제어권을 이양되는 과정을 말합니다. 작업중인 process1이 실행되다 interrupt가 발생하면, process1을 대기 상태또는 중지상태로 전환합니다. precess 1의 상태를 process1의 PCB에 저장하고, 다음으로 실행할 프로세스로 process2를 선택합니다. precess 2의 PCB에서 process2의 정보를 불러와 프로세서에 저장하여 process2를 실행합니다.

우선순위가 높은 프로세스를 먼저 처리할 수 있어 효율이 좋지만 Context switching이 빈번하게 일어나면 비효율이 발생합니다.

4. 사용자 수준 스레드와 커널 수준 스레드의 차이 설명

사용자 수준 스레드

사용자 수준 스레드는 사용자 영역의 스레드 라이브러리로 구현하고, 스레드와 관련된 모든 행위를 사용자영역에서 하므로 커널이 스레드의 존재를 알지 못합니다. 여기서 스레드 라이브러리는 스레드의 생성과 종료, 스레드 간의 통신, 스레드의 스케줄링과 context 등 정보를 보관합니다. 사용자 수준 스레드에서는 스레드 전환이 발생할 때, 커널이 개입하지 않아 커널에서 사용자 영역으로 전환하지 않습니다. 그리고 커널은 스레드가 아닌 프로세스를 한 단위로 인식하고 프로세서를 할당합니다. 다수의 사용자 수준 스레드가 커널 수준 스레드 한개에 매핑되므로 다대일 스레드 매핑이라고도 합니다.

사용자 수준 스레드의 장점

커널에 독립적으로 스케줄링을 할 수 있어 모든 OS에 적용할 수 있습니다. 스케줄링이나 동기화를 하려고 커널을 호출하지 않으므로 커널 영역으로 전환하는 과정이 생략됩니다. 커널이 아닌 스레드 라이브러리에서 스레드 스케줄링을 제어하므로 응용 프로그램에 맞게 스케줄링할 수 있습니다.

사용자 수준 스레드의 단점

프로세스 단위로 프로세서를 할당하여 다중 처리 환경을 갖춰도 스레드 단위로 다중 처리를 하지 못합니다. 동일한 프로세스의 스레드 한개가 대기 상태가 되면 이 중 어떤 쓰레드도 실행하지 못합니다. 커널이 한 프로세스에 속한 여러 쓰레드에 프로세서를 동시에 할당할 수 없어 다중 처리 시스템에서 규모를 확장하기가 어렵습니다. 스레드간 보호에 커널의 보호 방법을 사용할 수 없습니다. 스레드 라이브러리에서 스레 간 보호를 제공해야 프로세스 수준에서 보호가 가능합니다.

커널 수준 스레드

커널 수준 스레드는 사용자 수준 스레드의 한계를 극복하는 방법으로 커널이 스레드와 관련된 모든 작업을 관리합니다. 한 프로세스에서 다수의 스레드가 프로세서를 할당받아 병행으로 수행하고, 스레드 한 개가 대기 상태가 되면 동일한 프로세스에 속한 다른 쓰레드로 교환이 가능합니다. 이 때 커널이 개입하므로 사용자 영역에서 커널 영역으로 전환이 필요합니다. 커널 수준 스레드는 사용자 수준 스레드와 일대일로 매핑됩니다. 따라서 사용자 수준 스레드를 생성하면 이에 대응하는 커널 스레드를 자동 생성합니다.
커널 수준 스레드는 커널이 직접 스케줄링하고 실행하기에 사용자 수준 스레드의 커널 자원이 부족한 문제를 해결할 수 있지만, 커널이 전체 프로세스와 스레드 정보를 유지하여 리소스 소모가 커집니다. 대신 커널이 각 스레드를 개별적으로 관리할 수 있어 동일한 프로세스의 스레드들을 병렬처리할 수 있습니다.

5. 스케줄러에 대해 설명하고, 단기/중기/장기로 나눠지는 기준에 대해 설명해주세요.

스케줄러(scheduler)

스케줄링이란 프로세스가 생성되어 실행될 때, 필요한 CPU 또는 다른 시스템 자원을 효율적으로 여러 프로세스에게 할당하는 작업을 말합니다. 스케줄링을 하는 프로그램을 ‘스케줄러’라고 하며, 다양한 방법의 알고리즘으로 구현이 되어있습니다.

프로세스를 스케줄링하는 Queue에는 아래와 같은 3가지 종류가 있습니다.

Job Queue: 현재 시스템 내에 있는 모든 프로세스의 집합
Ready Queue: 현재 메모리 내에 있으면서 CPU를 할당받아 실행하기를 기다리는 프로세스의 집합
Device I/O Queue: Device I/O 작업을 대기하고 있는 프로세스의 집합

장기 스케줄러(long-term scheduler or job scheduler)

메모리는 한정되어 있는데 많은 Job이 한꺼번에 메모리로 올라온 경우, 대용량 메모리(디스크, pool)에 임시로 저장되고 이 중 어떤 job에게 먼저 메모리를 할당하여 Ready Queue로 보낼지 결정하는 역할을 한다.
정리하자면,

메모리와 디스크 사이의 스케줄링 담당
프로세스에 Memory 및 각종 리소스를 할당
실행중인 프로세스의 개수 제어
프로세스의 상태 New -> Ready

최근에는 가상메모리를 통한 OS의 서비스로 모든 job에 메모리가 할당되어 장기 스케줄러의 의미가 퇴색되었습니다.

단기 스케줄러(short-term scheduler or CPU scheduler)

Ready Queue에 담겨 있는 프로세스가 실행되기 위해서는 CPU를 할당받아야 하는데, 이 작업을 하는 스케줄러를 CPU scheduler 또는 단기 스케줄러라 합니다. Context switching도 단기 스케줄러에 의해 관리됩니다.

CPU와 메모리 사이의 스케줄링 담당
Ready Queue에 존재하는 프로세스 중 어떤 프로세스를 Running 상태로 전환할 지 결정
프로세스에 CPU 할당(CPU dispatch)
프로세스의 상태 Ready -> Running -> Waiting -> Ready

중기 스케줄러(medium-term scheduler of Swapper)

CPU의 과부하를 방지하기 위해 메모리의 여유공간을 확보하는 작업을 담당합니다.

여유공간을 위해 Ready Queue에 존재하는 프로세스 중 일시적으로 보류를 시킬 프로세스를 디스크로 swapping 진행
프로세스에게서 메모리를 deallocate
실행중인 프로세스의 개수 제어
프로세스의 상태 Ready -> Suspended

** Suspended : 외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태를 말합니다. 프로세스 전부 disk로 swap out Blocked 상태와 비교하자면, Blocked는 다른 I/O 작업을 기다리는 상태이므로 스스로 Ready state로 복귀할 수 있지만 Suspended의 경우 외부적인 이유로 정지가 되었기 때문에 스스로 복귀할 수 없습니다.

6. CPU 스케줄러인 FCFS, SJF, SRTF, Priority Scheduling, RR에 대해 간략히 설명해주세요.

FCFS(First Come First Served)

가장 먼저 도착한 요청을 가장 먼저 처리하는 기본적인 디스크 스케줄링 기법입니다. 개발이 용이하며 공평하고 무기한 대기가 없습니다. 하지만 최적의 방법은 아니며, 앞선 프로세스의 실행시간이 길어지면 뒤의 짧은 프로세스 또한 실행되지 못하고 줄줄이 따라가는 형태의 convoy effect가 발생합니다. 비선점(Non-preemptive)스케줄링 기법 중 하나입니다.

SJF(Shortest Job First)

실행시간이 가장 짧은 프로세스 먼저 처리하는 기법입니다. 평균 대기 시간이 가장 짧으며 최적의 결과를 도출합니다. 하지만 프로세스를 실행하기 전에 소요 시간을 안다는 것이 몹시 비현실적인 스케줄링 기법이며, 이를 해결하고자 과거 실행시간을 기록하여 예측에 사용하지만 더 많은 오버헤드를 발생시킵니다. 비선점 스케줄링 기법 중 하나입니다.

SRTF (Shortest Remaining Time First)

SJF 기법을 개량한 SJTF는 선점 스케줄링 기법 중 하나입니다. 프로세스가 작업을 하다 다른 프로세스가 도착하면 현재 작업중인 프로세스의 남은 시간과 도착한 프로세스의 실행시간을 비교해 도착한 프로세스의 시간이 짧다면 선점하여 먼저 실행하는 기법입니다. 작업하다가 CPU를 반환한 프로세스는 남은 시간을 기록합니다. 또 다른 프로세스가 도착을 하면 역시나 남은 시간이 가장 짧은 프로세스가 먼저 CPU를 선점 할당받아 실행됩니다. 단점으로는 실행시간이 긴 프로세스의 경우 항상 양보하게 되어 Starvation상태에 빠지게 되며, SJF와 마찬가지로 CPU 필요시간에 대하 정확한 정보를 알 수 없다는 점이 있습니다.

Priority Scheduling

우선순위가 높은 프로세스가 먼저 CPU를 할당받아 실행하는 기법으로, 현재 작업중인 프로세스를 밀어내는 선점형, Ready Queue의 Head에서 기다리는 비선점형으로 나눌 수 있습니다. 우선순위란 정수값으로 표현되며, 일반적으로 낮은 숫자가 높은 우선순위를 의미합니다. 우선순위는 내부적인 요인(수행시간, 메모리/IO/CPU 소비량)와 외부 요인(높은 등급의 사용자 프로세스)에 의해 결정됩니다. 역시나 우선순위가 높은 프로세스가 지속적으로 Queue에 삽입되어 우선순위가 낮은 프로세스가 오래 기다리는 starvation문제로 무한정 정지상태가 될 수 있습니다. 이를 해결하기 위해 Aging 기법이 있으며 우선순위가 낮더라도 대기 시간이 길어지면 우선순위를 조금씩 높여주는 방법입니다.

RR(Round Robin)

시분할 시스템을 위해 설계된 선점형 스케줄링 기법으로, 가장 현실적인 방법입니다. 일정한 시간단위(Time Quantum)마다 CPU를 할당하는 방법으로, 실행되다 CPU를 뺏기면 Ready Queue의 제일 마지막으로 삽입되어 다시 기다립니다. RR은 CPU사용시간이 랜덤한 프로세스들이 섞여 있을 때 효율적으로 작동하며, RR이 가능한 이유는 프로세스의 context를 기록할 수 있기 때문입니다. 주의할 점으로는 시간단위를 어떻게 설정하느냐인데, 너무 길어지면 FCFS와 같아지고, 너무 짧으면 잦은 context switch로 큰 오버헤드가 발생하여 비효율적입니다. 따라서 적당한 Time Quantum이 필요합니다.

7. 동기와 비동기의 차이를 설명해주세요.

동기(Synchronous)

동기적 시스템은 작업 요청을 보낸 후 응답(결과값)을 반환받아야 다음 동작으로 넘어갑니다. 어떠한 일을 처리할 때, 그 일에만 집중하여 처리되는 동안 다른 작업을 정지합니다. 시스템의 비효율화를 초래할 수 있으나, 작업을 주고받는 A node와 B node 사이 작업 트랙잭션을 맞춘다(동기화)라는 장점이 있습니다.

비동기(Asynchronous)

비동기적 서비스는 작업 요청을 보낸 후 응답(결과값)과는 상관없이 다음 작업이 작동합니다. 결과가 주어지는 데 걸리는 시간동안 다른 작업을 할 수 있어 효율적입니다. 작업요청을 받으면 함수는 요청에 대한 확인 동작으로 응답을 하고, 요청에 대한 연산은 별도로 하며, 연산에 대한 결과값을 반환할 때, callback함수로 전달하며 이는 사용자가 아닌 작업을 마친 시스템이 호출하는 형태입니다. 요청에 대한 확인 동작으로 이미 응답을 하였기에, 함수 호출 형태로 전달합니다.

8. Thread-safe에 대해 설명해주세요. (hint: critical section)

Thread-safe는 멀티 스레드 프로그래밍에서 일반적으로 어떤 함수나 변수, 혹은 객체가 여러 스레드로부터 동시에 접근이 이루어져도 프로그램의 실행결과에 문제가 없음을 의미합니다. thread-safe를 달성하기 위해 다음과 같은 방법이 있습니다.

Re-entrancy : 동시에 접근해도 올바른 결과를 주어야함
Thread local storage 사용
Mutual Exclusion : 자원을 세마포어/ 뮤택스로 동시 접근을 막는다.
atomic operations : 원자 연산을 이용하여 공유 자원에 접근한다.

또한 한번에 하나의 Thread에게만 접근을 허용하고 싶어하는 critical section을 먼저 접근한 스레드가 먼저 접근 lock을 걸어 다른 스레드가 동시에 접근 못하도록 관리합니다.

**Critical Section(임계영역) 동시 접근이 가능한 공유 자원이 있는 코드 영역으로, 문제가 생기지 않도록 공유 자원의 독점을 보장하는 코드 영역입니다.

9. 뮤텍스와 세마포어의 차이를 설명해주세요

뮤택스(Mutex)

Critical Section을 가진 스레드들의 공유자원 동시접근을 막기 위한 상호배제(Mutual Exclusion)하는 기법입니다. 현재 작업중인 스레드에게 key를 소유하게 하여 공유자원에 접근하며, 접근을 끝내면 key를 방출하는 일종의 Locking 매커니즘입니다.

세마포어(Semaphore)

Signaling 매커니즘으로 현재 공유자원에 접근할 수 있는 스레드, 프로세스의 수를 나타내는 값을 두어 상호배제를 달성합니다. 접근가능한 리소스 상태를 나타내는 counter로 1이상 값을 기록하고 있으면 접근이 가능합니다.

뮤택스와 세마포어의 차이

먼저 세마포어는 뮤택스로 대체될 수 있어도(이진 세마포어), 뮤택스는 세마포어로 대체할 수 없습니다. 또한 뮤택스의 경우 뮤택스를 소유한 스레드만이 작업을 끝내고 해제할 수 있지만 세마포어의 경우 세마포어를 소유하지 않은 프로세스가 해제할 수 있습니다. 그리고 세마포어는 시스템 범위에 걸쳐있어, 파일 형태로 존재하는 반면, 뮤택스는 프로세스 내 범위를 가지며 프로세스가 종료될 때, 자동으로 Clean up됩니다.

10. 교착상태(데드락, Deadlock)의 개념과 조건을 설명해주세요.

교착상태는 시스템 자원의 요구가 뒤엉킨 상태입니다. 예를 들어 process1이 자원1를 점유하고 있고 자원2를 필요로 할 때, process2는 자원2를 점유하고 있고 자원1을 필요로 하여 서로를 무한정 기다리고 있는 상태가 바로 교착상태입니다.

다음 같은 조건을 충족하고 있을 때 교착상태에 빠지게 됩니다.

상호배제(Mutual Exclusion): critical section의 자원을 한번에 한 프로세스만 사용할 수 있다.
점유와 대기(Hold and Wait): 자원을 최소한 하나 이상을 점유하고 있고, 다른 프로세스에게 할당된 자원을 점유하기 위해 대기하고 있는 상태이다.
선점 불가(No-preemption): 자원을 획득함에 있어 우선권이 없어 다른 프로세스의 자원을 강제적으로 뺏어올 수가 없다.
순환 대기(Circular wait): 예시에서 범위를 넓혀 process1은 자원1을 소유하고 있고, 자원2를 필요로합니다. process2는 자원2를 소유하고 있고, 자원3을 필요로 합니다. process3은 자원3을 소유하고 있고, 자원1을 필요로 합니다. 이처럼 순환구조를 이루어 무한정 대기를 하는 상태이다.

11. 메모리 관리 전략에는 무엇이 있는지 간략히 설명해주세요.

12. Paging과 Swapping에 대해 설명해주세요.

13. 가상 메모리에 대해 설명해주세요.

14. 외부 단편화와 내부 단편화에 대해 설명해주세요.

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

Reference

지식을 공유해주신 분들께 감사드립니다.

https://github.com/boostcamp-ai-tech-4/ai-tech-interview#%EF%B8%8F-operating-system

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS#part-1-4-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C

https://coding-start.tistory.com/199
https://patrickryoo.tistory.com/52