이동규

개발 잘하고 싶다

1. 공부방법

1) 종합시험 한달 전, 스터디가 큰 도움이 되었다

  • 대학원 졸업의 조건 중 하나는 3개 과목(알고리즘, 인터넷특론, 운영체제)을 통과해야만 한다. 각 과목은 내용이 많아서 먼저 지금까지의 기출 문제를 정리했고, 까다로운 과목인 알고리즘 과목부터 스터디를 시작했다.
  • 특히나 스터디에서 도움을 받을 수 있던 것은 운영체제 과목은 이번학기에 수강중인 과목이다 보니 모르는 내용이 기출에 많이 있었다. 물론, 홀로 답을 달고 공부할 수 있지만 스터디에서 도움 받은 것은 각자가 조사해온 문제에 대한 답안을 공유함으로써 답안을 보강하고 설명하는 과정에서 자연스럽게 학습이 되었다는 것이다.

2) 교수님이 “~도 공부해놓으면 좋다”라는 말은 시험에 나온다는 말

  • 운영체제가 수강중인 과목인데다 기출에서 패턴을 보기 어려워 난감했는데, 교수님이 지난 기수한테 운영체제에서 ‘CPU 스케쥴링도 공부해둬라’라고 하셨다. 반신반의였지만, CPU 스케쥴링이 종합시험과 별개로 중간고사의 출제범위이기도 했고, 워낙 수업시간에 강조한탓에 CPU 스케쥴링의 종류와 각각의 특징에 대해 시험 바로 직전에 외워둔 것이 매운 큰 도움이 되었다.
  • 늘 그렇지만 시험공부는 쌔~한건 다외우는게 답인거 같다

[기출정리]

알고리즘

  • 함수 증가에 따른 시간 복잡도 표기법에 대해 설명하고, T(n) = 10T(n/2) + O(n3)을 Master 방식으로 해를 구하시오.
  • Loop 불변성 개념을 설명하고 MergeSort 알고리즘의 병합단계에서 불변성을 증명하시오.

인터넷특론

  • IEEE 802.11 무선 프로토콜이 CSMA/CA 플로우 차트와 DSSS와 CDMA 차이점을 설명하시오.
  • (이건 기억이 안난다.)

운영체제

  • CPU 스케쥴링에서 가장 이상적인 스케쥴링이 무엇인지 말하고, 해당 스케쥴링이 preemtive일 때 어떻게 동작하는지 설명하시오.
  • 가상메모리에 대해 설명하고 디멘딩 페이지 원리를 설명하시오.

[공부한 것 정리]

알고리즘

  1. (문제) Loop invariant에 대해 설명하고, Quick Sort 알고리즘의 정확성 평가를 Loop invariant로 설명하시오.

    (정답) 루프의 불변성(Loop invariant)은 컴퓨터가 대량의 데이터를 처리할 때 루프(Loop)를 사용할 수 밖에 없는데, 이것에 대해 3단계(Initialization, Maintenace, Termination)에 걸쳐 알고리즘이 정확히 동작하는지를 증명하는데 사용된다.

    • Initialization(초기화): 루프의 첫번째 반복 전에 참임을 증명
    • Maintenance(유지): 어떠한 루프의 반복 전에도 참이었다면, 다음 반복에도 참임을 증명.
    • Termination(종료): 루프가 종료되었을 때, 알고리즘이 정확한지 보여주는 특성이 있는지 증명

    QuickSort에서 하위 배열을 나누는 위치를 표시하는 인덱스 q를 반환하는 PARTITION 프로시져를 통해, 분할 단계를 수행할 수 있다

    QuickSort의 루프 불변성을 증명하면 다음과 같다

    • 초기조건: Loop의 첫 반복 전, 나누어진 두 배열은 모두 비어 있으므로 불변성은 참이다
    • 유지조건: 만약 A[j]가 Pivot보다 작거나 같다면, i는 1증가하고 A[j]와 A[i]는 교환된다. 따라서, A[ … i]의 모든 원소는 Pivot보다 작거나 같은 원소로 정렬되어 있다. 반면에 A [ i+1 … j ]의 모든 원소는 Pivot보다 크기 때문에 불변성은 참이다.
    • 종료조건: Loop가 종료될 때, A[ … i]의 모든 원소는 Pivot보다 작거나 같고, A[i+1 … ]의 모든 원소는 Pivot보다 크다. 그리고 Pivot은 i+1의 위치로 이동되기 때문에 불변성은 참이다.

  2. (문제) Loop invariant에 대해 설명하고, Merge Sort 알고리즘의 정확성 평가를 Loop invariant로 설명하시오. (정답) 루프의 불변성(Loop invariant)은 컴퓨터가 대량의 데이터를 처리할 때 루프(Loop)를 사용할 수 밖에 없는데, 이것에 대해 3단계(Initialization, Maintenance, Termination)에 걸쳐 알고리즘이 정확히 동작하는지를 증명하는데 사용된다.

    • Initialization(초기): 루프의 첫번째 반복 전에 참임을 증명
    • Maintenance(유지): 어떠한 루프의 반복 전에도 참이었다면, 다음 반복에도 참임을 증명.
    • Termination(종료): 루프가 종료되었을 때, 알고리즘이 정확한지 보여주는 특성이 있는지 증명.

    Merge Sort의 루프 불변성을 증명하면 다음과 같다.

    • 초기조건 : 루프의 첫 반복이 시작되기 전에 빈 배열이므로 나눌 수 없기 때문에 불변성은 참이다.
    • 유지조건 : 두 개로 나누어진 배열에서 가장 작은 값이 결과 배열의 원소로 추가되고, 이 원소는 두 배열의 가장 작은 값 만을 포함하므로 불변성은 참이다.
    • 종료조건 : 루프가 종료되면, 두 배열 모두 정렬된 상태이다. 따라서, 병합 단계에서도 정렬된 상태를 유지하고 있으므로 불변성은 참이다.

  3. (문제) 다음 점화식을 Master 정리로 해를 구하시오. T(n) = 5T(n/2) + θ(n^3) (정답) Master 방식은 다음과 같이 주어진 점화식이 특정한 형태일 때, 두 개의 항의 크기를 비교하여 해를 쉽게 구하는 방식이다.

    T(n) = aT(n/b) * f(n)

    ( a ≥ 1, b > 1, f(n)은 비재귀적 동작 )

    주어진 점화식을 다음과 같이 분석하여, 항을 구한다.

    a = 5, b = 2, f(n)= n^3

    n^{log_ab} = n^{log_25} ≈ n^{2.32…}

    이 때, 아래 master theorm의 3가지 case 중 어디에 속하는지 분석해야 한다.

    Case 1:

    if f(n) = O(n^{log_ba - e}) e > 0

    n^{log_ba - e} > f(n),

    then T(n) = \varTheta(n^{log_ba})

    Case 2:

    if f(n) = \varTheta(n^{log_ba})

    n^{log_ba} = f(n),

    then T(n) = \varTheta(n^{log_ba} * logn)

    Case 3:

    if f(n) = \Omega(n^{log_ba + e}) for some constant $e > 0,

    if a *f(n/b) <= c * f(n), then c < 1,

    n^{log_ba} < f(n),

    then T(n) = \varTheta(f(n))

    다음으로 위에서 구한 n^{log_25} 과 f(n) = n^3 의 크기를 비교한다. 이 때 n^{log_25}가 n^3보다 작고,

    5 * f(n/2) = c * f(n)

    5 * (n/2)^3 = c * n^3

    c = 5/8 < 1

    따라서, case3에 해당하므로 점화식의 해는 다음과 같다

    T(n) = \varTheta(n^3)

  4. (문제) 함수 증가에 따른 시간 복잡도 표기법에 대해 설명하시오. (정답) Untitled (2)

    • 세타 표기법(tight bound) : 빅-오와 빅-오메가의 중간값. 구할 수 있으면 3가지중 가장 근사하지만 일반적으로 구하기 쉽지 않다.

    • 빅-오 표기법(Upper bound) : worst 케이스, 시간 복잡도에 많이 사용함, 최악의 경우(최대한 이정도 걸린다.)
    • 빅-오메가 표기법(lower bound) : 최선의 경우, (적어도, 최소한, 미니멈 이정도는 걸린다.)

  5. (문제) T(n)=T(n/3)+T(2n/3)+cn 일 때, Recursion Tree 형식으로 문제를 풀고 Tree의 깊이와 전체 Cost를 구하고 빅오 (O) 형태로 표기하시오 (정답) Recursion Tree 방식은 base case까지 치환하고, 확장하여 각 Level cost를 구하고 모든 Level cost를 더하여 Total cost를 구하는 방식이다. 먼저, 주어진 점화식을 Tree로 확장하면 다음과 같다. Untitled (3)

    위 Tree의 패턴을 보면, 모든 Level cost의 비용이 cn 으로 동일하다. Tree가 비대칭적으로 확산되기 때문에 오른쪽 가장자리를 따라 가장 깊은 경로( T(2n/3) )의 일반항 T(2/3)^k*n을 구할 수 있다. base case가 1일 때, depth(k)를 구하면 다음과 같다:

    1 = (2/3)^k * n

    k = log_3/_2n

    k = log_{2/3} {1/n}

    따라서, Total cost는 각 레벨의 비용과 depth를 곱하여 다음과 같이 구할 수 있다:

    Total cost = cn * log_3/_2n

    이를 빅오 표기법으로 표기하면 다음과 같다: O(n log n)

인터넷특론

  1. (문제) 무선 환경에서 발생하는 Hidden Terminal 문제와 무선랜 상에서 해결 방법을 설명하시오. (정답) Hidden terminal은 무선 환경에서 발생한다. 아래 그림과 같이 AP를 기준으로 두 개의 스테이션이 있는데, AP와 스테이션 사이의 전송 문제가 없더라도 베리어가 있으면, 서로 감지 범위 밖에 있기 때문에 carrier sensing이 안되어 충돌이 일어날 수 있고 이 문제가 Hidden terminal 문제이다. Untitled (4)

    Hidden terminal의 해결법은 RTS(Request To Send), CTS(Clear To Send) 교환방식이다. 선착순으로 스테이션 A에서 AP로 RTS를 보낸다. 그러면 AP가 CTS로 응답한다. 이 때, CTS는 스테이션 A와 B 모두에 응답된다. 스테이션 B는 RTS를 C전송하지 않았음에도 TS를 전송받았기 때문에, 보낼 데이터를 보류하여 충돌을 회피할 수 있다.

  2. (문제) 이동통신에서 다중 엑세스(Multiple Access) 기술의 목적 및 원리를 설명하고, 대표적인 3가지 종류를 설명하시오. (정답) 다중 액세스(Multiple Access)는 여러 유저가 동시에 채널을 공유하고 간섭을 최소화하여 통신하기 위해, 물리적 자원(라디오 스펙트럼)을 효율적으로 사용하는 기술이다.

    다중 액세스의 3가지 기술은 다음과 같다.

    • FDMA(Frequency Division Multiple Access): 주파수 대역을 여러 개의 주파수 채널로 나누어 각 유저에게 할당하는 방식이다. 각 유저는 할당된 채널을 독점하여 사용한다.

    • TDMA(Time Division Multiple Access): 하나의 주파수 채널을 시간 슬롯으로 나누어 각 유저에게 할당하는 방식이다. 주파수 채널 하나를 ms단위로 돌아가며 순차적으로 사용하게 된다.

    • CDMA(Code Division Multiple Access): 시간축에 겹쳐있는 논리적 자원인 코드 채널을 사용하는 방식. 코드 채널은 0과 1로 이루어진 bit Sequence로 무한대로 만들 수 있으며, 같은 시간에 있더라도 직교성이 있어 간섭이 발생하지 않는다. 여기서 직교성이란 두 개의 채널을 적분하여 0이 나오는 상태를 말한다.

  3. (문제) IEEE 802.15.4 LR-WPAN(Low-Rate Wireless Personal Area Network)에 MAC 프로토콜인 CSMA/CA 방식에서 unslotted부분을 흐름도로 표시하고, 특히 저전력 기능을 어떻게 실현 하는지 설명하시오. (정답) CSMA/CA 방식의 unslotted 모드 흐름도는 다음과 같다. Untitled (5)

    backoff 횟수(NB)를 0으로 초기화하고 BE를 macMinBE로 설정한다. 다음으로 BE에 기반한 랜덤 backoff 시간을 설정하여 딜레이를 준다. CCA를 통해 채널의 상태를 감지한다. 채널이 idle하면 데이터 프레임을 전송하고, busy 상태면 NB를 1 증가시키고 BE를 조정한 후, 다시 랜덤 backoff 시간을 설정하여 딜레이를 준다. 이 과정을 macMaxCSMABackoffs 횟수까지 반복한다. 만약 NB가 macMaxCSMABackoffs에 도달하면 전송을 포기한다.

    WPAN은 CSMA/CA의 non-persistent 방식으로 장치가 backoff 시간 동안 대기하면서 다음 채널 감지를 기다릴 때, 이 대기 시간 동안 장치는 sleep 상태로 전환하여 전력을 절약할 수 있다.

  4. (문제) 이동통신은 셀룰러 기반으로 전체 담당 지역에 서비스를 제공하는데, 셀룰러 방식의 개념을 설명하시오. (정답) 셀룰러 방식은 1개의 고출력 기지국이 대도시 전체를 커버하는게 아닌, 셀(Cell)이라는 지역적인 영역으로 네트워크를 나누는 방식이며, 각 셀의 중앙에는 기지국이 위치한다.

    이렇게 작은 셀로 나누어 전송량을 줄이면, 똑같은 주파수를 다른 셀 영역에서도 재사용할 수 있어 사용자수를 늘릴 수 있는 장점이 있다.

    하지만, 기지국 수가 늘어난 만큼 초기 비용이 많이 들어간다.

  5. (문제) IEEE LAN 상에서 3 종류의 LLC 링크 서비스가 가능한데, 특히 무선 LAN 에서 어떠한 종류의 서비스가 필요한지 유선 LAN 과 비교하여 설명하시오. (정답) LLC는 IEEE 802 표준의 데이터 링크 계층에 속하며, 다음과 같은 링크 서비스를 제공한다.

    • Unacknowledged connectionless service:

      • 커넥션을 사용하지 않고, 데이터 전송 확인(Ack)도 수행하지 않음.

      • 근거리 유선 네트워크 환경에서 주로 사용.

    • Acknowledged connectionless service:

      • 커넥션을 사용하지 않지만, 데이터 전송 확인(Ack)은 수행.

      • 무선 네트워크에서 주로 사용. 무선의 특성 상 에러가 발생할 확률이 높기 때문에 데이터 수신을 항상 확인함.

    • Connection-mode service:

      • 커넥션을 설정하여, 플로우와 에러 컨트롤을 수행.

      • 장거리 유선 네트워크 환경에서 주로 사용

    무선 환경의 특성 상 에러가 자주 발생할 수 있기 때문에, Ack을 사용하여 항상 데이터의 수신을 확인해야하며, 에러 발생 시 재전송을 수행할 수 있어야 한다.

    따라서, 무선 LAN 환경에서는 Acknowledged connectionless service를 사용해야 한다.

  6. (문제) 블루투스 방식은 주로 소형 디바이스를 대상으로 하고있기 때문에,효율적인 전력 관리를 위해 Slave 디바이스를 전력 소모 관점에서 4가지 상태로 구분하여 관리하는데,각각의 상태를 설명하시오. (정답)

    • Active: 피코넷에서 활동, Full Power, 항상 깨어 있는 상태(Listen, Transmit, Receive packets)
    • Sniff: 피코넷에서 활동, 정해진 슬롯만 Listen을 수행하고 이외에는 sleep 한다. 비동기/동기 지원
    • Hold: 피코넷에서 활동, 정해진 시간 동안 피코넷에서 활동하지 않음으로써 전력을 절감. (ACL 패킷 지원하지 않음[비동기 지원 X], 동기 지원[음성 통신])
    • Park : 피코넷에서 활동을 중단하고, 마스터의 비콘에 의해 필요시 깨어난다.

운영체제

  1. (문제) Thread의 정의와 장점을 설명하시오. (정답) 스레드는 프로세스에 비해 경량화된 방식이다. ‘스레드 ID’, ‘프로그램 카운터’, ‘레지스터’, ‘스택’으로 구성된다. 멀티 스레드 방식을 사용하면 스레드끼리 실행 코드, 데이터, 파일을 공유한다. 다중 스레드를 이용하면, 응답성, 자원공유, 경제성, 멀티프로세서 구조의 활용에서 이점을 얻을 수 있다.

    • 응답성: 자원을 공유하기 때문에, 빨리 응답할 수 있다.

    • 자원공유: 한 프로세스의 여러 스레드들은 실행 코드, 데이터, 파일 등을 공유할 수 있다.

    • 경제성: 새로운 프로세스를 생성하는 것보다, 한 프로세스 내에서 여러 자원을 공유하여 경제적이다.

    • 멀티프로세서 구조의 활용: 한 프로세스의 여러 스레드가 여러 CPU를 동시에 사용할 수 있어서 병렬성이 높다.

    스레드의 모델은 3가지가 있다.

    • Many to one model: 하나의 커널 스레드가 있고 여러개의 유저 스레드가 있다. 시스템 콜을 받으면 하나의 커널 스레드로 진입하게 된다.

      Untitled (6)

    • One to one model: 유저 스레드와 커널스레드가 일대일 매핑되는 방식. 유저 스레드는 커널 스레드에 제한없이 들어갈 수 있다. Untitled (7)

    • Many to many model: 커널 스레드를 제한적으로 만들고 이를 유저 스레드에게 공유하는 방식이다. Untitled (6)

  2. (문제) 가상메모리(Virtual Memory)의 개념을 설명하고, 어떻게 가상메모리를 구현하는지 대표적인 2가지 방법을 설명하시오. (정답) 가상메모리(Virtual Memory)는 논리 메모리와 물리 메모리를 분리하여, 프로세스 전체가 메모리 내에 올라오지 않더라도 실행 가능하게 하는 기법이 기법이며, 멀티프로그램이 쉽다. 논리 주소 영역은 물리 주소 영역보다 커질 수 있어서 메모리 크기에 제약받지 않는 장점이 있다.

    Paging 기법은 블럭이 동일한 고정된 크기로 가상 기억장소를 구성하는 방법이다. 페이지는 블럭단위로 보조기억장치로부터 주기억장치로 옮겨져서 페이지 프레임이라 불리는 주기억장치에 위치하게 되며, 내부 단편화는 발생하지만 외부 단편화는 발생하지 않는다.

    세그먼트 기법은 블럭이 가변적인 크기로 가상 기억장소를 구성하는 방법으로 각 세그먼트는 서로 독립적이다. 페이지 기법에 비해 물리적 개념보다는 논리적이라는 장점을 가지며 외부 단편화가 발생한다.

  3. (문제) Semaphore가 Busy Waiting 문제를 해결한 방법에 대한 설명과 Semaphore를 잘못 사용했을 때 발생할 수 있는 두가지 문제에 대해 설명하시오. (정답) 세마포어는 환경에서 공유 자원에 대한 동시 접근을 제한하는 방법으로 사용된다. 건널목 신호처럼 P(Wait)과 V(Signal) 두 개의 함수를 사용한다. 세마포어는 S라는 정수값으로 크리티컬 섹션(CS)에 프로세스를 얼마나 추가할지 정한다. 만약 S가 1이면 CS에 하나의 프로세스만 들어간다. 그리고 S를 증가, 감소시켜 프로세스 간의 동기를 맞춘다.

    Busy Waiting이란, 다른 프로세스가 CS를 사용중일 때, While 문에서 조건의 변경 검사를 계속 반복하여 CPU 시간을 낭비하는 현상을 말한다. Busy Waiting의 해결법은 Block과 Wake 함수를 추가하면 된다. 대기 시, 대기 큐에 해당 프로세스를 추가하고, 다른 프로세스의 Signal이 완료되면, 대기 큐에 있던 프로세스를 꺼내어 큐로부터 제거하고, 해당 프로세스를 깨운다.

    Semaphore를 잘못 사용했을 때 발생할 수 있는 문제는 다음과 같다.

    • 교착 상태(Deadlock): 둘 이상의 프로세스가 보류 상태에 놓여 자원을 이용하기 위해 기다릴 때 발생한다.
    • 기아 상태(Starvation): 특정 프로세스가 자원을 할당 바디 못하고 무한정 대기하는 상태를 말한다.

  4. (문제) 프로세스 동기화에서 race condition 문제를 해결하기 위한 요구사항을 기술하시오. (정답) 두 개 이상의 프로세스가 공유 메모리에 동시에 접근하여 하나의 공유 변수에 대해 경쟁적으로 수정 작업 할 때 생기는 데이터의 불일치 현상을 말한다. 이러한 문제를 해결하기 위해서 프로세스끼리 공유하는 코드 부분을 크리티컬 섹션(CS)으로 지정해야 한다. 이 CS는 다음과 같은 특성을 갖는다.

    • Mutual Exclusion : 두 개 이상의 프로세스가 CS에 동시에 들어가지 못하게 해야한다.
    • Progress : CS가 비어있고 대기 중인 프로세스가 있다면, 무한정 기다리게 하지 않고 올바른 결정 기법에 따라 진행시켜야 한다.
    • Bounded Waiting : CS에 진입 요청부터 그 요청이 허용될 때까지 프로세스가 대기하는 시간에는 한계가 있어야 한다.

  5. (문제) Memory Management Address Binding(주소 바인딩)에 대하여 설명하시오. (정답) CPU는 물리 메모리에 올라간 데이터를 읽고 쓸 수 있는데, 프로그램을 실행하기 위해 논리적 주소를 물리적 주소로 변환하는 과정을 말한다. 메모리 주소 공간에서 명령어와 데이터의 바인딩은 시점에 따라 다음과 같이 구분된다.

    • 컴파일 시간 바인딩: 컴파일 시간에 프로세스가 기억장치 어디에 들어갈지를 미리 알 수 있으면 컴파일러는 절대 코드를 생성할 수 있다.
    • 적재 시간 바인딩: 커파일 시간에 프로세스가 기억 장치 어디에 들어갈지를 알지 못하면 컴파일러는 재배치 가능 코드를 생성한다. 실제 바인딩은 적재할 때까지 지연된다.
    • 실행 시간 바인딩: 최종 실행 시간에 바인딩하는 방법으로, 하드웨어의 지원이 필요하다. 대부분의 운영체제가 이 방식의 바인딩을 채택한다.

  6. (문제) CPU Scheduling에 대해 설명하고, 스케쥴링의 종류와 그것에 대해 설명하시오. (정답)

  7. CPU Scheduling은 멀티프로그램 방식으로 여러 프로세스를 올려 CPU 사용률을 극대화하기 위한 방식이다. CPU Scheduling의 대표적인 기준은 프로세스의 레디큐 대기시간을 최소화다. 스케쥴링은 아래와 같이 3가지 방식이 있다.

    • FCFS(First-Come, First-Served): 프로세스가 들어온 순서대로 먼저 처리하는 기본적인 방식이다. 들어온 시간이 아주 작은 차이라도 순서대로 처리한다. 하지만, 단순한 처리 방식이기에 성능이 떨어질 수 있다.
    • SJF(Sortest-Job-First): CPU 사용시간을 가장 적게 사용하는 프로세스부터 처리하는 방식이다. 두가지 스키마(non-preemtive, preemtive)가 있는데, 요즘은 preemtive 스키마를 사용하여 인터랙티브 동작을 확보한다. CPU 스케쥴링에서 레디큐에 프로세스가 대기하는 시간을 최소화해주기 때문에 가장 Optimal한 방식이다.
    • RB(Round Robin): 현재 타임 쉐어링 시스템에서 가장 많이 사용하는 방식이며, 응답성이 가장 좋다. 각 프로세스는 타임 퀀텀만큼만 CPU를 사용하며, 순환하는 방식이다.

2. 시험후기

  • 6시 30분 ~ 8시 동안 진행되었는데, 샤프와 지우개를 들고가길 정말 잘한 것 같다. 끝나고 나서 손톱이 밀려서 아플정도로 열심히 했다는 점에서 후회는 없다 :) 좋은 결과가 나오길…

댓글남기기

참고