CS 2주차 발자국

jurjur 1개월 전

운영체제

프로세스간 통신

프로세스는 독립적으로 실행되지만, 다른 프로세스와 데이터를 주고 받는 경우가 존재.
통신은 동일한 컴퓨터 또는 네트워크에 연결된 다른 프로세스와 통신이 가능함.
한 컴퓨터 내에서 프로세스간 통신하는 방법
- 파일 & 파이프
  - 하나의 파일을 이용해 읽고 쓰는 방법
  - 운영체제가 생성한 파이프를 이요해 데이터를 읽고 쓰는 방법
- 쓰레드
  - 한 프로세스 내에서 쓰레드간 통신을 하는 방법.
  - 쓰레드는 코드, 데이터, 힙 영역을 공유하므로 데이터 또는 힙 영역을 통해 통신
네트워크
- 소켓 통신
- 다른 컴퓨터에 있는 함수를 호출하는 RPC(원격 프로시저 호출)를 이용해 통신하는 방법

공유 자원과 임계 구역

통신을 할때 공동으로 이용하는 함수나 파일이 있는데 이를 공유 자원이라 함.
공유 자원은 여러 프로세스가 공유하기 때문에 각 프로세스가 접근하는 순서에 따라 결과가 달라짐.
컨텍스트 스위칭으로 시분할 처리 되기 때문에 어떤 프로세스가 먼저실행되고 나중에 실행되는지 예측이 어려움.
→ 연산 결과를 예측하기 힘들고 동기화 문제가 발생

임계 구역

여러 프로세스가 동시에 사용하면 안되는 영역을 임계 구역(Critical Section)이라 함.
공유자원을 서로 사용하기 위해 경쟁하는 것은 경쟁 조건(Race Condtion)이라 함.
임계 구역을 해결 하기 위해서는 상호 배제 매커니즘이 필요.

상호 배제의 요구사항

임계구역엔 동시에 하나의 프로세스만 접근한다.
여러 요청에도 하나의 프로세스의 접근만 허용한다.
임계 구역에 들어간 프로세스는 빠르게 나와야 한다.

세마포어

정의
- 운영체제는 자원을 사용할 수 있는 열쇠(세마포어)를 설정해서 공유 자원 요청이 온 프로세스에게 열쇠를 전달.
- 열쇠를 전달받은 프로세스는 공유 자원을 사용
- 다른 프로세스가 공유자원을 요청
- 이전의 프로세스가 열쇠를 반납할때까지 대기큐에서 대기.
- 공유 자원을 다 사용하고 난 후 운영체제에 열쇠를 반납.
- 운영체제는 대기 큐에서 기다리고 있는 프로세스에세 열쇠를 전달 하여 공유 자원 사용 허락.
단점
- 세마포어 호출이 꼬일 경우 원하는 대로 동작이 되지 않을 수 있다.

모니터

세마포어의 단점을 해결한 상호배제 메커니즘.
운영체제에서 처리하는 것이 아닌 프로그래밍 언어 차원에서 지원하는 방법

자바 예시

public class Health {
	private int health = 100;
	
	synchronized void increase(int amout) {
		health += amout;
	}
	
	synchronized void decrease(int amout) {
		health -= amout;
	}
}

synchronized 키워드가 붙어 있는 함수는 동시에 여러 프로세스에서 실행 시킬 수 없음.
상호배제가 완벽히 이루어짐.

교착상태(데드락)

여러 프로세스가 서로 다른 프로세스의 작업을 끝나길 기다리다가 아무도 작업을 진행하지 못하는 상태.
발생 이유는 공유자원.

교착상태 필요조건

아래 조건들이 모두 만족하면 교착상태가 발생.
하나라도 만족하지 않으면 교착 상태가 발생하지 않음.

상호배제
- 어떤 프로세스가 한 리소스를 점유 했다면 그 리소스는 다른 프로세스에게 공유가 되면 안됨.
비선점
- 리소스를 갖고 있는 프로세스 한테서 다른 프로세스가 리소스를 빼앗을 수 없다.
점유와 대기
- 리소스A를 갖고 있는 프로세스가 리소스B를 원하는 상태
원형 대기
1. 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있는 상태.

교착 상태 해결

교착 상태 회피(Deadlock avoidance)

프로세스에게 자원을 할당할때 교착 상태가 발생하는 상황을 파악해서 교착상태가 발생하지 않는 수준의 자원을 할당.
전체 자원의 수와 할당된 자원이 수로 안정상태와 불안정 상태로 나눔.
운영체제는 최대한 안정상태를 유지하려고 자원을 할당.
불안정 상태에 있다하더라고 무조건 교착 상태에 빠지는게 아니라 교착 상태에 빠질 가능성이 높아짐.

은행원 알고리즘(Banker’s Algorithm)

은행이 대출해주는 방식의 알고리즘
돈을 빌려줄때 은행의 여윳돈과 사업가들에게 빌려준 돈들을 보고 대출 가능한 상황인지 보고 빌려주는 알고리즘.
운영체제는 프로세스에게 자원을 할당하기 전에 자신이 가지고 있는 자원의 수를 파악
→ 시스테의 총 자원
프로세스들은 각자 자기가 필요한 자원의 최대 수를 운영체제에 알려줌
→ 최대 요구 자원

⇒ 은행원 알고리즘은 교착 상태를 피하는 좋은 알고리즘이지만 비용이 비싸고 비효율적.

교착 상태의 발생은 허용하지만, 교착 상태가 발생시 해결 방법을 연구.
교착 상태 검출 방법 고민.

가벼운 교착 상태 검출

프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착 상태에 발생했다고 감지하고 교착 상태를 해결.
해결 방법은 일정 시간마다 체크포인트를 만들어 작업을 저장하고 교착 상태가 발생하면 마지막으로 저장한 체크포인트로 롤백 하는 방식.

무거운 교착 상태 검출

자원 할당 그래프를 사용하여 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착 상태가 발생하면 해결.
자원 할당 그래프를 통해 순환 구조가 발생하면 교착 상태로 판단.
교착 상태를 검출하면 교착 상태를 일으킨 프로세스를 강제 종료하고, 다시 실행할때 체크포엔트로 롤백을 진행.
운영체제가 지속적으로 자원할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드가 발생.
가벼운 교착 상태 검출에서 발생하는 억울하게 종료되는 프로세스는 발생되지 않음.

메모리 종류

레지스터 - 캐시 - 메인 메모리(RAM) - 보조 저장 장치(HDD, SSD)
- 좌 → 우 갈수록 속도가 느려지고 용량이 커지며 가격이 저렴해진다.
레지스터
- 가장 빠른 기억 장소로 CPU내에서 존재
- 컴퓨터 전원이 꺼지면 데이터가 사라지기 때문에 휘발성 메모리라고 부름.
- 32bit, 64bit는 레지스터의 크기.
- CPU는 계산을 할 때 메인 메모리에 있는 값을 레지스터로 갖고와서 계산하고 계산 결과를 메인 메모리에 다시 저장.
캐시
- 레지스터와 메인 메모리 사이에 존재하는 메모리.
- 레지스터와 메인 메모리 데이터 속도의 차이 때문에 필요한 데이터를 미리 갖고와서 저장하는 공간.
- 속도에 따라 L1, L2, … 캐시가 존재.
메인 메모리
- 실제 운영체제와 다른 프로세스가 올라가는 공간
- 전원이 공급되지 않으면 데이터가 지워지기 때문에 휘발성 메모리.
- 하드디스크나 SSD 보다 속도는 빠르지만 가격이 비싸기 때문에 실행중인 프로그램만 올라감.
보조 저장 장치
- 전원이 공급되지 않아도 데이터가 지워지지 않는 비 휘발성 메모리.

메모리와 주소

메인 메모리에 대한 설명
오늘 날의 컴퓨터는 폰 노이만 구조.
폰 노이만 컴퓨터는 모든 프로그램을 메모리에 올려 실행.
유니 프로그래밍 환경에서는 하나의 프로세스만 메모리에 올라가 메모리 관리가 쉬었으나, 멀티 프로그래밍 환경에서는 여러개의 프로세스가 올라가 실행되어 복잡하고 어려워짐.
운영체제는 메모리를 관리하기 위해 1바이트(8bit) 단위로 나누고 숫자를 할당.
→ 주소

32bit, 64bit CPU

32bit CPU는 레지스터 크기가 32bit, CPU가 처리하는 ALU(산술 논리 연산 장치)도 32bit, 데이터가 이동하는 버스도 32bit. 또한 CPU가 다룰 수 있는 메모리도 2^32으로 4GB.
64bit CPU는 레지스터 크기가 64bit, CPU가 처리하는 ALU(산술 논리 연산 장치)도 64bit, 데이터가 이동하는 버스도 64bit. 또한 CPU가 다룰 수 있는 메모리도 2^64으로 거의 무한대에 가까움
⇒ 64bit가 32bit보다 한번에 처리할 수 있는 양이 많아 속도가 빠름.

물리 주소와 논리 주소

메모리를 컴퓨터에 연결하면 0x0번지부터 시작하는 주소 공간이 존재
→ 물리 주소 공간.
사용자 관점에서 바라보는 주소 공간
→ 논리 주소 공간
사용자는 물리 주소를 몰라도 논리 주소를 알면 물리 주소에 접근할 수 있음.
메모리에는 운영체제와 다 수의 프로세스가 올라옴.
운영체제를 위한 공간은 따로 만들어 사용자 프로세스가 운영체제에 침범 할 수 없도록 운영체제 공간과 사용자 프로세스 공간을 나누는 경계 레지스터를 만듦.
경계 레지스터는 CPU내에서 존재하는 레지스터로 메모리 관리자는 사용자 프로세스가 경계 레지스터의 값을 벗어 났는지 확인하고, 침범했다면 사용자 프로세스를 종료 시킴.

절대 주소와 상대 주소

상대 주소
- 개발자가 프로그램 개발 시 주소는 신경 쓰지 않고 개발.
- 이는 컴파일러가 메모리 0번지에서 실행한다고 가정.
  → 상대 주소(논리 주소 공간)
절대 주소
- 실제 프로그램이 올라간 주소
  → 절대 주소(물리 주소 공간)
사용자가 0x100번지 데이터를 요청하면, CPU도 0x100번지(상대 주소, 논리 주소)의 데이터를 요청. 그리고 메모리 관리자는 CPU가 요청한 0x100번지의 주소와 재배치 레지스터에 있는 프로그램이 올라간 주소(e.g. 0x4000)의 값을 더해 0x4100번지(절대 주소, 물리 주소)에 접근해서 데이터를 가져옴.
- 재배치 레지스터에는 프로그램이 시작된 주소가 저장 되어 있음.
- 메모리 관리자 덕분에 사용자는 모든 메모리는 0x0번지에 시작한다고 가정할 수 있고, 시작 영역이 바뀌더라도 재배치 레지스터만 변경해 하면 되므로 굉장히 유연.

메모리 할당 방식

메모리 오버레이(Memory overlay)
- 메모리 보다 더 큰 프로그램을 실행 시키는 방법.
- 큰 프로그램을 잘라서 당장 실행 시켜야 할 부분만 메모리에 올리고 나머지 부분은 하드 디스크에 저장(하드디스크의 스왑 영역)하는 방식.
  - 스왑
    - 스왑 영역에 있는 데이터 일부를 메모리에 가져오고, 메모리에 있는 데이터를 스왑 영역으로 옮기는 것
- 사용자는 실행 중인 프로그램만큼 메모리를 사용한다고 느끼지만 실제는 그것보다 적으므로 메모리가 큰 컴퓨터보다는 느리게 동작.
- 유니 프로그래밍에서 사용하는 방식.
가변 분할 방식(세그멘테이션)
- 프로세스의 크기에 따라 메모리를 나누는 방식.
- 한 프로세스가 메모리에 연속된 공간에 할당되기 때문에 연속 메모리 할당 이라고 함.
고정 분할 방식(페이징)
- 프로세스의 크기와 상관없이 메모리를 할당.
- 메모리 분할 크기에 따라 프로세스들을 해당 크기에 맞게 나눠서 할당하는 방식.
- 한 프로세스가 여러개로 쪼개져서 메모리에 할당 되기 때문에 비 연속 메모리 할당 이라고 함.

가변 분할과 고정 분할 방식의 장단점

가변 분할 방식
- 장점
  - 메모리에 연속된 공간에 할당 되기 때문에 낭비되는 공간인 내부 단편화가 없다.
- 단점
  - 외부 단편화 발생
    - 중간에 다른 프로세스들이 종료되고 새로운 프로세스가 실행되는 경우 새로 시작하는 프로세스가 기존 종료된 프로세스들의 메모리 합보다 같거나 작지만, 연속된 공간에 할당 할 수 없는 상황.
    - 해결방법
      - 조각모음.
      - 조각모음을 하려면 현재 메모리에서 실행되고 있는 프로세스들의 작업을 일시 중지해야하고 메모리 공간을 이동하는 작업을 해야 하기 때문에 오버헤드가 발생.
고정 분할 방식
- 장점
  - 구현이 간단하고 오버헤드가 적음.
- 단점
  - 작은 프로세스도 큰 공간에 할당 되면 내부 단편화 발생
    - 할당된 공가보다 작은 크기의 프로세스를 할당할 경우 낭비 공간이 발생.
    - 해결방법은 없어서 분할되는 크기를 조절해서 내부 단편화를 최소화.

버디 시스템

가변분할 방식과 고정 분할 방식을 혼합해 단점을 최소화 한 방법
2의 승수로 메모리를 분할해 메모리를 할당하는 방식.
예시
- 메모리 크기가 2^11승인 2024b가 존재.
- 이때 크기가 500b인 프로세스가 메모리 할당을 원함.
- 2의 승수로 500b 작은 값을 만날때까지 메모리 영역을 나눔
  - 1024 / 1024 → 1024 / 512 / 512 → 1024 / 512 / 256 / 256
  - 즉, 1024b / 512b / 256b / 256b 4가지 영역이 생성
  - 256b에는 500b의 프로세스를 할당할 수 없으니 512b 영역에 프로세스를 할당.
    - 12b가 낭비되는 내부 단편화 발생.
    - 내부 단편활가 발생되긴 하지만 많은 공간이 발생하지는 않음.
  - 해당 프로세스가 종료되어 메모리 공간 할당이 해제 되어도 근접한 메모리 공간을 합치기 쉬움
    - 2의 승수로 동일할게 나누어서 반대로 조립만 하면 큰 공간이 만들어져서 조각 모음보다 간단함
  - 1024 / 512 / 512 → 1024 / 1024 → 2024

자료구조와 알고리즘

재귀

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

재귀 함수

예시

const myFunction = (number) => {
  console.log(number);
  myFunction(number + 1);
}

myFunction(0);

이 함수는 실행하면 오류가 발생한다.

node:internal/util/inspect:765
function formatValue(ctx, value, recurseTimes, typedArray) {
                    ^

RangeError: Maximum call stack size exceeded

탈출 조건이 없어 계속 실행하다가 메모리가 부족해서 오류가 발생.

기저 조건(탈출 조건)있는 재귀함수

예시

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

myFunction(0);

콜 스택
- 함수가 호출되면서 올라가는 메모리 영역으로 스택이라고도 부름.
- 콜스택은 스택의 특성처럼 FILO(First In Last Out) 특성을 갖고 있음.
- 함수를 호출하면 콜스택에 올라가고, 함수가 종료되면 콜스택에서 제거됨.

재귀적으로 생각하기

패턴1 - 단순한 반복 실행

단순한 반복 실행을 재귀로 구현하면 반복문으로 구현했을 때보다 크게 이점은 없다.
콜스택의 공간을 많이 차지해 반복문보다 좋지 않음.

패턴2 - 하위 문제의 결과를 기반으로 현재 문제를 계산

팩토리얼 함수를 예시로 설명
예를 들어 5!의 계산을 구할때 5 * 4! 계산 방식으로 구하는 방법.
- 하위문제: 4!
- 현재 문제: 5!
팩토리얼을 반복문으로도 구현이 가능하지만, 현재 문제를 해결하는데 하위 문제가 쓰이는 것이 중요한 포인트
반복문은 상향식 계산.
재귀 함수로 구현하면 하향식 계산.
- 재귀를 사용한다고 무조건 하향식 계산은 아님.
- 상향식 계산도 가능.
- 재귀 함수의 위력은 하향식 방향 계산에서 발휘.
⇒ 재귀를 사용하는 이유

예시

배열의 모든 원소의 합.

const sumArray = (arr) => {
  if (arr.length === 1) return arr[0];
  return sumArray(arr.slice(0, -1)) + arr[arr.length - 1];
}

let arr = [1, 2, 3, 4, 5];
const res = sumArray(arr);
console.log(res);

문자열의 길이 구하기

const strLength = (arr) => {
  if (!arr[0]) return 0;

  return strLength(arr.slice(0, -1)) + 1
}

const str = 'abcde';
const res = strLength(str);
console.log(res);

지수 함수

const power = (x, n) => {
  if (n === 0) return 1;
  return power(x, n - 1) * x;
}

console.log(power(2, 5)); // 2^5 계산

하노이 탑

하향식 계산 방식의 좋은 예

정렬

배열에 무작위로 섞인 숫자를 정렬하는 방법.

버블 정렬(Bubble Sort)

가장 쉽게 생각할 수 있는 정렬중 하나
구현하는 방법은 쉬우나 성능은 좋진 않다.

예시 코드

코드

const bubbleSort = (arr) => {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < (arr.length - i - 1); j++) {
      if (arr[j] >= arr[j + 1]) {
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }
}

const arr = [4, 2, 3, 1];
console.log('> > > 정렬 전 < < <');
console.log(arr);

bubbleSort(arr);

console.log('> > > 정렬 후 < < <');
console.log(arr);

결과

> > > 정렬 전 < < <
[ 4, 2, 3, 1 ]
> > > 정렬 후 < < <
[ 1, 2, 3, 4 ]

버블 정렬의 성능

버블 정렬의 성능을 구하면 등차수열의 합과 같은 경우의 수가 나타남
- $\frac{n^2 - n}{2}$
시간 복잡도는 $O(n^2)$
- $n$이 증가할때마다 계산량은 엄청나게 증가하게 됨.
성능이 중요한 시스템을 만든다면 버블 정렬 방식은 사용하기 힘듦.

장단점

이해와 구현이 간단함.
성능이 좋지 않음.

선택 정렬(Selection Sort)

버블 정렬처럼 이해와 구현이 간단.
아쉬운 성능
배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져옴.

코드 예시

코드

const selectionSort = (arr) => {
  for (let i = 0; i < arr.length - 1; i++) {
    let minValIdx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minValIdx]) {
        minValIdx = j;
      }
    }

    const tmp = arr[i];
    arr[i] = arr[minValIdx];
    arr[minValIdx] = tmp;
  }
}

const arr = [4, 2, 1, 3];
console.log('> > > 정렬 전 < < <')
console.log(arr);

selectionSort(arr);

console.log('> > > 정렬 후 < < <')
console.log(arr);

결과

> > > 정렬 전 < < <
[ 4, 2, 1, 3 ]
> > > 정렬 후 < < <
[ 1, 2, 3, 4 ]

선택 정렬의 성능

버블 정렬과 마찬가지로 $\frac{n^2 - n}{2}$ 나타남.
성능도 마찬가지로 $O(n^2)$ 시간 복잡도를 갖고 있음.

장 단점

이해와 구현이 간단함.
성능이 좋지 않음.