1편에 이어서 작성하겠습니다.
⭐ 데드락(DeadLock) 이란?
데드락(DeadLock) 또는 교착상태란 한정된 자원을 여러 프로세스가 사용하고자 할 때 발생하는 상황으로, 프로세스가 자원을 얻기 위해 영구적으로 기다리는 상태입니다.
▶ 데드락의 4가지 조건에 대해 설명해 주세요.
1. 상호 배제(Mutual Exclusion) : 한 번에 한 프로세스만 공유 자원에 접근 가능합니다.
2. 점유 대기 (Hold & Wait) : 공유 자원에 대한 접근 권한을 가진 채로 다른 자원에 대한 접근 권한을 요구.
3. 비선점 (Nonpreemptive) : 다른 프로세스의 자원을 뺏을 수 없음.
4. 순환 대기 (Circular wait) : 두 개 이상의 프로세스가 자원 접근을 기다릴 때, 관계가 순환적 구조.
4가지 모두 성립해야 데드락 발생합니다. 하나라도 성립하지 않으면 데드락 문제 해결 가능합니다.
▶ 교착 상태 처리 방법에 대해 설명해 주세요.
1. 예방(prevention)
교착 상태 발생 조건 중 하나를 제거하면서 해결한다 (자원 낭비 엄청 심하다는 단점 존재)
- 상호배제 부정 : 여러 프로세스가 공유 자원 사용 - 불가능
- 점유대기 부정 : 프로세스 실행 전 모든 자원을 할당
- 비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
- 순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구 - 가장 현실적
2. 회피(avoidance)
은행원 알고리즘(Banker's Algorithm)
- 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
- 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
- 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기
3. 탐지 & 회복
교착 상태가 되도록 허용한 다음 회복시키는 방법
- 탐지(Detection)
자원 할당 그래프를 통해 교착 상태를 탐지함
- 회복(Recovery)
교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법
프로세스 종료 방법
- 교착 상태의 프로세스를 모두 중지
- 교착 상태가 제거될 때까지 하나씩 프로세스 중지
자원 선점 방법
- 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당 (해당 프로세스 일시정지 시킴)
- 우선순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점
▶기아상태를 설명하는 식사하는 철학자 문제에 대해 설명해 주세요.
▶ 회피 기법인 은행원 알고리즘을 설명해 주세요.
은행원 알고리즘은 운영체제가 안전상태를 유지할 수 있는 요구만을 수락하고 불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있을 때까지 계속 거절하는 알고리즘입니다.
안전상태(safe state) :
시스템이 교착상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼
필요한 자원을 할당해 줄 수 있는 상태로 안전순서열이 존재하는 상태입니다.
😎 경쟁 상태(Race Condition)
공유 자원에 대해 여러 프로세스가 동시에 접근할 때, 결괏값에 영향을 줄 수 있는 상태로
동시 접근 시 자료의 일관성을 해치는 결과가 나타남
▶Race Condition이 발생하는 경우는 어떤 경우일까요?
1. 커널 작업을 수행하는 중에 인터럽트 발생
- 문제점 : 커널모드에서 데이터를 로드하여 작업을 수행하다가 인터럽트가 발생하여 같은 데이터를 조작하는 경우
- 해결법 : 커널모드에서 작업을 수행하는 동안, 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 한다.
2. 프로세스가 'System Call'을 하여 커널 모드로 진입하여 작업을 수행하는 도중 문맥 교환이 발생할 때
- 문제점 : 프로세스 1이 커널모드에서 데이터를 조작하는 도중, 시간이 초과되어 CPU 제어권이 프로세스 2로 넘어가 같은 데이터를 조작하는 경우 ( 프로세스 2가 작업에 반영되지 않음 )
- 해결법 : 프로세스가 커널모드에서 작업을 하는 경우 시간이 초과되어도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 함
3. 멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근할 때
- 문제점 : 멀티 프로세서 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우
- 해결법 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 방법
😎 Critical Section(임계영역)에 대해 설명해 주세요.
동일한 자원을 동시에 접근하는 작업을 실행하는 코드 영역을 Critical Section이라 합니다.
임계 영역 문제를 해결하기 위해서는 아래의 3가지 조건을 충족해야 합니다.
- 상호 배제(Mutual exclution) - 하나의 프로세스가 임계 영역에 들어가 있다면 다른 프로세스는 들어갈 수 없어야 한다.
- 진행(Progress) - 임계 영역에 들어간 프로세스가 없는 상태에서 들어가려 하는 프로세스가 여러 개라면 어느 것이 들어갈지 결정해주어야 한다.
- 한정 대기(Bounded waiting) - 다른 프로세스의 기아를 방지하기 위해, 한 번 임계 구역에 들어간 프로세스는 다음번 임계 영역에 들어갈 때 제한을 두어야 한다.
😎 프로세스 동기화 해결책 : 세마포어(Semaphore) vs 뮤텍스(Mutex) 차이
뮤텍스
- Lock을 사용해 하나의 프로세스나 스레드를 단독으로 실행하게 합니다.
- Critical Section에 진입하는 프로세스는 Lock을 획득하고 Critical Section 을 빠져나올 때, Lock 을 방출함으로써 동시에 접근이 되지 않도록 한다.
- 락(lock)을 획득한 프로세스가 반드시 그 락을 해제해야 합니다.
- 단점 : 다중처리기 환경에서는 시간적인 효율성 측면에서 적용할 수 없다.
세마포어
- 공유자원에 세마포어 변수만큼의 프로세스(또는 스레드)가 접근할 수 있습니다.
- 현재 수행 중인 프로세스가 아닌 다른 프로세스가 세마포어를 해제할 수 있습니다.
- 0과 1의 값만 갖는 세마포어 → 이진 세마포어(binary semaphore) (= 뮤텍스)
😎 콘보이 현상(convoy effect)이란 무엇이고, 콘보이 현상이 발생될 수 있는 CPU 스케줄러 알고리즘은 무엇인지 설명해 주세요.
콘보이 현상이란 작업 시간이 긴 프로세스가 먼저 큐에 도착해서 다른 프로세스의 실행 시간이 전부 늦춰져 효율성을 떨어뜨리는 현상을 말합니다.
FCFS(First-Come First Served) 스케줄링은 비선점형으로, 순차적으로 먼저 큐에 들어온 작업부터 실행하므로 콘보이 현상이 발생할 수 있습니다.
😎 선점형 스케줄링과 비선점형 스케줄링의 차이를 설명해 주세요.
선점형은 하나의 프로세스가 다른 프로세스 대신에 CPU를 차지할 수 있음을 말하고,
비선점형은 하나의 프로세스가 끝나지 않으면 다른 프로세스는 CPU를 사용할 수 없음을 말합니다.
😎 CPU 스케줄링
1. 스케줄링
CPU를 잘 사용하기 위해 프로세스를 잘 배정하는 것을 말합니다.
- 목표
- Batch System: 가능하면 많은 일을 수행. 시간(time) 보단 처리량(throughout)이 중요
- Interactive System: 빠른 응답 시간. 적은 대기 시간.
- Real-time System: 기한(deadline) 맞추기
2. 프로세스 상태 전이
✓ 승인 (Admitted) : 프로세스 생성이 가능하여 승인됨.
✓ 스케줄러 디스패치 (Scheduler Dispatch) : 준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것.
✓ 인터럽트 (Interrupt) : 예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리하는 것.
✓ 입출력 또는 이벤트 대기 (I/O or Event wait) : 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때까지 대기 상태로 만드는 것.
✓ 입출력 또는 이벤트 완료 (I/O or Event Completion) : 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것
3. CPU 스케줄링의 종류
스케줄링 대상은 Ready Queue* 에 있는 프로세스들이다.
* Ready Queue : 현재 메모리 내에 있으면서 CPU 를 잡아서 실행되기를 기다리는 프로세스의 집합
비선점 스케줄링
- FCFS 선입 선처리 스케줄링(First Come First Served)
- 큐에 도착한 순서대로 CPU 할당
- 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐
- SJF 최단 작업 우선 스케줄링 (Shortest Job First)
- 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
- FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리
선점 스케줄링
- Priority Scheduling 우선순위 스케줄링
- 우선순위를 부여하여 우선순위가 높은 순서대로 처리
- 우선순위가 낮은 프로세스가 무한정 기다리는 Starvation 기아현상 이 생길 수 있음
- Aging 방법으로 Starvation 문제 해결 가능
- SRTF(Shortest Remaining Time First) 최소 잔여 시간 우선 스케줄링
- Round Robin 라운드 로빈 스케줄링
- FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum 만큼 CPU를 한 달 받음
- Time Quantum or Time Slice : 실행의 최소 단위 시간
- 할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 작으면 문맥 교환 (Context Switching) 잦아져서 오버헤드 증가
- FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum 만큼 CPU를 한 달 받음
- Multilevel-Queue 다단계 큐 스케줄링
- 작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 기법
- 우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 Time Quantum을 설정해주는 방식 사용
- 우선순위가 높은 큐는 작은 Time Quantum 할당. 우선순위가 낮은 큐는 큰 Time Quantum 할당.
- Multilevel-Feedback-Queue 다단계 피드백 큐 스케줄링
- 다단계 큐에서 자신의 Time Quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 그대로
- Time Quantum을 다 채운 프로세스는 CPU burst 프로세스로 판단하기 때문
- 짧은 작업에 유리, 입출력 위주(Interrupt가 잦은) 작업에 우선권을 줌
- 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 Turnaround 평균 시간을 줄여줌
- 다단계 큐에서 자신의 Time Quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 그대로
4. CPU 스케줄링 척도
- Response Time
- 작업이 처음 실행되기까지 걸린 시간
- Turnaround Time
- 실행 시간과 대기 시간을 모두 합한 시간으로 작업이 완료될 때까지 걸린 시간
출처:
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS
'기술 면접 준비' 카테고리의 다른 글
| [기술면접] 자료구조 - 2/2 (1) | 2023.05.16 |
|---|---|
| [기술면접] 자료구조 - 1/2 (2) | 2023.05.16 |
| [기술면접] 운영체제 - 1/2 (0) | 2023.04.04 |
| [운영체제] 교착 상태(데드락, Deadlock) - 5/5 (0) | 2023.04.03 |
| [운영체제] 프로세스와 스레드의 동기화 - 4/5 (0) | 2023.04.03 |