운영체제

Q. 메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.

• CPU 레지스터: CPU에서 임의에 변수를 담는 장소로 주기억장치에 데이터를 가져와 레지스터에 저장한다.

• CPU 캐시(L1, L2, ~): 주기억장치에서 데이터를 가져와 레지스터에 담을 때, 지역성이론에 따라 자주 사용되는 데이터를 캐시에 저장한다.

• 주기억장치(RAM): 주기억장치라고 불리우는 RAM은 어떠한 주소로 데이터를 가져와도 동일한 성능으로 데이터를 가져올 수 있다. 프로세스와 운영체제가 주기억장치에 올라와 실행되는 공간이다. RAM의 또다른 특성은 전원이 공급되지 않으면 데이터가 지워지는 휘발성 메모리이다.

• 보조기억장치: 휘발성 메모리인 RAM은 데이터를 저장하기 보다는 실행되는 데이터를 저장하는데 유용하다. 때문에 작업중인 파일이나 프로그램의 데이터를 보조기억장치에 저장하여 필요할 때 RAM에 올려 사용한다.

Q. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?

경계 레지스터: MMU가 경계 레지스터에 침범하려고 하는 프로세스를 강제 종료시킨다.

Q. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?

• 가변 분할 방식(세그멘테이션): 세그멘테이션은 프로세스의 크기에 맞게 적절한 메모리 크기를 할당하여 불필요한 내부 단편화로 낭비되는 메모리 영역이 없다. 또한, 프로세스 크기에 맞는 메모리 영역을 할당하기 때문에 프로세스 영역별로 권한 등의 관리가 쉽다. 단, 외부 단편화 문제가 있는데, 예를 들어, 프로세스 A가 종료되어 메모리 영역에 구멍이 생길 경우, 새롭게 실행될 프로세스 B가 프로세스 A보다 큰 메모리를 요구한다면 구멍난 메모리 영역에 할당할 수 없게 된다. 이를 외부 단편화 문제라고 부르며 외부 단편화 문제를 해결하기 위해서는 메모리 조각 모음을 실행해야 한다. 하지만, 메모리 조각 모음은 실행중인 프로세스들을 종료하고 구멍난 메모리 영역을 매꿔야하기 때문에 오버헤드가 발생한다.

• 고정 분할 방식(페이징): 페이징은 세그멘테이션과 다르게 고정된 메모리 크기를 분할하여 프로세스들에게 할당하는 방식이다. 때문에 고정된 크기보다 작은 프로세스를 실행하려 한다면 메모리 낭비가 발생하게 되는데 이를 내부 단편화라 부른다. 하지만, 항상 고정된 크기의 메모리를 분할하여 프로세스에게 할당하여 세그멘테이션의 외부 단편화 문제가 없다.

Q. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?

• 정답: 스레싱, 이를 해결하기 위해 지역성이론에 따라 다시 현재 사용중인 페이지들은 다시 사용될 확률이 높다. 이러한 페이지를 하나로 묶어 메모리에 올리는데 이를 워킹셋이라고 부른다.

Q. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? (이유를 함께 적어주세요.)

HDD나 SSD와 같은 보조기억장치가 필요한 이유는 다음과 같다.

1. CPU 레지스터나 캐시, 주기억장치는 휘발성 메모리이다. 때문에 작업했던 문서나 프로그램의 데이터 등 유지시킬 필요가 있는 상태들은 전원 공급 없이도 보조기억장치를 통해 상태를 저장해야 한다.

2. 또한, 메모리는 가격이 매우 비싸기 때문에, 메모리보다 저렴한 보조기억장치에 문서나 데이터를 저장하고 프로그램이 실행될 때 프로세스로 메모리에 올리는 방식이 효율적이다.

3. 보조기억장치에는 운영체제 프로그램을 담고 있다. 컴퓨터가 실행하면 보조기억장치에 있는 운영체제를 메모리에 올려 프로세스로 실행하게 된다.

Q. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?

이는 파일을 삭제할 때 파일의 헤더만 삭제하기 때문이다. 때문에 사용했던 블록의 데이터는 그대로 남아있어 포렌식을 통해 데이터를 복구할 수 있게 된다.

파일을 삭제할 때 헤더만을 삭제하여 Free Block List에 추가한다. 그리고 해당 블록은 "사용 가능" 상태로 두어, 새로운 파일을 작성할 때 해당 영역에 덮어쓰기하게 된다. 이러한 방식을 통해 모든 파일을 지울 때 발생하는 디스크 입출력에 대한 부담을 줄여주어 성능을 끌어올리고, 데이터 복구 가능성 또한 열어두는 것이다.

자료구조와 알고리즘

Q. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.

• 버블정렬: 현재 요소와 다음 요소를 비교하며 정렬하는 알고리즘으로 구현이 쉽지만 중첩 for 문을 사용하기 때문에 성능이 좋지 않다. 단, 정렬하려는 요소의 다음 요소를 비교하기 떄문에 안정적인 정렬 알고리즘이다. | O(n^2) |

• 선택정렬: 정렬된 영역과 정렬되지 않은 영역을 나누어, 정렬되지 않은 영역에서 가장 작은 (또는 가장 큰) 값을 선택해 정렬한다. 구현이 쉽지만 버블정렬과 마찬가지로 중첩 for 문을 사용하기 때문에 성능이 좋지 않다. 단, 버블 정렬보다 교환 횟수가 상대적으로 적은데 이는 큰 배열에서 선택 정렬이 상대적으로 빠르다. | O(n^2) |

• 삽입정렬: 정렬되지 않은 영역의 요소를 정렬된 영역의 적절한 위치에 삽입하는 알고리즘으로 구현이 쉽다는 장점이 있지만 중첩 for 문을 사용하기 때문에 성능이 좋지 않다. | O(n^2) |

• 병합정렬: 정렬할 배열을 반으로 나누는데 더 이상 나눌 수 없을 때까지 반으로 나눈 후, 다시 역순으로 비교하며 병합하는 알고리즘이다. 재귀적으로 해결하기 때문에 이해 및 구현이 어렵다. 또한, 배열을 반으로 나누는 방식으로 비교적 많은 메모리 공간을 사용한다. 단, 버블/선택/삽입 정렬보다 빠른 성능을 가진다는 장점이있다. | O(nlogn) |

• 퀵정렬: '피벗'이라는 배열의 기준이 되는 요소를 선택한 후 재귀적 호출을 통해 정렬하는 알고리즘이다. 퀵정렬은 어떤 피벗을 선택하느냐에 따라 최악의 성능인 O(n^2)이 나올 수 있다. 하지만, 매번 최악의 피벗 선택을 하는 것은 극히 낮으며, 병합정렬보다 메모리 공간을 덜 사용하기 때문에 병합정렬보다 퀵정렬이 더 좋은 평가를 받는다. | O(nlogn) |

Q. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.

재귀적으로 호출하는 상황에서 메모리 부족 문제를 해결하기 위해서는, 이미 해결한 문제를 저장하여 불필요한 연산과 콜스택 낭비를 해결할 수 있다. 이를 메모이제이션이라고 부른다. 메모이제이션으로 메모리 부족 문제를 해결하는 방식은 값을 저장할 해시 테이블을 두고 재귀적으로 해결할 문제를 해시 테이블의 키 값으로 저장한다. 이후 같은 문제가 재귀적으로 호출 될 때 해시 테이블을 조회하여, 이미 해결된 문제라면 해당 키에 해당하는 값을 이용하여 메모리 낭비를 해결할 수 있다. 이러한 방식에서 해시 테이블을 이용하는 이유는, 해시 테이블의 특성상 키를 이용한 조회가 O(1) 시간으로 빠르게 값을 찾을 수 있기 때문이다.