BP면접 복기

박성민·2021년 3월 31일

면접 준비

목록 보기

5/6

DeadLock에 대해 아는데로 설명해보세요

Dead Lock

프로세스가 자원을 얻지 못해서 다음 처리를 하지 못하는 교착 상태. 시스템적으로 한정된 자원을 여러곳에서 사용하려고 할 때 발생합니다.

Dead Lock이 발생하는 경우

멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황
한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생하면서 프로세스가 대기 상태로 들어갈 때

대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때

Dead Lock의 발생조건

상호 배제(Mutual Exclusion): 자원은 한 번에 한 프로세스만 사용할 수 있다.
점유 대기(Hold and Wait): 최소 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 있고, 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 함.
비선점(No Preemption): 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다.
순환 대기(Circular Wait): 프로세스의 집합에서 순환 형태로 자원을 대기하고 있음.

Dead Lock 처리 방법

예방(prevention)

Dead Lock이 발생하는 4가지 조건 중 하나라도 만족되지 않도록 함
-> 교착상태 발생조건 중 하나를 제거한다

상호배제 부정 : 여러 프로세스가 공유 자원 사용
점유대기 부정 : 프로세스 실행전 모든 자원을 할당
비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구

회피(avoidence)

은행원 알고리즘(Banker's Algorithm)
프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피한다. 안정 상태면 자원 할당을 하고, 아니면 다른 프로세스들이 자원 해지까지 대기한다.

회복(Recovery)

교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시킨다.

프로세스 종료 방법
교착 상태의 프로세스를 모두 중지한다.
교착 상태가 제거될 때까지 하나씩 프로세스를 중지한다.
자원 선점 방법
교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당한다. 해당 프로세스 일시정지
우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원을 선점한다.
무시
회복 과정의 성능 저하가 더 심하면 그냥 무시한다.

자주쓰는 자료구조가 뭔가요?

array와 map의 차이점은? 각각 언제 쓰나요?

Array

가장 기본적인 자료구조인 Array 자료구조는, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스(index)로 해당 원소(element)에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다. 즉 random access 가 가능하다는 장점이 있다.

Map

Map은 key와 value를 가진 집합이며, 중복을 허용하지 않습니다. 즉, 한개의 key에 한개의 value가 매칭된다.

map과 hashmap의 차이는?

둘의 가장 큰 차이는 특정 키에 대한 값을 찾는 과정에서, hash_map은 이름 그대로 hash table을 이용해서 키-값 관계를 유지하며, map은 red-black tree 알고리즘을 이용합니다.

hash_map은 이상적으로 O(1)의 시간을 소요하지만, 실제로는 hash table의 크기에 반비례하는 O(n)의 시간을 소요합니다. 큰 문제점이 없다면, hash table의 크기는 저장되는 key-value pair의 20% 정도 되어도 충분히 쓸만합니다. 그리고 hash table은 key 값을 hashing을 해야 하기 때문에,특정한 객체를 key로 쓸 경우 별도의 적절한 hash 생성 함수를 만들어야 합니다. 그리고, 삽입, 제거의 과정이 가볍습니다.
내부 hash 값에 따라서 키순서가 정해지므로 특정 규칙없이 출력됩니다.
map을 쓰는 경우, 최악 O(n), 최상 O(logn)의 성능을 냅니다. 그러나 red black tree의 특성상 node rotation을 하는 과정에서 최악 log2n개의 노드의 값을 업데이트하는 부하가 있습니다. (사실 그다지 크지도 않습니다.) red black tree는 key ordered tree이기 때문에, key값이 특정 구조체인 경우 key 값의 비교 함수나 비교 연산자(operator<)가 만들어져 있어야 합니다.
경험상, map보다 hash_map이 더 좋은 성능을 내게 하려면, 우선 key 값 비교 연산이 큰 경우(예컨대 키값이 덩치 큰 객체인 경우)에 효과적이며, 이러한 경우 log2n보다 짧을 수 있는 비교 횟수가 나올 수 있도록 충분한 hash table 크기를 설정하는 것입니다. (보통 키 갯수의 70%정도입니다.)

git에서 주로 쓰던 명령어들은 뭐가 있었나요?

git init : git 생성하기
git clone git_path : 코드가져오기
git checkout branch_name : 브랜치 선택하기
git checkout -t remote_path/branch_name : 원격 브랜치 선택하기
git branch branch_name : 브랜치 생성하기
git branch -r : 원격 브랜치 목록보기
git branch -a : 로컬 브랜치 목록보기
git branch -m branch_name change_branch_name : 브랜치 이름 바꾸기
git branch -d branch_name : 브랜치 삭제하기
git push remote_name — delete branch_name : 원격 브랜치 삭제하기 ( git push origin — -delete gh-pages )
git add file_path : 수정한 코드 선택하기 ( git add * )
git commit -m “commit_description” : 선택한 코드 설명 적기 ( git commit -m “내용”)
git push romote_name branch_name : add하고 commit한 코드 git server에 보내기 (git push origin master)
git pull : git서버에서 최신 코드 받아와 merge 하기
git fetch : git서버에서 최신 코드 받아오기
git reset — hard HEAD^ : commit한 이전 코드 취소하기
git reset — soft HEAD^ : 코드는 살리고 commit만 취소하기
git reset — merge : merge 취소하기
git reset — hard HEAD && git pull : git 코드 강제로 모두 받아오기
git config — global user.name “user_name ” : git 계정Name 변경하기
git config — global user.email “user_email” : git 계정Mail변경하기
git stash / git stash save “description” : 작업코드 임시저장하고 브랜치 바꾸기
git stash pop : 마지막으로 임시저장한 작업코드 가져오기

출처 및 참고

박성민

iOS시작~

이전 포스트

면접준비 - 3

다음 포스트