운영체제

프로세스 동기화

프로세스 간 통신

한 컴퓨터 내에서 프로세스 간에 통신은 어떻게 할까?

• 운영체제가 만든 파이프를 통해 통신

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

• 네트워크를 이용한 통신

  • 소켓 통신 (운영체제가 제공)

  • RPC 통신 (다른 컴퓨터에 있는 함수를 호출 - 원격 프로시저 호출)

  공유자원과 임계구역

• 공유자원

  • 여러 프로세스가 공유하는 변수나 파일

  • 여러 프로세스가 공유하기 때문에 순서에 따라서 값이 다를 수 있음

  • 컨텍스트 스위칭으로 실행되기 때문에 누가 먼저 실행되는지 알수가 없거나 어렵다

  • 따라서 연산 결과를 예측하기 어렵다

  • 여기서 발생하는 문제가 동기화 문제

• 임계구역

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

  • 이 문제를 해결하려면 상호 배제 매커니즘이 필요

   

  상호 배제 매커니즘

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

동시에 여러 요청이 와도 하나의 프로세스만 접근한다

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

세마포어

열쇠 관리자가 열쇠를 가지고 있고 열쇠를 한 명한테만 준다

• 프린터: 공유자원

• 프린터를 사용하려는 지원들: 프로세스

• 프로세스들이 기다리는 공간: 대기 큐

• 열쇠 관리자: 운영체제

• 열쇠: 세마포어

실제로 세마포어는 정수형 변수로 여러 개의 열쇠를 가질 수 있다.

예를 들어 공유자원이 2개라면 열쇠도 2개다.

단, 열쇠 제공과 반납을 이상하게 호출해서 잘못 사용할 수도 있다는 단점이 있다.

// 임계 영역 진입 전
semaphore.wait();

try {
    // 임계 영역 코드
} finally {
    // 임계 영역 퇴출 시
    semaphore.signal();
}

이런식으로 항상 wait()과 signal() 은 쌍으로 호출되어야 하는데 연속으로 각각의 것을 호출하면 안된다.

• 연속으로 wait()를 호출한 경우 > 데드락 발생

• 연속으로 signal()를 호출한 경우 > 자원 낭비

모니터

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

운영체제가 아닌 프로그래밍 언어에서 자체 지원한다.

명시적으로 wait()과 signal() 를 호출하지 않아도 자동으로 됨

Java에서는 synchronized 키워드를 통해 모니터를 구현한다.

public class BoundedBuffer {
    private final int[] buffer = new int[5];
    private int count = 0;
    private int in = 0;
    private int out = 0;
    
    // synchronized 키워드로 상호배제 보장
    public synchronized void produce(int item) throws InterruptedException {
        // 버퍼가 가득 찼다면 대기
        while (count == buffer.length) {
            wait();  // 다른 스레드가 notify할 때까지 대기
        }
        
        buffer[in] = item;
        in = (in + 1) % buffer.length;
        count++;
        
        notify();  // 대기 중인 소비자에게 알림
    }
    
    public synchronized int consume() throws InterruptedException {
        // 버퍼가 비었다면 대기
        while (count == 0) {
            wait();  // 다른 스레드가 notify할 때까지 대기
        }
        
        int item = buffer[out];
        out = (out + 1) % buffer.length;
        count--;
        
        notify();  // 대기 중인 생산자에게 알림
        return item;
    }
}

데드락

공유자원을 서로 차지하려다가 발생하는 교착 상태

• 식사하는 철학자 문제

  • 5명의 철학자가 원형 테이블에 앉아있고 각 철학자 사이에 포크가 1개씩 있다

  • 철학자는 양쪽의 포크 (2개)가 필요하다

  • 포크는 한 번에 한 사람만 사용할 수 있다.

모든 철학자가 동시에 왼쪽 포크를 잡으면 > 오른쪽 포크를 집으려고 모두가 대기 > 아무도 식사를 시작할 수 없는 교착상태가 발생

• 교착상태의 필요조건

  • 상호배제: 먼저 리소스를 차지했다면 다른 프로세스가 사용할 수 없음

  • 비선점: 한번 차지한 리소스는 다른 프로세스가 빼앗을 수 없음

  • 점유와 대기: 리소스를 가진 상태에서 다른 리소스를 기다림

  • 원형 대기: 점유와 대기를 하는 프로세스들이 원형을 이룬다

  이 중 한가지라도 충족되지 않으면 교착상태가 발생하지 않는다

   

  해결하는 법

• 교착상태 회피

  • 어느 정도 할당해야 교착상태가 발생하지 않는지 파악해서 할당

  • 전체 자원의 수, 할당된 자원의 수로 안정상태와 불안정 상태를 나눔

  • 불안정 상태에 있더라도 무조건 교착상태인 것은 아니지만 교착상태가 될 확률이 높다

     

• 교착상태 검출

  • 가벼운 교착상태 검출

    • 프로세삭 일정시간 동안 진행되지 않으면 교착상태라고 간주

    • 일정 시점마다 체크포인트를 만들어서 저장하고 타임아웃이 나면 롤백

  • 무거운 교착상태 검출

    • 자원 할당 그래프를 이용

    • 운영체제가 어떤 프로세스를 쓰는지 지켜보다가 문제가 발생하면 해결

    • 계속 지켜봐야 하기 때문에 오버헤드가 발생함

    • 억울하게 종료되는 프로세스는 발생하지 않음

       

       

  컴파일

  코드를 기계어로 바꿔서 실행파일로 만드는 것

• 컴파일을 할 때 타입, 문법을 검사한다

• 속도가 빠르다

• C, C++, C#

코드 > 전처리기 > 컴파일러 > 어셈블러 > 링커 > 실행파일 완성!

인터프리터

컴파일 과정이 없고 코드를 한 줄 씩 해석해서 실행하는 것

• 미리 검사를 하지 않기 때문에 에러가 발생할 수 있음

• 속도가 느리다

• JavaScript, Python, Ruby

   

   

  메모리

• 레지스터

휘발성 메모리

32bit, 64bit == 레지스터의 크기

CPU는 레지스터에 있는 값을 가져와서 메인 메모리에 저장한다

CPU가 사용하는 메모리로 엄청나게 빠르다

• 캐시

휘발성 메모리

RAM이 너무 느려서 미리 데이터를 가져다 둘 곳이 필요해서 생김

가장 속도가 빠른 순서로 나열하면 L1 캐시 > L2 캐시 > 메인메모리

• 메인메모리 (RAM)

휘발성 메모리

가장 중요한 메모리로 실제 운영체제 및 다른 프로세스들이 올라가는 곳

가격이 매우 비싸서 데이터를 저장하는 게 아닌 실행 중인 프로그램만 올라간다

• 보조저장장치 (HDD, SSD) 

비휘발성 메모리

게임, 파일 등을 저장할 때 사용한다

왜 다른데에 저장 안하냐? > 너무 비싸서 다른애들은 가성비가 좋지 않음

메모리와 주소

RAM을 관리하려고 운영체제가 메모리를 1바이트씩 나누고 구역에 이름을 매김 == 주소

• 논리주소

  • 프로세스가 바라보는 메모리 주소

  • 0번지로 시작하는 연속된 메모리 공간으로 보임 (가상)

  • 각 프로세스마다 독립된 주소 공간을 가짐

• 물리주소

  • 실제 RAM의 하드웨어 주소

  • 모든 프로세스가 공유하는 실제 메모리 공간

• 절대주소

  • 고정된 메모리 위치

  • 재배치가 불가

• 상대주소

  • 재배치가 가능한 상대적인 주소

• 경계 레지스터

  • 레지스터 공간에서 운영체제가 있는 공간(커널 공간)이랑 사용자 공간을 나누었는데

  • 이 경계를 지키는게 경계 레지스터

메모리 접근 과정

프로세스의 논리주소 > 재배치 레지스터로 주소 변환 > 물리 메모리에 접근

메모리 할당 방식

• 유니 프로그래밍 방식

[시스템 메모리 구조]

물리 메모리(RAM)
┌─────────────┐
│ Process A   │
├─────────────┤
│ Process B   │    ↔️    [스왑 영역(디스크)]
├─────────────┤           ┌─────────────┐
│ Process C   │           │ Process D   │
└─────────────┘           └─────────────┘

메모리 오버레이 > 큰 프로그램을 메모리에 올릴 때 일부만 메모리에 올리고 일부는 하드디스크에 저장했음

메모리에 올릴 때는 하드디스크 내부 스왑 영역에 올림

스왑 과정이 있기 때문에 실제 메로리가 큰 컴퓨터 보다는 느리게 동작한다

• 멀티 프로그래밍 방식

가변 분할 방식 (Segmentation)

프로세스의 크기에 따라 메모리를 나누는 방법 > 연속된 메모리를 할당

연속된 공간에 딱 맞게 할당 되어서 내부 단편화가 없음

대신 외부 단편화가 발생

- 외부 단편화란?

메모리의 빈 공간들이 있지만 프로세스의 크기보다 각각 작아서 할당되지 못하는 문제

해결하려면 메모리 조각 모음을 하면 되는데 조각 모음을 할 때는 실행 중인 프로세스들을 일시 중지 시켜야 해서 오버헤드가 발생한다

- 내부 단편화란?

프로세스의 크기보다 큰 메모리에 프로세스가 할당되어서 낭비 공간이 발생하는 것

고정 분할 방식 (Paging)

프로세스의 크기와 상관없이 메모리를 할당 > 한 프로세스가 메모리에 분산되어서 할당됨 > 비연속 할당

구현이 간단하고 오버헤드가 적음

작은 프로세스도 큰 메모리에 할당 되기 때문에 낭비공간이 생김 > 내부 단편화 현상 있음

버디 시스템

가변 분할 방식과 고정 분할 방식을 혼합해서 단점을 최소화 한 방식

2의 승수로 메모리를 분할해서 메모리를 할당

각 분할된 영역은 "버디(짝)"를 가지며, 인접한 두 버디가 모두 가용 상태면 합칠 수 있다.

가변 분할 방식처럼 프로세스 크기에 따라 메모리의 크기가 달라지면서 외부 단편화를 방지하기 위해서 메모리를 확보하는 것이 간단

• 왜 간단할까?

  • 원래는 메모리 빈 공간 크기가 제각각이어서 이동 위치 계산이나 주소 재배치가 복잡했음

  • 버디 시스템에서는 조각들이 모두 2의 승수 크기이기 때문에 버디끼리만 합치면 된다

     

내부 단편화가 발생하긴 하지만 그 공간이 매우 작음

자료구조와 알고리즘

재귀

자기 자신을 참조하는 것으로 꼭 종료 조건(기저 조건)이 있어야 한다.

• 콜스택

First In Last out

함수를 호출하면 콜스택에 올라가고 종료되는 콜스택에서 제거됨

isStackOverflowError 는 기저 조건 없이 실행되어 콜 스택이 꽉 차서 오류난 것

• 재귀적으로 생각하기

재귀함수를 쉽게 작성하려면 재귀함수가 이미 구현되어있다고 생각하고 하위 문제의 결과를 기반으로 현재 문제의 계산을 구성한다. > 하향식 계산 (가장 큰 문제에서 시작하여 작은 문제로 나누어 해결하는 방식)

return number * factorial(number - 1);
                // 이 부분은 이미 구현되어있다고 생각한다

• 상향식 계산과 하향식 계산

function factorial2(number, i = 1, sum = 1) {
  if(i > number) return sum;
  return factorial2(number, i + 1, sum * 1)
} // 상향식 계산 (재귀)

재귀를 이용한다고 해서 모두 하향식 계산인 것은 아니다.

이렇게 재귀를 사용해서도 상향식 계산을 할 수 있지만 하향식은 재귀로만 가능함

상향식 재귀는 성능이 좋지 않으므로 하향식으로 하는게 좋다.

정렬

버블정렬

구현이 쉽지만 성능이 그렇게 좋지 않음

두 개를 비교해서 큰 애를 뒤로 보내는 방식

한 번 순회가 끝나면 마지막 원소는 이미 끝났으니 제외해야 한다

• 구현

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;
            }
        }
    }
}

• 성능

바깥 쪽 For문이 돌 때마다 가장 큰 원소가 하나씩 정렬된다.

안쪽 For문은 그 갯수가 하나씩 줄어든다.

자연수는 버리고 가장 높은 차수를 선택하면 Big(O)는 O(n²)가 된다.

대강 For문 2개가 중첩이면 O(n²)라고 생각하면 된다.

선택정렬 

이해와 구현이 간단하지만 성능이 떨어짐

첫 번째 원소에서 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져온다 

• 구현

function selectionSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        let minValueIndex = i;
        
        // 수정된 부분: j는 i+1부터 시작해야 한다
        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;
        console.log(arr);
    }
}

처음에 직접 써봤는데 let j를 i 부터 시작해서 계속 원하는 결과가 나오지 않았음

한 번 순회를 돌면 최소값은 찾아진 것이므로 걔를 제외하고 해야한다!

• 성능

똑같이 시간 복잡도는 O(n²)

회고

👏 칭찬하고 싶은 점

일이 많이 바빴는데 밀리지 않고 듣고 정리해 두었다

구현을 직접 해보고 오류가 나면 스스로 해결해 보았다

😅 아쉬웠던 점

바빠서 운영체제 같은 경우에는 완벽하게 이해를 하지 못했는데 넘어간 부분이 좀 있었다

🔄 보완하고 싶은 점

강의를 한 번 듣고 바로 한 번 복기를 하면 이해가 더 잘될 것 같아서 그렇게 해봐야 겠다

🎯 다음주의 목표

강의 한 번 듣고 바로 복기하면서 한 번 더 이해해보기

들으면서 드는 질문 정리해서 해보기