기술면접 : 운영체제(2/2) , 자료구조+알고리즘(1/2)

1.세마포어와 뮤텍스의 차이에 대해 설명해보세요.

세마 포어와 뮤텍스는 동기화에 이용되는 도구이지만 차이가 있습니다.

세마포어는 여러개의 프로세스가 접근 가능한 공유자원을 관리하는 방식

뮤텍스는 한번에 한개의 프로세스만 접근 가능한 방식

세마포어는 다른 프로세스가 세마포어를 해제할 수 있지만 뮤텍스는 락을획득한 프로세스만 락을 반환 할 수 있습니다.

2.가상 메모리에 대해 설명해보세요.

가상 메모리는 어떤 프로세스가 실행될 때 메모리에 해당 프로세스 전체가 올라가지 않더라도 실행이 가능하다는 점에 착안하여 고안되었습니다. 애플리케이션이 실행될 때 실행에 필요한 일부분만 주기억장치에 올라가게 되며 나머지는

보조기억장치인 디스크에 남게 됩니다. 디스크가 RAM의 보조 기억장치 처럼 작동하는 것입니다. 

결론은 빠르고 작은 기억장치 (RAM)을 크고 느린 기억장치(디스크)와 병합하여서 하나의 크고 빠른 기억장치(가상메모리)가 됩니다.

 

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

캐시가 효율적으로 동작하기 위해서는 적중율을 극대화 시켜야하는데

그러기 위해서 지역성을 가져야합니다.

캐시의 지역성은 데이터 접근이 시간적, 혹은 공간적으로 가깝게 일어나는 것을 의미하는데

시간 지역성과 공간 지역성으로 나뉘게 됩니다.

시간지역성은 최근에 접근한 데이터에 다시 접근하는 경향이고 공간 지역성은 최근에 접근한 데이터의 주변 공간에

다시 접근하는 경향을 의미합니다.

즉 지역성은 기억장치 내의 정보를 균일하게 Access하는 것이 아니라 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성입니다.

4.프로세스 관련 용어를 설명해보세요. (알아만 둡시다.)

PCB : 프로세스 제어블록 프로세스에 대한 정보를 저장하는곳

PC : 프로그램 카운터, 프로세스 실행을 위한 다음 명령의 주소를 표시

캐시메모리 : 자주 사용되는 데이터가 저장되는 공간으로 CPU의 레지스터와 메모리 사이에서 병목 현상을 완화하는 장치 

5.배열과 링크드 리스트의 차이를 설명해주세요.

배열은 순차구조로 데이터를 저장하고 링크드 리스트는 다음 데이터의 주소값을 가르키는 포인터를 가지는 구조입니다.

배열은 순차구조로 데이터가 저장되어있기 때문에 인덱스를 사용하여 조회성능이 높고 캐시의 지역성으로 인하여 빠르게 탐색을 할 수 있습니다. 링크드 리스트는 중간에 데이터를 삽입 삭제하는것이 포인트주소만 바꿔주면 되기때문에 배열보다 더 효율적입니다.

6.List와 Set의 차이에 대해서 설명해주세요.

List와 Set은 선형자료구조이며 차이점은 

List는 순서대로 중복을허용하며 데이터를 저장할 수 있고 Set은 중복을 허용하지 않고 순서가 없이 저장됩니다.

TreeSet으로 순서를 유지하는 자료구조도 있습니다.

 

7.Hash Function, HashTable에 대해서 설명해주세요.

HashTable은 Key에 value값을 저장하는 구조입니다.

연관배열 구조라고도 합니다. key는 유니크해야되기 때문에 중복되지않고 value는 중복이 됩니다.

Key는 HashFunction를 통해서 Hash값으로 변경이 되고 Hash는 Value랑 매칭이 되어서 저장소에 저장됩니다.

해시 테이블은 이러한 구조로 키를 가지고 빠르게 Value에 접근하고 조작할 수 있는 장점이 있어서 많이 사용됩니다.

 

8.Stack, Queue에 대해서 설명해주세요.

Stack과 Queue도 마찬가지로 선형자료구조에 속하며

Stack의 특성은 후입선출 구조로 들어간 데이터의 순서대로 쌓이는 구조입니다.

제일 마지막에 들어간 데이터가 먼저 나오는특성을 가지고있습니다.

Queue의 특성은 선입선출 구조로 제일 먼저 들어간 데이터가 제일 먼저 나오는 구조를 가지고 있습니다.