[워밍업 클럽 3기 CS 전공지식] 2주차 회고

[2 주차 시작하기 전 다짐]

• 아침에 일어나서 주어진 강의 분량을 다 듣기

• 틈날 때 강의 듣기

• 저녁에 집에 와서 다시 듣기 또는 실습 진행

• 강의 들으면서 강의 노트도 실시간으로 작성하기!

  ---

  [2 주차 회고]

  • 칭찬할 점

    • 2 주차 다짐을 모두 지켰다!

      
      => 꾸준히 하는 걸 힘들어하는 나에게 칭찬하고 싶다.

  • 아쉬운 점

     

    • 강의 노트를 적는 동안은 생각을 안 하고 따라 치기만 한 것 같다.

      
      => 강의를 듣고 그 날 강의 노트를 정리하는 시간을 가지자.

  ---

[강의 내용 정리]

[운영체제]

[프로세스 동기화]

• 프로세스 간 통신

  • 프로세스는 독립적으로 실행되기도 하지만 다른 프로세스와 데이터를 주고받으며 통신을 하는 경우도 있다.

  • 종류

    • 한 컴퓨터 내에서 프로세스 간 통신

      • 파일을 이용한 방법

        • 통신을 하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법

      • 파이프를 이용한 방법

        • 운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법

    • 한 프로세스 내에서 쓰레드 간 통신

      • 쓰레드는 코드, 데이터, 힙 영역을 공유하고 스택만 자기의 것을 가진다.

      • 데이터 영역에 있는 전역변수나 힙을 이용하면 통신이 가능하다.

    • 네트워크를 이용한 통신

      • 운영체제가 제공하는 소켓 통신하는 방법

      • 다른 컴퓨터에 있는 함수를 호출하는 RPC(원격 프로시저 호출)를 이용해 통신하는 방법

• 공유자원과 임계구역

  • 공유자원

    • 프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일들

    • 문제

      • 여러 프로세스가 공유하고 있어서 각 프로세스의 접근 순서에 따라 결과가 달라진다.

      • 컨텍스트 스위칭으로 시분할 처리를 하기 때문에 어떤 프로세스가 먼저 실행될 지 예측하기 어렵다.

      • 연산 결과를 예측하기 힘들다. 여기서 발생한 문제가 '동기화 문제' 이다.

    • 그러니 예측 불가능하고 손 댈 수 없는 운영체제 보다는 예측 가능하고 손 댈 수 있는 코드를 수정하는 게 최선이다.

  • 동기화 문제

    • 여러 프로세스 또는 여러 쓰레드가 공유 자원에 동시에 접근할 때 발생하는 문제이다.

    • 적절한 제어 없이 데이터가 동시에 수정되면 경쟁 조건(Race Condition)이 발생하여 예측 불가능한 결과나 데이터 불일치가 일어난다.

    • 해결 방법으로는 세마포어, 모니터 등의 동기화 기법을 사용한다.

  • 임계구역(Critical Section)

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

    • 임계구역 문제를 해결하기 위해서는 '상호 배제(Mutual Exclusion)' 메커니즘'이 필요하다.

  • 상호 배제(Mutual Exclusion) 요구사항 세가지

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

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

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

      • 그렇지 않으면 다른 프로세스들이 오래 기다려야 한다.

         

• 세마포어(Semaphore)

  • 상포배제 메커니즘의 한 가지이다.

  • 정수형 변수이다.

    • 공유되는 자원의 개수에 따라 세마포어의 초기값 숫자를 설정한다.

  • wait() 함수로 시작하고 signal() 함수로 끝나야 한다. 사이에 코드 작성

  • 세마포어를 이용하면 공유자원에 여러 프로세스가 동시에 접근하지 못하기 때문에 동기화 문제가 발생하지 않는다.

  • 단점

    • wait(), signal() 함수의 순서를 이상하게 호출해서 잘못 사용할 경우가 있다.

      
      => 이것을 해결한 방법은 '모니터'이다.

• 모니터(Monitor)

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

  • 운영체제가 처리하는 것이 아닌 프로그래밍 언어 차원에서 지원하는 방법

  • 대표적으로 Java 에서 모니터를 지원

    • synchronized 키워드

    • 해당 키워드가 붙은 함수들은 동시에 여러 프로세스에서 실행시킬 수 없다.

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

[데드락]

• 교착 상태(데드락)

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

  • 발생 이유

    • 여러 프로세스가 공유하는 자원 때문이다.

    • 자원을 공유하지 않으면 교착 상태가 발생하지 않는다.

  • 유명한 예시

    • 식사하는 철학자

  • 교착 상태의 필요조건

    • 교착상태가 발생하기 위해서는 4가지 필요 조건이 모두 충족되어야 한다.

    • 상호배제

      • 프로세스A가 한 자원을 점유했다면 그 자원은 프로세스B에게 공유가 되면 안된다.

    • 비선점

      • 프로세스A가 자원을 점유하고 있는데 프로세스B가 자원을 빼앗을 수 없어야 한다.

    • 점유와 대기

      • 어떤 프로세스가 자원A를 가지고 있는 상태에서 자원B를 원하는 상태여야 한다.

    • 원형 대기

      • 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있다.

• 해결

  • 교착 상태 회피(Deadlock avoidance)

    • 프로세스들에게 자원을 할당할 때 어느 정도 자원을 할당 했을 때 교착 상태가 발생하는지 파악해서 교착 상태가 발생하지 않는 수준의 자원을 할당한다.

    • 전체 자원의 수와 할당된 자원의 수를 기준으로 안정 상태(Safe state)와 불안정 상태(Unsafe state)로 나뉜다.

      • 운영체제가 최대한 안정 상태를 유지하려고 한다.

      • 불안정 상태에 있더라도 무조건 교착 상태에 빠지는 건 아니고 교착 상태에 빠질 확률이 높아진다.

    • 은행원 알고리즘

      • 돈을 빌려줄 때 사업가들의 상환 능력도 보면서 빌려준다.

• 교착 상태 발생했을 때 해결

  • 교착 상태를 막지 못한다. 그래서 교착 상태가 발생했을 때 해결하는 방법을 알아보자.

  • 가벼운 교착 상태 검출

    • 타이머를 이용한 방식

    • 프로세스가 일정 시간 동안 작업을 진행하지 않는다면 교착상태가 발생한 걸로 간주하고 해결한다.

    • 교착 상태 해결

      • 일정 시점마다 체크포인트를 만들어 작업을 저장한다.

      • 타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백한다.

  • 무거운 교착 상태 검출

    • 자원 할당 그래프를 이용

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

    • 프로세스들 간 자원 점유와 대기가 순환구조가 생긴다면 교착상태가 생긴 그래프이다.

      • 교착상태를 검출했다면 교착상태를 일으킨 프로세스를 강제종료 시킨다.

      • 그리고 다시 실행시킬 때 체크포인트로 롤백을 시킨다.

    • 운영체제가 지속적으로 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드가 발생한다.

    • 가벼운 교착상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스는 발생하지 않는다.

[프로그래밍 언어, 프로세스]

•  프로그래밍 언어

  • 컴파일 언어

    • 개발자가 코드를 작성하고 컴파일 과정을 거쳐서 0과 1로된 기계어로 실행파일을 만든다.

    • 컴파일 과정에서 문법 오류를 검사하고 CPU에서 처리가능한 기계어로 실행파일을 만들어 놓기 때문에 속도가 빠르다.

    • C, C++, C# 등이 이에 속한다.

  • 인터프리터 언어

    • 개발자가 작성한 코드를 미리 기계어로 만들지 않고 실행 시 코드를 한 줄씩 해석해 실행하는 언어이다.

    • 미리 검사를 하지 않기 때문에 실행할 때 오류가 날 수 있고 속도도 컴파일 언어와 비교하면 느리다.

    • JavaScript, Python, Ruby 등이 이에 속한다.

• 프로세스의 메모리 구조

  • 코드 영역, 데이터 영역, 스택 영역, 힙 영역으로 나뉜다.

  • 코드 영역

    • 말 그대로 실행해야 할 코드가 들어가는 영역

  • 데이터 영역

    • 전역변수나 배열이 들어가는 영역

  • 스택과 힙은 프로세스가 실행될 때 할당되는 메모리

    • 스택 영역

      • 지역변수와 함수 관련 값들

    • 힙 영역

      • 실행중에 메모리 공간을 할당할 수 있는 유동적인 공간

• 프로그램을 실행 시켰을 때

  • 사용자가 프로그램을 실행시키면 운영체제가 프로세스를 만든다.

  • 운영체제는 exe 파일에 있는 코드 영역과 데이터 영역을 가져온다.

  • 프로세스의 코드 영역과 데이터 영역에 넣어준다.

  • 빈 상태의 스택과 힙을 할당한다.

  • PCB(Process Control Block)를 만들어 관리가 가능하도록 만든다.

  • 프로그램 카운터 즉, 다음 실행할 명령어의 주소를 생성한 프로세스의 코드 영역의 첫 번째 주소로 설정한다.

  • 운영체제의 CPU 스케줄링에 따라서 프로세스가 실행되다기 작업을 마친다.

     

[메모리]

• 메모리 종류

  • 레지스터, 캐시, 메인메모리(RAM), 보조저장장치(하드디스크(이하 HDD), SSD)

  • 오른쪽으로 갈수록 가격은 싸지고 용량은 커진다. 속도는 느려진다.

  • 레지스터

    • 가장 빠른 기억 장소로 CPU 내에 존재한다.

    • 컴퓨터 전원이 꺼지면 데이터가 사라진다. 휘발성 메모리라고 부른다.

    • 32bit 레지스터를 가지고 있으면 32bit CPU라고 말한다.

    • 64bit 레지스터를 가지고 있으면 64bit CPU라고 말한다.

    • CPU는 계산 할 때 메인메모리에 있는 값을 레지스터로 가져와서 계산한다. 계산 결과는 다시 메인메모리에 저장시킨다.

  • 캐시

    • 레지스터와 메인메모리에서 중간 단계 역할을 한다.

    • 레지스터는 CPU가 사용하는 메모리로 굉장히 빠르다. 그에 비해 메인메모리는 너무나 느리다.

    • 메인메모리에 있는 값을 레지스터로 옮기려면 한참 걸린다. 그래서 필요할 것 같은 데이터를 미리 가져오기로 한다.

    • 미리 가져온 데이터를 저장하는 곳이 바로 캐시이다.

  • 메인메모리(RAM)

    • 운영체제와 다른 프로세스들이 올라가는 공간이다.

    • 전원이 공급되지 않으면 데이터가 지워져 휘발성 메모리이다.

    • HDD나 SSD 보다는 속도는 빠르지만 가격이 비싸기 때문에 데이터를 저장하기 보다 실행중인 프로그램만 올린다.

  • 보조저장장치인 HDD와 SSD

    • 가격이 저렴하고 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리이다.

    • 저장 작업하기에 좋다.

       

• 메모리와 주소

  • 운영체제는 메모리를 관리하기 위해 1바이트 크기로 구역을 나누고 숫자를 매긴다.

  • 이 숫자를 '주소'라고 부른다. - 1바이트(8비트)마다 주소를 가지고 있다.

  • 물리 주소와 논리 주소

    • 물리 주소

      • 메모리 0x0번지부터 시작하는 주소 공간

    • 논리 주소

      • 사용자 관점에서 바라본 주소 공간

    • 사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근할 수 있다.

    • 경계 레지스터

      • 하드웨어적으로 운영체제 공간과 사용자 공간을 나누는 경계 레지스터

  • 절대 주소와 상대 주소

    • 절대 주소

      • 실제 프로그램이 올라간 주소는 0x4000번지로 메모리 관리자가 바라본 주소이다.

    • 상대 주소

      • 컴파일러는 0x0번지라고 가정해서 프로그램 만든다.

    • 사용자가 바라본 주소인 '상대 주소'는 '논리 주소 공간'이라고 부른다.

    • 메모리 관리자가 바라본 주소인 '절대 주소'는 '물리 주소 공간'이라고 부른다.

  • 메모리 관리자

    • CPU가 요청한 상대 주소와 재배치 레지스터에 있는 절대 주소를 더해서 데이터에 접근한다.

    • 재배치 레지스터

      • 프로그램의 시작 주소가 저장되어 있다.

      • 시작 영역이 바뀌면 재배치 레지스터만 변경해주면 된다. 그래서 굉장히 유연하다.

• 메모리 할당방식

  • 유니프로그래밍 환경에서 메모리보다 더 큰 프로그램을 실행시키는 방법

    • 메모리 오버레이(memory overlay)

      • 큰 프로그램을 작게 나누어 일부만 실행하고 일부는 HDD의 스왑 영역에 저장된다.

      • 스왑(swap)

        • 스왑 영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑 영역으로 옮긴다.

  • 멀티프로그래밍 환경에서 메모리 관리

    • 가변 분할 방식

      • 프로세스의 크기에 따라 메모리를 나누는 방식

      • 프로세스가 크면 메모리도 크게 할당

      • 한 프로세스가 메모리에 연속된 공간에 할당되서 '연속 메모리 할당'이라고 한다.

      • 장점

        • 메모리에 낭비되는 공간이 없다. - 내부 단편화가 없다.

      • 단점

        • 외부 단편화가 발생한다.

      • 외부 단편화

        • 메모리 할당 해제 된 자리를 더하면 새로운 프로그램을 올릴 수 있는데 따로 따로 자리가 있어서 다른 프로그램을 올릴 수 없다.

        • 해결

          • 외부 단편화가 발생한 공간을 합쳐주는 조각모음을 하면된다.

    • 고정 분할 방식

      • 프로세스의 크기와는 상관없이 메모리를 정해진 크기로 나누는 방식

        • 프로세스 크기와 상관없이 메모리를 할당

      • 한 프로세스가 메모리에 분산되어 할당되어서 '비연속 메모리 할당'이라고 한다.

      • 장점

        • 구현이 간단하고 오버헤드가 적다.

      • 단점

        • 메모리에 낭비되는 공간이 있다. - 내부 단편화가 발생한다.

    • 가상 메모리에서 가변 분할 방식은 '세그멘테이션', 고정 분할 방식은 '페이징'이라고 부른다.

    • 버디 시스템

      • 가변 분할 방식과 고정 분할 방식의 단점을 최소화한 시스템

      • 2의 승수로 메모리를 분할해 메모리를 할당하는 방식

      • 프로세스가 사용을 마치고 메모리에서 나가도 근접한 메모리 공간을 합치기 쉽다.

      • 장점

        • 가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라진다.

        • 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단하다.

        • 고정 분할 방식처럼 내부 단편화가 발생하기는 하지만 많은 공간의 낭비가 발생하지 않는다.

[자료구조와 알고리즘]

[java로 실습한 것은 깃허브에 올려두었다.]

• 재귀

  • 사전적 정의 : 어떠한 것을 정의할 때 자기 자신을 참조하는 것

• 재귀 함수

  • 재귀적으로 정의된 함수

  • 기저 조건(탈출 조건)이 반드시 있어야 한다.

    • if() 로 함수를 종료하지 않으면 콜스택에 메모리 공간이 가득 차서 자동으로 종료된다.
      => java.lang.StackOverflowError 에러 발생

    • 콜스택

      • 함수가 호출되면서 올라가는 메모리 영역으로 스택이라고 부른다.

      • 스택의 특성처럼 먼저 들어온 데이터가 나중에 나간다. (FILO : First In Last Out)

      • 함수를 호출하면 해당 함수는 콜스택에 올라가게 되고 함수가 종료되면 콜스택에서 제거된다.

public class Recursion {
    public static void main(String[] args) {
        myFunction(1);
    }

    public static void myFunction(int number) {
        if (number > 10) return;
        System.out.println(number);
        myFunction(number + 1);
    }
}

• 재귀 함수 - 팩토리얼

  • n이 주어질 때 1부터 n까지 모든 수의 곱을 말한다.

    • 예시) 5! => 5*4*3*2*1 => 120

  • 재귀 함수 쉽게 작성하는 방법

    • 재귀 함수 내에서 자기 자신을 호출할 때 이 함수가 벌써 구현이 되어 있다고 가정하자.

      • 5! 구현하기

        • 5 * 4!(4*3*2*1) => 하위 4 * 3!(3*2*1) => 하위 3 * 2!(2*1) => 하위 2 * 1!(1)

      • factorial() 함수가 이미 구현되었다고 가정하면 5 * factorial(4)를 호출하면 된다.

    • 이를 일반화 하면 number * factorial(number-1)

    • 그리고 중요한 기저 조건을 만들어야 한다.

      • 1이 되면 팩토리얼은 종료된다.

      • 0! 은 1이기 때문에 같이 기저 조건에 넣겠다.

public class Factorial {
    public static void main(String[] args) {
        System.out.println(factorial(5)); // 120
    }

    public static int factorial(int number) {
        if (number == 1 || number == 0) {
            return 1;
        } else {
            return number * factorial(number - 1);
        }
    }
}

• 재귀적으로 생각하기

  • 패턴1

    • 단순히 반복 실행

    • 콜스택 공간을 많이 차치해 성능은 for문보다 좋지 않다.

  • 패턴2

    • 하위 문제의 결과를 기반으로 현재 문제를 계산하는 것

    • 재귀를 이용해 하위 문제의 결과를 기반으로 현재 문제를 계산하는 방식 - 하향식 계산

      • 재귀를 이용해서 상향식 계산도 가능하다.

      • 재귀 함수의 진정한 위력은 하향식 계산에서 발휘된다.

         

         

• 재귀 - 하노이탑 (정리 한번하기)

   

  

  • 재귀 함수의 대표적인 예시

    • 하향식 계산 방식을 보여줄 수 있는 좋은 예시이다.

  • 세 개의 기둥과 서로 다른 크기의 원반들이 있다.

    • 가장 큰 원반이 아래에 있고 위로 갈수록 작은 원반으로 이루어져 있다.

    • 현재 기둥에서 다른 기둥으로 옮겨야 한다.

  • 규칙

    • 한 번에 하나의 원반을 움직일 수 있다.

    • 가장 위에 있는 원반만 옮길 수 있다.

    • 아래에 작은 원반이 올 수 없다.

  • 하위 문제 찾기 (재귀함수를 이용해서 하향식으로 접근)

    • [깃허브 코드]

    • 이미 해결을 한 상황을 예상해보기 (하위 문제)

      • 첫 번째 목표 : 원반3을 기둥A에서 기둥C로 옮긴다.

         

        • 하위 문제1 : 원반3 위에 있는 원반1,2를 기둥A에서 기둥B로 옮겨야 한다.

          • hanoi(count - 1, from, temp, to);

        • 하위 문제2 : (하위 문제1) 이 해결되었다면 출력

          • System.out.printf("원반 %d을/를 %s에서 %s로 이동%n", count, from, to);
            => 원반 3을 A에서 C로 이동

        • 하위 문제3 : (하위 문제2) 가 해결되었다면
          => 두 번째 목표 : 원반1,2를 기둥 B에서 기둥C로 옮겨야 한다.

          • hanoi(count - 1, temp, to, from);

    • 기저 조건(탈출 조건)

      • 원반이 없는 경우, 옮길 원반이 없을 때

      • if (count == 0) return;

• 정렬 - 버블정렬

  • 가장 쉽게 생각할 수 있는 정렬 중 하나이다.

  • 구현하기 쉽지만, 성능은 좋지 않다.

  • 앞에 있는 숫자와 옆에 숫자를 비교해서 자리를 바꾸는 알고리즘이다.

  • 방식

    • 앞에서부터 요소들을 하나씩 비교한다.

    • 가장 큰 숫자는 자기 위치를 찾아 가장 끝에 정렬된다.

    • 이미 정렬된 마지막 원소를 제외하고 앞에서부터 다시 요소를 검사한다.

    • 남은 원소가 하나이면 더이상 정렬을 할 필요가 없다.

  • 성능

    • 반복 횟수 for문 * 원소비교 for문 => O(n제곱)

    • 성능이 좋지 않다.

  • 장점

    • 가장 쉽게 생각할 수 있는 정렬 방법으로 이해와 구현이 간단하다.

  • 단점

    • 성능이 O(n제곱)으로 좋지 않다.

• 정렬 - 선택정렬

  • 버블정렬과 마찬가지로 구현이 쉬운 알고리즘

  • 이해와 구현이 간단하지만 성능이 아쉽다.

  • 방식

    • 정렬된 영역과 정렬되지 않은 영역을 나눠서 정렬되지 않은 영역을 비교한다.

    • 정렬되지 않은 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져온다.

    • 첫 번째 원소는 정렬된 영역으로 제외하고 다시 정렬되지 않은 영역을 비교한다.

    • 정렬되지 않은 영역에 요소가 한 개 남으면 정렬할 필요없이 끝이난다.

  • 성능

    • 반복 횟수 for문 * 원소비교 for문 => O(n제곱)

    • 성능이 좋지 않다.

  • 장점

    • 이해하기 쉽고 구현이 간단하다.

  • 단점

    • 성능이 O(n제곱)으로 좋지 않다.

 ※ '강의 내용 정리' 출처

[인프런 / 그림으로 쉽게 배우는 운영체제 (감자) / 섹션 4~7]

[인프런 / 그림으로 쉽게 배우는 자료구조와 알고리즘 (감자) / 섹션 3 (유닛 1~5)]