인프런 워밍업 클럽 스터디 2기 - CS 2주차 발자국

강의 수강

운영체제

일주일 간의 학습했던 내용

• SJF (Shortest Job First)

  • FIFO에서 Burst Time이 짧은 프로세스를 먼저 실행했을 때 평균 대기 시간이 짧아져서 고안된 알고리즘

  • 현실적 어려움 존재 : 프로세스의 작업시간 예측 어려움, Burst Time이 긴 프로세스는 오랫동안 실행되지 않을 수 있음

  • 현재 사용되지 않는다.

    
    

• RR (Round Robin)

  • 할당된 시간이 지나면 강제로 다른 프로세스에게 CPU를 할당, CPU를 뺏긴 프로세스는 큐의 맨 뒤로 밀려나는 방식

     

  • 타임 슬라이스 : 프로세스에게 할당하는 일정 시간

  • 타임 슬라이스의 값이 매우 크다면, FIFO와 비슷해진다.

  • 타임 슬라이스의 값이 매우 작다면, 컨텍스트 스위칭 비용 > 프로세스 처리량 (오버헤드가 커진다.)
    

• MLPQ

  • 오늘날 운영체제에서 가장 일반적으로 쓰이는 CPU 스케줄링 기법

  • 기본적으로는 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임 슬라이스를 선택

  • CPU Bound Process에게는 타임 슬라이스를 크게 준다.

  • 우선순위 가진 큐를 여러 개 준비 후, 프로세스는 타임 슬라이스에 맞는 큐로 이동하게 됨

  • 

• 프로세스 간 통신

  • 컴퓨터 내의 프로세스 간의 통신 : 파일, 파이프를 이용

  • 프로세스 내 쓰레드 간의 통신 : 데이터 영역의 전역변수나 힙을 이용해서 통신

  • 네트워크를 이용한 통신 : 소켓 통신, RPC 사용
    

• 공유자원과 임계구역

  • 공유자원 : 프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일 -> 동기화 문제가 존재한다.

  • 임계구역 : 여러 프로세스가 동시에 사용하면 안 되는 영역

  • 임계구역 문제를 해결하기 위해서는 상호배제 매커니즘이 필요하다.

    • 임계영역엔 동시에 하나의 프로세스만 접근한다.

    • 여러 요청에도 하나의 프로세스의 접근만 허용한다.

    • 임계 구역에 들어간 프로세스는 빠르게 나와야한다.
      

• 세마포어

  • 운영체제가 가지고 있는 열쇠

  • 세마포어는 실제로 여러개의 열쇠를 가질 수 있다.

  • 

  • 단점 : wait(), signal() 함수의 순서를 이상하게 호출해서 세마포어를 잘못 사용할 가능성 존재
    

• 모니터

  • 세마포어의 단점을 해결한 상호배제 매커니즘

  • 운영체제가 아니라 프로그래밍 언어에서 지원한다.

  • ex) Java에서 synchronized가 붙으면 동시에 여러 프로세스에서 실행시킬 수 없다.

  • 상호배제가 완벽하게 이루어진다.

   

• 데드락 (교착 상태) : 여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무도 작업을 진행하지 못하는 상태

• 교착 상태의 필요조건 :

  상호배제, 비선점, 점유와 대기, 원형 대기

• 교착상태 회피

  • 프로세스에게 자원을 할당할 때 교착상태가 발생하지 않는 수준의 자원 할당을 한다.

  • 운영체제는 최대한 안정 상태를 유지하려고 자원 할당을 한다.

  • 이를 표현한 알고리즘 : 은행원 알고리즘

  • 은행원 알고리즘은 좋지만, 비용이 비싸고 비효율적

• 교착상태 검출 방식

  • 가벼운 교착 상태 검출

    • 프로세스가 일정한 시간동안 작업하지 않는다면 교착상태가 발생했다고 간주

    • 해결 방식 : 일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백
      

  • 무거운 교착 상태 검출

    • 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생했다면 해결

    • 자원 할당 그래프에서 순환구조가 생긴다면 교착상태라고 간주

    • 해결 방식 : 교착상태를 일으킨 프로세스를 강제종료 -> 다시 실행 시 체크포인트로 롤백

    • 단점 : 지속적으로 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드 발생

    • 장점 : 정확함 (억울하게 종료되는 프로세스 없음)

자료구조와 알고리즘

일주일 간의 학습했던 내용

• 재귀

  • 어떤 정의를 참조할 때 자기 자신을 참조하는 것

  • 계속 호출하게 되면 콜스택이라는 메모리 공간이 가득 차서 비정상으로 종료된다. -> 정상 종료를 위한 기저조건이 필요

  • for문으로 해결 가능한 상황을 재귀함수로 해결하려고 하면 비효율적인 경우도 많다. -> 메모리 공간을 더 많이 차지하기 때문

  • 하향식 계산을 해야 성능이 Good -> 하위 문제의 결과를 기반으로 현재 문제를 계산하는 것

  • 팩토리얼, 하노이 탑
    

• 버블 정

  렬

  • 앞에 있는 숫자와 바로 옆에 있는 숫자를 비교해서 자리를 바꾸는 방식으로 정렬하는 알고리즘

  • 장점 : 이해와 구현이 간단하다.

  • 단점 :

    성능이 좋지 않다. -> O(n^2)
    

• 선택 정렬

  • 배열이 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져오는 방식

  • 장단점은 버블 정렬과 동일하다.

회고

• 칭찬하고 싶은 점

   

이해가 한번에 안 되는 부분은 강의를 여러 번 돌려보고 개인적으로 다른 정보도 찾아보면서 공부했습니다.

개인 공부 시간을 늘렸다는 것에 칭찬하고 싶습니다.

• 아쉬웠던 점

   

늦게 퇴근하는 날이 있었어서, 2~3일치 강의를 몰아서 수강했습니다 😢

그래서 그런지 조금 급하게 강의를 수강한 것 같아서 아쉽습니다.

• 보완하고 싶은 점

   

스케줄에 밀리지 않고 강의를 수강할 수 있도록 보완하고 싶습니다.

미션

미션을 해결한 과정

재귀함수를 만드는 문제에서 두 가지 고민을 했습니다.

1. 어떻게 기저조건을 만들지

    

처음에는 n == 1일 때만 고려해서 기저조건을 만들었습니다.

if (n == 1) { return 1; }

하지만 문제에 0부터 입력 n까지 의 홀수의 합을 구하는 문제였기 때문에 0 이하의 수를 입력 받게 되는 경우도 고려해야 한다고 생각했습니다. 그래서 아래 기저 조건을 추가했습니다.

if (n <= 0) { return 0; }

2. 어떻게 메모리 사용을 줄일지

처음에는 n이 짝수일 경우에는 바로 sumOdd(n -1) 을 호출해서 홀수의 합만 구할 수 있도록 만들었습니다.

function sumOdd(n) {

// 기저조건 생략

if (n % 2 == 0) { return sumOdd(n - 1); }

return n + sumOdd(n - 1);

}

하지만 n이 짝수일 경우는 계산 결과에 포함되어 있지 않기 때문에 불필요하게 콜스택 메모리를 많이 사용할 수 있다고 생각했습니다.

그래서 최초 호출 시 n이 짝수로 들어왔을 때에만, sumOdd(n - 1)을 호출해서 파라미터를 홀수로 만들고

그 뒤로는 sumOdd(n - 2)를 호출해서 파라미터가 홀수인 경우만 고려할 수 있도록 수정했습니다.

function sumOdd(n) {

// 기저조건 생략

if (n % 2 == 0) { return sumOdd(n - 1); }

return n + sumOdd(n - 2); // 이 부분을 수정

}

그 외의 문제들은 강의 내용을 토대로 해결했습니다!

회고

미션 해결을 하면서 학습했던 내용을 복습하게 되는 것 같아서 좋았습니다.

특히 재귀 함수를 만드는 문제는 고민할 포인트가 다양해서 재밌었습니다 😄

실무에서도 코드를 작성할 때 성능을 고려해서 작성하는 습관을 들여야겠다는 생각을 하게 되었습니다.

다음 미션이 기대가 되는 이번주 미션이었습니다 👍