[인프런 워밍업 클럽 스터디 3기 - CS전공지식] 2주차 발자국

운영체제

프로세스 간 통신

• 프로세스간 통신은 1) 한 컴퓨터 내에서 파일과 파이프를 이용하는 방법과 2) 한 프로세스 내에서 데이터 영역과 힙 영역을 이용하여 쓰레드간 통신 하는 방법과 3) 소켓이나 다른 컴퓨터에 있는 함수를 호출하는 네트워크를 이용하는 방법이 있다.

공유자원과 임계구역

• 공유자원 : 프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일을 말한다.

  • 여러 프로세스가 공유하다보니 문제점이 발생하는데, 각 프로세스의 접근 순서에 따라 결과값이 달라지거나, 어떤 프로세스가 먼저 실행될지 예측하기 힘들기 때문에 연산 결과를 예측하기 힘든 동기화 문제가 발생한다

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

• 경쟁조건 : 공유자원을 서로 사용하기 위해 경쟁하는 것

• 임계구역 문제를 해결하기 위해 상호 배제 메커니즘을 사용한다.

• 상호 배제 메커니즘의 요구사항은 3가지

   

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

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

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

세마포어

• 상호배제 메커니즘 중 한가지이다.

• 세마포어를 가진 프로세스만 공유자원에 접근하는 방법.

  • 사용자(프로세스)가 프린터(공유자원)을 사용하기 위해 프린터실 앞 대기실(대기큐)에서 대기하고 있다가, 열쇠관리자(운영체제)에게 열쇠(세마포어)를 받아서 들어가서 사용한다. 프린터실에는 열쇠(세마포어)를 가진 한 사람만 들어갈 수 있다.

• 세마포어는 여러개를 가질 수 있다.

• 장점 : 공유자원에 여러 프로세스가 동시에 접근하지 못하기 때문에 동기화 문제가 발생하지 않는다.

• 단점 : 세마포어를 요청/반납 하는 함수의 순서를 이상하게 호출하면, 세마포어를 잘못 사용할 가능성이 있다.

모니터

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

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

• 대표적으로 자바에서 모니터를 지원한다.

• 자바에서 synchronized키워드가 붙으면 동시에 여러 프로세스에서 실행시킬 수 없다.

• synchronized키워드가 붙은 함수를 호출했다면, 어떠한 프로세스에서도 synchronized키워드가 붙은 어떠한 함수도 호출 할 수 없다.

교착상태(데드락)

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

• 교착상태가 발생하는 원인은 공유자원이다.

• 교착상태의 필요조건 (한가지라도 충족되지 않으면, 교착 상태가 발생하지 않음.)

  • 1. 상호배제 : 프로세스에게 점유 당한 리소스는 다른 프로세스에게 공유되면 안 된다.

  • 2. 비선점 : 프로세스에게 점유 당한 리소스는 다른 프로세스가 강제로 빼앗을 수 없다.

  • 3. 점유와 대기 : 어떤 프로세스가 리소스A를 가지고 있는 리소스B를 원하는 상태여야 한다.

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

데드락 해결

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

  • 전체자원의 수와 할당된 자원의 수를 기준으로 안정상태와 불안정상태로 나누어진다.

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

• 은행원 알고리즘 : 운영체제는 프로세스들에게 자원을 할당하기 전에 자기가 가지고 있는 전체 자원의 수를 알고 있어야 하고, 프로세스들은 각자 자기가 필요한 자원의 최대 숫자를 운영체제에게 알려줘야 한다. 이 숫자를 기반으로 안정상태와 불안정상태를 확인 할수있다.

  • 단점 : 비용이 비싸고 비효율적이다.

교착상태를 검출하는 법

• 가벼운 교착 상태 검출

  • 타이머를 이용하는 방식

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

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

• 무거운 교착 상태 검출

  • 자원 할당 그래프를 이용하는 방법

  • 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고, 만약 순화구조가 생겼다면 교착상태가 발생했다고 간주한다.

  • 교착상태를 해결하기 위해 교착상태를 일으킨 프로세스를 강제 종료하고 다시 실행 시킬 때 체크포인트로 롤백한다.

  • 장점 : 가벼운 교착 상태 검출에서 교착상태가 발생할때 전체 프로세스가 종료되는 현상은 발생하지 않음.

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

컴파일과 프로세스

• 프로그래밍 언어

  • 컴파일 언어 : 개발자가 코드를 작성하고 컴파일을 거쳐 0과 1로 된 기계어로 실행파일을 만듬

    • 기계어이기 때문에 속도가 빠름

  • 인터프리터 언어 : 개발자가 작성한 코드를 실행시 코드를 한 줄 씩 해석해 실행하는 언어

    • 실행시 오류 날 수도 있고, 컴파일언어와 비교하면 느림

• 프로세스의 메모리 구조

  • CODE영역 : 실행해야 할 코드

  • DATA영역 : 전역변수나 배열

  • HEAP영역 : 프로세스가 실행될 때 할당되는 메모리. 유동적인 공간

  • STACK영역 : 프로세스가 실행될 때 할당되는 메모리. 지역변수와 함수 관련 값

• 컴파일 언어의 컴파일 과정 : test.c → 전처리기 → test.i → 컴파일러 → test.s → 어셈블러 → test.o → 링커 → test.exe

메모리 종류

• 레지스터 : 가장 빠른 기억 장소, 휘발성메모리

• 메인메모리(RAM) : 운영체제와 다른 프로세스들이 올라가는 장소, 휘발성메모리

• 보조저장장치(HDD, SSD) : 비휘발성 메모리. 메인메모리에 비해서 훨씬 저렴함.

메모리와 주소

• 주소 : 운영체제는 메모리를 관리하기 위해서 1바이트 크기로 구역을 나누고 숫자를 매기는 것

• 물리주소공간 : 메모리를 컴퓨터에 연결하면 0번째부터 시작하는 주소 공간

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

• 사용자는 논리주소로 물리주소에 접근할 수 있음.

• 메모리에는 운영체제를 위한 공간이 따로 있고, 메모리 관리자가 경계 레지스터로 사용자 프로세스가 경계레지스 터의 값을 벗어났는지 검사하고 만약 벗어났다면 그 프로세스를 종료 시킨다.

• 절대주소 : 메모리관리자가 바라보는 주소공간(물리주소)

• 상대주소 : 사용자가 바라보는 주소공간 상대주소(논리주소)

• 재배치 레지스터 : 프로그램의 시작 주소가 저장되어 있고, CPU가 데이터를 요청하면 메모리 관리자가 재배치 레지스터에 있는 프로그램의 시작 주소와 CPU가 데이터를 요청한 주소를 더하여 데이터를 가져와 전달하게 된다.

  • 만약 프로그램의 시작 위치가 바뀌어도 재배치 레지스터만 수정해주면 되기 때문에 굉장히 유연하다.

메모리 할당방식

• 유니프로그래밍 환경에서 메모리보다 더 큰 프로그램을 실행 시킬때 메모리 오버레이 방식을 사용한다.

  • 메모리 오버레이 방식 : 큰 프로그램을 메모리 위에 잘라서 올리고, 남은 조각은 하드디스크의 스왑영역에 저장시키는 방식

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

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

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

    • 장점 : 메모리에 연속된 공간에 할당되기 때문에 더 크게 할당되서 낭비되는 공간인 내부 단편화가 없음

    • 단점 : 외부 단편화가 발생함.

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

    • 장점 : 구현이 간단하고 오버헤드가 적음

    • 단점 : 작은 프로세스도 큰 영역에 할당되서 공간이 낭비되는 내부 단편화가 발생함.

• 외부 단편화 : 메모리에 서로 다른 크기를 가지고 있는 여러개의 프로세스중 작업을 마친 프로세스가 메모리에서 내려가면 그 프로세스들이 있는 공간은 빈공간이 된다. 이때, 그 빈 메모리를 전부 합친 공간이 필요한 프로세스가 있을때, 연속된 공간이 아니기 때문에 새로운 프로세스에게 메모리를 할당할 수 없다.

  • 외부단편화의 해결법으로 조각모음을 해주면 되지만, 현재 메모리에서 실행되고 있는 프로세스들의 작업을 일시 중지하고, 메모리 공간을 이동시키는 작업을 해야하기 때문에 오버헤드가 발생함.

• 내부 단편화 문제는 분할된 크기를 조절해서 내부 단편화를 최소화 하는 방법밖에 없다.

• 버디 시스템 : 2의 승수로 메모리를 분할해 메모리를 할당하는 방식

  • 메모리의 크기가 2048바이트라고 가정할 때, 크기가 500바이트인 프로세스가 할당을 원하면, 먼저 2의 승수로 500바이트보다 작은 바이트를 만날 때까지 메모리를 나누고, 512바이트에 할당 한다. 이때 내부 단편화가 발생하지만, 12바이트밖에 낭비가 생기지 않는다.

  • 장점 : 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고, 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단하다. 내부 단편화가 발생하기는 하지만, 많은 공간의 낭비가 발생하지 않는다.

     

자료구조와 알고리즘

재귀

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

• 재귀 함수는 기저조건(탈출조건)이 반드시 있어야 한다.

  • 기저조건이 없이 실행된다면, 콜스택이 가득차서 메모리가 부족하여 자동으로 종료된다.

• for문으로 해결할 수 있는 작업을 재귀함수로 해결하면 비효율적이다.

• 재귀함수는 더 복잡한 문제를 쉽게 해결하기 위해 사용된다. (대표적으로 팩토리얼)

재귀적으로 생각하기

• 패턴1 : 단순히 반복 실행하는 패턴 → 성능 안좋음

function myFunction(number) {
    if (number > 3) return; // 기저조건
    console.log(number);
    myFunction(number + 1);
}
myFunction(1);

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

  • 하향식 계산 방식은 재귀 방식으로만 구현할 수 있다.

  function factorial(number) {
      if (number === 1 || number === 0) {
          return 1;
      }
      return number * factorial(number - 1);
  }
  console.log(factorial(5));

  재귀 - 하노이탑

• 하노이탑 규칙

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

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

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

  function hanoi(count, from, to, temp) {
      if (count === 0) return;
      hanoi(count - 1, from, temp, to);
      console.log(`원반 ${count}를 ${from}에서 ${to}로 이동`);
      hanoi(count - 1, temp, to, from);
  }
  
  hanoi(3, "A", "C", "B"); // 원반3개, A기둥(from)에서 C기둥(to)로 이동하는데, B기둥(temp)도 사용함

• 하노이탑을 재귀로 접근하기(하향식 접근 방식)

  • 기둥A에 있는 원반1,2,3을 기둥C로 옮기기

    • 원반1, 기둥C 이동 → 원반2, 기둥B 이동 → 원반1, 기둥B 이동 → 원반3, 기둥C 이동

    • 원반1, 기둥A 이동 → 원반2, 기둥C 이동 → 원반1, 기둥C 이동

       

  정렬 - 버블 정렬

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

  정렬이 완료된 범위는 제외한다.

• 버블 정렬의 성능 : O(n²)

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

• 단점 : 성능이 O(n²)으로 좋지 않음.

정렬 - 선택정렬

• 배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져온다. 배열의 끝에 다다를때까지 반복하는데, 정렬이 완료된 범위는 제외한다.

• 선택 정렬의 성능 : O(n²)

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

• 단점 : 성능이 O(n²)으로 좋지 않다.

회고

• 칭찬하고 싶은 점 : 진도표 대로 따라가지는 못했지만, 벼락치기로 한주를 마무리 한건 아니어서 만족한다.

• 아쉬웠던 점 : 재귀를 이해하려고 노력했는데, 아직은 조금 이해가 부족한 것 같다. 인프런 워밍업 클럽에 출석체크 방이 있다는 것을 이제야 알았다..!

• 보완하고 싶은 점 : 여러 재귀함수 예시를 찾아보려고 한다.

• 다음주의 목표 : 밀리지 않고, 진도표대로 따라가기. 늦었지만, 출석체크 꼬박꼬박 하기.