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

채채 2개월 전

학습 내용

운영체제

프로세스 동기화
- 컴퓨터 내 프로세스 간 통신
  - 동일 프로세스 내 통신: 운영체제가 생성한 파이프로 데이터를 읽고 씀
  - 스레드 간 통신: 데이터 영역이나 힙 영역 사용 시 통신 가능
- 동일 네트워크 내 프로세스 간 통신
  - 소켓 통신, RPC(원격 프로시저 호출)
공유 자원: 프로세스 통신 시 공동으로 이용하는 변수나 파일
임계구역 (Critical Section): 여러 프로세스가 동시에 사용하는 영역
- 해결책: 상호 배제의 매커니즘
경쟁 조건 (Race Condition): 공유 자원을 서로 사용하기 위해 경쟁하는 것
상호 배제의 요구사항
- 임계 영역에는 동시에 하나의 프로세스만 접근
- 여러 요청에도 하나의 프로세스의 접근만 허용
- 임 영역에 들어간 프로세스는 빠르게 나와야함.
세마포어
- 공유자원이 하나 이상일 때 처리하는 동기화 방법
- 예) 프린터 실을 예시로 들때
  - 직원: 프로세스
  - 기존 프린터: 공유자원
  - 프린터실: 임계구역
  - 대기줄: 대기큐
  - 열쇠 관리자: 운영체제
  - 열쇠: 세마포어
- 자바스크립트는 멀티 스레드 환경이 아니라서 비동기 코드에서 적용할 수 있음
모니터:
세마포어의 단점을 해결한 상호배제 매커니즘
교착 상태 (데드락)
- 여러 프로세스가 서로 다른 프로세스의 작업을 기다리다가 아무도 작업을 진행하지 못하는 상태
- 필요 조건 (
  모두 충족 시 교착 상태 발생)
  - 상호 배제: A가 리소스 점유 시 B에게 공유될 수 없음 (즉, 한 번에 하나의 프로세스만 특정 자원을 사용할 수 있음)
  - 비선점: A 프로세스는 B가 점유한 리소스를 뺏을 수 없음
  - 점유와 대기: 리소스 A를 가지고 있는 상태에서 리소스 B를 원하는 상태 (무한정 대기)
  - 원형 대기: 점유와 대기를 하는 프로세스가 원형을 이룸 (서로 교차해서 자원을 기다리고 있는 상태, 모든 프로세스가 영원히 자원을 획득할 수 없음)
- 회피 방법
  - 은행원 알고리즘: 교착 상태를 피하기 위해 상태 확인 뒤 실행
    - 안정 상태: 자원 요청을 했으나 사용 가능한 자원이 더 적을 경우 요청 거부
    - 불안정 상태: 모든 프로세스에 자원을 공급할 수 없는 경우
  - 교착상태 검출
    - 가벼운 교착 상태 검출: 일정시간동안 작업하지 않을 시 교착 상태 발생으로 간주
      - 과정: 일정 시간마다 체크포인트 생성 -> 작업 저장 -> 타임 아웃으로 교착 상태 발생 시 마지막 지점으로 롤백
    - 무거운 교착 상태 검출: 운영체제가 자원 사용 여부를 지켜보고 교착 상태 발생 시 해결
      - 과정: 자원 할당 그래프 사용 -> 교착 상태 발생 시 순환 구조 형성 -> 교착 상태 해결을 위해 순환 구조 단절 -> 해결 후 재실행 시 체크포인트 롤백

컴파일 과정: 문법 오류 확인, CPU에서 처리 가능한 기계어로 실행 파일 생성 => 속도 빠름
- 대표 언어: C, C++, C#
인터프리터 과정: 코드를 한 줄씩 해석 후 변환 (미리 검사하지 않음) => 속도 느림, 오류 발생 가능성 높음
- 대표 언어: JavaScript, Python, Ruby
1. test.c → 전처리기 → 전처리 구문 처리 → test.i → 컴파일러로 어셈블리어로 변환 → test.s → 어셈블러로 오브젝트 파일 변환 → test.o → 링커에서 실행 파일로 생성 → test.exe
2. test.exe 프로그램 실행 → 운영체제가 프로세스 생성 → PCB 생성 → 프로그램 카운터를 코드 영역의 첫번째 주소로 설정 → CPU 스케줄링에 따라 프로세스 실행 → 종료
메모리 종류: 레지스터, 캐시, 메인메모리(RAM), 보조저장장치(HDD, SSD)
레지스터
- 가장 빠른 기억장소, CPU 내 존재, 휘발성 메모리, 빠름
- RAM의 값을 레지스터로 가져와서 계산 -> 계산 결과는 다시 RAM에 저장
캐시
- 레지스터에서 쓸 법한 데이터를 RAM에서 미리 가져와서 저장, 사용 완료 후 다시 RAM에 저장
보조 저장장치: 가격 저렴, 비휘발성 메모리

휘발성 메모리: 전원 공급이 없으면 데이터가 사라짐
비휘발성 메모리: 전원 공급이 없어도 데이터가 사라지지 않음

메인 메모리 RAM
- 운영체제에 프로세스가 올라가는 공간, 휘발성 메모리, 가격 비쌈
- 멀티 프로그래밍 환경에서 여러 프로그램을 올리다 보니 복잡해짐
- 운영체제는 메모리 관리를 위해 1바이트 구역으로 나누고 숫자(주소)를 매김
- 32bit 메모리
  - 레지스터 크기, 산술논리연산장치, 데이터 이동 버스 === 32bit
  - 가능한 메모리: 2³² ⇒ 4GB
- 64bit 메모리
  - 레지스터 크기, 산술논리연산장치, 데이터 이동 버스 === 64bit
  - 가능한 메모리: 2⁶⁴ ⇒ 거의 무한대
  - 32bit에 비해 한 번에 처리할 수 있는 양이 많음 → 속도가 더 빠름
- 물리주소 공간(절대 주소): 0x0번지부터 시작하는 주소공간
  - 메모리 관리자가 바라본 실제 주소
- 논리 주소 공간(상대 주소): 사용자 관점에서 바라본 주소, 물리주소를 몰라도 접근 가능
  - 메모리 어디선가 실행되겠지~~하고 컴파일러는 0번지에서 실행한다고 가정하고 컴파일함
- 경계 레지스터: 하드웨어적으로 운영체제 공간과 사용자 공간 분리
  - CPU 내 존재
  - 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 감시 (메모리 관리자)
  - 벗어났을 경우 프로세스 종료
유니 프로그래밍에서의 메모리 분리
- 당장 실행해야하는 부분만 잘라서 메모리에 올리고 나머지는 하드디스크의 스왑 영역에 저장
- 스왑: 스왑영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 이동
멀티 프로그래밍에서의 메모리 분리
- 가변 분할 방식 (Segmentation)
  - 프로세스의 크기에 따라 메모리를 나누는 방식
  - 연속 메모리 할당: 프로세스가 연속된 메모리 공간에 할당
  - 장점: 낭비 공간인 내부 단편화가 없음
  - 단점: 외부 단편화 발생
- 고정 분할 방식 (Paging)
  - 메모리를 정해진 크기로 나누는 방식
  - 예) 고정 크기가 2MB인 경우 5MB인 프로세스는 2MB + 2MB + 1MB + 낭비 공간 1MB
  - 비연속 메모리 할당: 프로세스가 여러 개로 쪼개어 여러 곳에 할당됨
  - 장점: 구현 간단, 오버헤드 적음
  - 단점: 낭비 공간 내부 단편화 발생
현대 운영체제는 가변 분할 방식과 고정 분할 방식을 혼합함
외부 단편화
- 메모리의 공간보다 프로세스의 크기가 더 큰 경우
- 해결책: 조각 모음
  - 단점: 현재 사용 중인 프로세스 전체 일시 중지, 메모리 공간을 이동시키는 작업을 해야함 ⇒ 오버헤드 발생
내부 단편화
- 메모리 공간보다 프로세스의 크기가 더 작은 경우
- 해결책: 없음
버디 시스템: 2의 승수로 메모리 분할 및 할당
- 방법
  - 2의 승수로 프로세스 크기보다 작은 값이 나올때 까지 분리 (예: 1024 - 1024(512 - 512(256 - 256)))
  - 비슷한 크기의 프로세스에 할당 (예: 512byte에 할당 (내부 단편화가 적게 발생, 실행이 끝나고 근접한 메모리와 합치기 쉬움))
- 2의 승수로 분할했기 때문에 조립만 하면 큰 공간이 만들어짐 (조각모음보다 간단함)
- 장점
  - 가변 분할: 프로세스 크기에 따라 할당되는 메모리 크기가 다름
  - 외부 단편화 방지를 위해 메모리 공간 확보가 간단함
  - 내부 단편화가 발생하나 많은 공간이 낭비되지 않음

자료구조 & 알고리즘

재귀 함수: 자기 자신을 호출하여 문제를 해결하는 함수
- 필수: 기저 조건
  - 기저 조건이 없으면 반복되는 출력으로 호출 스택의 메모리 공간이 가득 차서 자동으로 종료됨
- 기본 패턴
  - 단순 반복 계산 (예: 누적합, 누적곱, DFS 등)
  - 하위 문제의 결과를 기반으로 현재 문제 계산 (예: 팩토리얼, 피보나치 등)
- 상향식 계산: for문, 재귀 함수
- 하향식 계산: 재귀 함수만 가능
호출 스택
- 함수가 호출되면서 올라가는 메모리 영역, FILO
- 재귀함수는 모든 호출이 콜 스택에 올라가고 for문은 1개만 올라감
예) 팩토리얼

function factorial(number) {
  if (number <= 1) return 1;
  return number * factorial(number - 1)
}

console.log(factorial(4))  // 4 * 3 * 2 * 1

예) 모든 원소의 합

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

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

예) 하노이 탑

규칙
1. 한 번에 하나의 원반을 움직일 수 있다.
2. 가장 위에 있는 원반만 옮길 수 있다
3. 아래에 작은 원반이 올 수 있다.

function hanoi(count, start, target, tmp) {
  if (count === 0) return;
  hanoi(count - 1, start, tmp, target)
  hanoi(count - 1, tmp, target, start)
}

hanoi(3, 'A', 'C', 'B')

1. count - 1개의 작은 원반을 start → tmp로 옮긴다. (임시: target)
2. 가장 큰 원반을 start → target으로 옮긴다.
3. count - 1개의 작은 원반을 tmp → target으로 옮긴다 (임시: start)
4. 이전 과정을 반복하며 모든 원반을 start에서 target으로 옮긴다.
5. 모든 원반을 옮겨 count가 0이 되면 재귀를 종료한다.

버블 정렬
- 장점: 구현하기 쉬움
- 단점: 성능이 좋지 않음
- 방법: 근접한 두 개의 숫자를 비교하여 정렬되어있지 않다면 오름차/내림차 순으로 정렬한다.
- 시간 복잡도: O(n²)
버블 정렬 구현

function 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 temp = arr[j]
    	arr[j] = arr[j + 1]
    	arr[j + 1] = temp
      }
    }
  }
}

const arr = [4, 2, 3, 1]

// ===== 정렬 전 =====
console.log(arr)

// ==== 정렬 후 =====
console.log(bubbleSort(arr)

선택 정렬
- 장점: 구현하기 쉬움
- 단점: 성능이 좋지 않음
- 방법: 정렬되지 않은 영역의 첫번째 원소와 가장 작은 값의 위치 교환
- 시간 복잡도: O(n²)
선택 정렬 구현

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minValueIndex = i
	  
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minValueIndex]) {
        minValueIndex = j
      }
    }
		
    let temp = arr[i]
    arr[i] = arr[minValueIndex]
    arr[minValueIndex] = temp;
  }
}

회고

Keep
- 시간표에 따라 매일 CS 지식을 학습했다. 뿌듯
- 나머지 한 주를 잘 마무리하면 좋겠다.
Problem
- 없다
Try
- 재귀를 구현할 때 더 작은 문제로 나누는 연습을 해야할 것 같다. 기저 조건과 점화식은 바로 이해되는데 나머지가 약간 알쏭달쏭하다.