[인프런 워밍업 클럽 3기 CS] 2주 차 발자국

운영체제

프로세스 간 통신

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

• 통신은 한 컴퓨터 내에서 실행되고 있는 다른 프로세스와 할 수 있고, 네트워크로 연결된 다른 컴퓨터에 있는 프로세스와 할 수도 있다.

종류

한 컴퓨터 내에서

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

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

한 프로세스 내에서

• 쓰레드 간 통신: 전역 변수나 힙을 사용

네트워크를 이용한 방법

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

• 다른 컴퓨터에 있는 함수를 호출하는 RPC

공유자원과 임계구역

공유자원

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

• 공유자원은 여러 프로세스가 공유하기 때문에 각 프로세스의 접근 순서에 따라 결과가 달라질 수 있음

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

• 연산 결과를 예측하기 힘들고 동기화 문제가 발생

임계구역

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

• 공유자원을 서로 사용하기 위해 사용하는 것은 경쟁조건이라 한다.

해결 방법

상호 배제의 요구사항

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

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

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

세마포어

• 상호배제 매커니즘 중 하나

모니터

• synchronized

• 동시에 여러 프로세스에서 실행시킬 수 없음

교착상태(데드락)

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

• 원인은 공유자원 때문

필요조건

• 상호배제: 어떤 프로세스가 한 리소스를 점유했다면 그 리소스는 다른 리소스에게 공유되면 안 된다.

• 비선점: 프로세스 A가 리소스를 점유하고 있는데 프로세스 B가 빼앗을 수 없어야 한다.

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

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

교착상태 해결 방법

교착상태 회피

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

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

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

• 불완전 상태에 있다고 교착상태에 빠지는 것이 아니라 교착상태에 빠질 확률이 높아진다.

교착상태를 검출하는 방법

1. 가벼운 교착상태 검출: 타이머를 이용해 프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주하고 해결함

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

2. 무거운 교착상태 검출: 자원 할당 그래프를 이용해 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생했다면 해결함

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

컴파일과 프로세스

컴파일 언어

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

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

인터프리터 언어

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

• 실행할 때 오류가 날 수도 있고 컴파일 속도가 느림

메모리

레지스터

• 가장 빠른 기억저장소

• CPU 내에 존재

• 컴퓨터의 전원이 꺼지면 데이터가 사라져 휘발성 메모리라고 함

캐시

• 필요할 것 같은 데이터를 미리 가져와 저장하는 곳

• 성능의 이유로 여러 개를 둔다

메인 메모리

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

• 전원이 공급되지 않으면 데이터가 지워지기 때문에 휘발성 메모리

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

보조 저장 장치

• 비휘발성 메모리

• 속도가 느리고 가격이 쌈

메모리와 구조

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

물리 주소

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

논리 주소

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

• 물리 주소를 몰라도 논리 주소로 접근할 수 있음

메모리 할당 방식

• 메모리 오버레이: 당장 실행해야 될 부분부터 메모리에 올리고 나머지는 하드디스크(스왑 영역)에 저장하는 방식

가변 분할 방식(세그멘테이션)

• 프로세스 크기에 따라 메모리를 할당하는 방식

장점 단점 메모리의 연속된 공간에 할당되기 때문에 낭비되는 공간인 내부 단편화가 없음 외부 단편화 발생

고정 분할 방식(페이징)

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

장점 단점 구현이 간단하고 오버헤드가 적음 작은 프로세스도 큰 영역에 할당되어 낭비되는 내부 단편화 발생

외부 단편화

• 남아있는 메모리의 크기가 실행하고자 하는 프로세스보다 크지만, 연속적이지 않은 공간에 존재하여 실행하지 못하는 현상

• 외부 단편화를 해결하는 방법은 공간을 합쳐주는 조각모음을 하면 된다.

내부 단편화

• Partition의 크기가 프로세스의 크기보다 커서 메모리가 남지만, 다른 프로세스가 사용할 수 없는 상태

알고리즘

재귀

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

• 재귀 함수: 재귀적으로 정의된 함수

function myFunction(number) {
  console.log(number);
  myFunction(number + 1);
}

• 콜스택이라는 메모리 공간이 가득차면 자동으로 종료됨

• 위 코드는 종료 조건이 없음

• 재귀 함수는 탈출 조건 즉, 기조 조건이 반드시 있어야 함

function myFunction(number) {
  if (number > 10) return;
  console.log(number);
  myFunction(number + 1);
}

콜스택

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

팩토리얼

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

하노이탑

1. 한 번에 한개의 원판만 옮길 수 있다.

2. 가장 위에 있는 원판만 이동할 수 있다.

3. 큰 원판이 작은 원판 위에 있어서는 안 된다.

정렬

버블 정렬

• 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘

• O(n^2)

• 장점: 이해와 구현이 간단함

• 단점: 성능이 좋지 않음

   

선택 정렬

• 정렬되지 않은 영역의 최솟값을 찾아 맨 앞의 위치한 값과 교체하여 정렬하는 알고리즘

• O(n^2)

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

References

• 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

• 그림으로 쉽게 배우는 운영체제