'그림으로 쉽게 배우는 운영체제 2주차'

[섹션 04]

프로세스 동기화

CPU 스케줄링에서 고려해야 할 사항

CPU 스케줄러가 고려해야 할 요소는 다음과 같습니다.

1. 프로세스에게 CPU 리소스를 줘야 하는가?

   • 실행 가능한 프로세스 중에서 어떤 프로세스에 CPU를 할당할 것인지 결정.

   • 우선순위가 높은 프로세스를 먼저 실행할 것인지 고려해야 함.

2. CPU를 할당받은 프로세스가 얼마 동안 실행되어야 하는가?

   • 특정 프로세스가 너무 오랫동안 CPU를 독점하지 않도록 타임 퀀텀(Time Quantum) 을 설정.

   • 선점형(Preemptive) 스케줄링과 비선점형(Non-preemptive) 스케줄링 방식 중 선택.

CPU Burst와 I/O Burst

• CPU Burst: 프로세스가 연속적으로 CPU에서 실행되는 시간.

• I/O Burst: 프로세스가 I/O 작업을 수행하는 시간.

CPU 작업과 I/O 작업이 번갈아 가며 실행됨.

프로세스 간 통신 (IPC, Inter-Process Communication) 종류

1. 파일과 파이프(Pipe) 이용

   • 파일: 프로세스 간 데이터를 파일을 통해 공유하는 방식.

   • 파이프: 한 프로세스가 데이터를 쓰고 다른 프로세스가 읽는 구조 (ex. | 연산자).

2. 스레드(Thread) 이용

   • 같은 프로세스 내의 여러 스레드가 메모리를 공유하면서 데이터를 주고받는 방식.

3. 네트워크 이용

   • 소켓(Socket) 통신, 원격 프로시저 호출(RPC) 등을 사용하여 원격 프로세스와 데이터 교환.

RPC (Remote Procedure Call, 원격 프로시저 호출)

• 네트워크를 통해 다른 시스템에서 동작하는 프로세스의 함수를 호출하는 기법.

• 클라이언트가 마치 로컬 함수처럼 호출하면, 원격 서버에서 실행되고 결과가 반환됨.

공유 자원 & 동기화 문제

• 공유 자원(Shared Resource): 여러 프로세스가 동시에 접근할 수 있는 자원 (예: 변수, 파일).

• 동기화 문제(Synchronization Issue): 여러 프로세스가 공유 자원에 접근할 때 데이터 충돌이 발생할 위험이 있음.

임계구역 (Critical Section)

• 공유 자원에 접근하는 코드 영역.

• 한 번에 하나의 프로세스만 임계구역에 접근해야 함.

상호 배제(Mutual Exclusion) 매커니즘 요구사항 3가지

1. 단일 접근 원칙: 주어진 시간에 오직 하나의 프로세스만 임계구역에 접근 가능.

2. 동시 요청 처리: 여러 프로세스가 동시에 요청해도 한 개의 프로세스만 진입 가능.

3. 빠른 실행 보장: 임계구역에 들어간 프로세스는 최대한 빠르게 나와야 함.

세마포어 (Semaphore)

• 공유 자원의 접근을 제한하는 동기화 기법.

• 프로세스 간 상호 배제(Mutual Exclusion) 를 보장함.

세마포어 메커니즘

• P(S) (wait 연산): 세마포어 값을 감소시키고, 0이면 대기(block).

• V(S) (signal 연산): 세마포어 값을 증가시키고, 대기 중인 프로세스가 있으면 깨움.

C++ 예제

#include <iostream>
#include <semaphore.h>
#include <pthread.h>

sem_t semaphore;

void* worker(void* arg) {
    sem_wait(&semaphore); // P(S) 연산 (진입)
    std::cout << "임계구역 실행 중...\n";
    sem_post(&semaphore); // V(S) 연산 (해제)
    return nullptr;
}

int main() {
    sem_init(&semaphore, 0, 1); // 초기값 1 (binary semaphore)

    pthread_t t1, t2;
    pthread_create(&t1, nullptr, worker, nullptr);
    pthread_create(&t2, nullptr, worker, nullptr);

    pthread_join(t1, nullptr);
    pthread_join(t2, nullptr);

    sem_destroy(&semaphore);
}

세마포어를 잘못 사용할 경우 발생할 위험성

1. 데드락(Deadlock)

   • 여러 프로세스가 세마포어를 무한정 대기하면 교착 상태 발생.

2. 기아 상태(Starvation)

   • 특정 프로세스가 세마포어를 계속 점유하면, 다른 프로세스는 계속 대기해야 함.

3. 우선순위 반전(Priority Inversion)

   • 낮은 우선순위 프로세스가 세마포어를 점유하면, 높은 우선순위 프로세스가 대기할 수 있음.

모니터(Monitor)란?

• 세마포어의 단점을 해결한 상호 배제(Mutual Exclusion) 매커니즘.

• 프로그래머가 wait()과 signal()을 직접 사용하지 않고, 자동으로 동기화를 제공.

Java에서 모니터 예제

class SharedResource {
    synchronized void print() {
        System.out.println(Thread.currentThread().getName() + " 실행 중...");
    }
}

class MyThread extends Thread {
    SharedResource sr;

    MyThread(SharedResource sr) {
        this.sr = sr;
    }

    public void run() {
        sr.print();
    }
}

public class MonitorExample {
    public static void main(String[] args) {
        SharedResource sr = new SharedResource();
        Thread t1 = new MyThread(sr);
        Thread t2 = new MyThread(sr);

        t1.start();
        t2.start();
    }
}

• synchronized 키워드를 사용하면, 임계구역에 하나의 스레드만 진입할 수 있음.

• 프로그래머가 직접 세마포어를 관리할 필요 없이 안전한 동기화를 제공.

[섹션 05]

데드락

데드락(Deadlock)이란?

정의:
데드락(교착 상태)은 두 개 이상의 프로세스가 서로 상대방의 작업이 끝나기를 기다리면서 무한히 멈춰 있는 상태를 의미

예제:

• 식사하는 철학자 문제

  • 다섯 명의 철학자가 둥근 테이블에서 식사를 하려면 양옆의 포크 두 개를 동시에 집어야 한다.

  • 모든 철학자가 왼쪽 포크를 집고 오른쪽 포크를 기다리면 교착 상태(Deadlock)가 발생하여 아무도 식사를 할 수 없게 된다.

교착 상태 (Deadlock)

정의:

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

교착 상태 발생 조건 (4가지 필요조건)

데드락이 발생하려면 다음 4가지 조건이 동시에 만족해야 함
이 중 하나라도 충족되지 않으면 데드락은 발생하지 않음!!

1. 상호 배제 (Mutual Exclusion)

• 한 번에 하나의 프로세스만 특정 자원을 사용할 수 있어야 함

• 예: 한 개의 프린터를 여러 프로세스가 사용할 경우, 한 프로세스가 사용하는 동안 다른 프로세스는 대기해야 함.

2. 점유와 대기 (Hold and Wait)

• 프로세스가 이미 할당받은 자원을 보유한 채로 추가적인 자원을 기다려야 한다.

• 예: 프로세스 A는 프린터를 가지고 있고, 프로세스 B가 사용하는 스캐너를 기다리는 상황

3. 비선점 (No Preemption)

• 할당된 자원을 강제로 빼앗을 수 없음

• 즉, 자원을 점유한 프로세스가 스스로 해제할 때까지 다른 프로세스는 기다려야 한다.

4. 순환 대기 (Circular Wait)

• 프로세스들이 서로 원형(사이클) 형태로 자원을 점유하고 대기한다.

• 예:

  • A → B가 가진 자원을 기다림

  • B → C가 가진 자원을 기다림

  • C → A가 가진 자원을 기다림

  • 이처럼 순환 구조가 형성되면 데드락 발생!

데드락 해결 방법

데드락을 해결하기 위해 예방, 회피, 검출 및 복구 방법이 존재

데드락 예방 (Prevention)

• 데드락 필요조건 4가지 중 하나 이상을 제거하여 방지하는 방법
  방법:

  • 상호 배제 제거: 여러 프로세스가 동시에 자원을 공유하도록 설계

  • 점유와 대기 방지: 모든 자원을 한 번에 요청하도록 함

  • 비선점 가능하게 변경: 자원을 강제로 회수할 수 있도록 설정

  • 순환 대기 방지: 자원에 우선순위를 부여하여 순환이 생기지 않도록 설계

     

     

데드락 회피 (Avoidance)

• 시스템이 미리 안전 상태(Safe State)를 유지하며 자원 할당을 조절하는 방법
  대표적인 알고리즘:

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

    • 프로세스가 최대 자원 요청량을 미리 선언해야 함

    • 시스템은 프로세스가 요청하는 자원을 할당했을 때 데드락이 발생하지 않는지 검토한 후 할당

  • 장점
    교착 상태 예방 가능
    안전 상태에서만 자원 할당 → 시스템 안정성 증가

     

  • 단점
    프로세스가 최대 요구량을 미리 선언해야 함
    시스템이 항상 가능한 상태를 계산해야 하므로 오버헤드 발생

교착 상태 검출 및 복구

• 이미 발생한 데드락을 감지하고 해결하는 방법
  방법:

  • 자원 할당 그래프(Resource Allocation Graph, RAG) 분석

  • 교착 상태 발생 시 체크포인트로 롤백

  • 교착 상태 프로세스 강제 종료 또는 자원 선점

교착 상태 검출

1) 가벼운 교착 상태 검출

• 시스템이 주기적으로 자원 할당 그래프를 분석하여 교착 상태 가능성을 확인

2) 체크포인트 롤백 (Checkpoint Rollback)

• 마지막으로 저장한 체크포인트(Checkpoint)로 프로세스를 되돌려 교착 상태 해소

[섹션 06]

컴파일과 프로세스

프로그램이 실행되는 과정

1. 소스 코드 작성 (C, Java, Python 등)

2. 컴파일 (Compile)

   • 소스 코드를 기계어(바이너리 코드)로 변환

3. 링크 (Link)

   • 여러 개의 오브젝트 파일(.o, .obj)을 합쳐 실행 가능한 파일(.exe) 생성

4. 로드 (Load)

   • 실행 파일을 메모리에 로드

5. 실행 (Execute)

   • CPU가 프로그램 명령어 실행

     ---

   [섹션 07]

    

   메모리

    

   메모리의 종류

   

메모리 주소

1) 물리 주소 (Physical Address)

• 실제 RAM의 주소

• CPU가 직접 접근하는 주소

2) 논리 주소 (Logical Address)

• 프로그램이 보는 가상의 주소

• OS가 논리 주소를 물리 주소로 변환

재배치 레지스터 (Relocation Register)

• 논리 주소를 물리 주소로 변환하는 데 사용되는 레지스터

• 프로그램을 다른 메모리 위치로 이동해도 주소 수정 없이 실행 가능

메모리 오버레이 (Memory Overlay)

• 큰 프로그램을 작은 조각(Overlay)으로 분할하여 필요한 부분만 메모리에 적재하는 기법

• 초창기 컴퓨터에서 메모리가 부족할 때 사용

메모리 할당 방식 (2가지)

1. 고정 분할 방식 (Fixed Partitioning)

• 메모리를 고정된 크기의 블록(파티션)으로 나누고, 프로세스를 할당하는 방식

• 각 파티션 크기는 시스템 부팅 시 미리 정해짐

• 단순한 구조이지만 메모리 낭비(내부 단편화)가 발생할 수 있음

특징

• 프로세스가 할당된 크기보다 작으면 남은 공간이 낭비됨 (내부 단편화 발생)

• 파티션 크기를 변경할 수 없음

• 작은 프로세스가 들어가야 할 공간에 큰 프로세스가 오면 메모리 낭비가 발생

• 관리가 쉬운 대신 유연성이 부족

장점

• 관리가 단순함 (구현 쉬움)

• 메모리 할당/해제 속도가 빠름

• CPU 스케줄링이 단순해짐

단점

• 내부 단편화(Internal Fragmentation) 발생 → 프로세스보다 큰 파티션을 할당받으면 남는 공간이 낭비됨

• 파티션 크기를 미리 설정해야 함 → 크기 조정 불가능

• 큰 프로그램을 실행하기 어려움 (적절한 크기의 파티션이 없으면 실행 불가)

예시

2.가변 분할 방식 (Variable Partitioning)

• 프로세스가 요청하는 크기만큼 메모리를 할당하는 방식

• 동적 메모리 할당 방식 → 프로세스가 들어올 때마다 필요한 만큼만 메모리를 할당

• 메모리를 효율적으로 사용할 수 있지만, 외부 단편화 문제 발생

특징

• 메모리 크기에 맞게 프로세스를 할당하므로 내부 단편화가 없음

• 하지만 메모리가 여러 개의 작은 조각으로 나뉘어 외부 단편화 발생

• 메모리를 동적으로 관리할 수 있어 유연성이 높음

장점

• 내부 단편화 없음 → 프로세스 크기에 맞춰 메모리를 할당

• 큰 프로그램도 실행 가능 → 고정된 크기 제한이 없음

• 메모리 활용률이 높음

단점

• 외부 단편화(External Fragmentation) 발생 → 메모리 사이에 작은 빈 공간이 많아져 사용 불가

• 메모리 관리가 복잡 → 동적 할당을 위해 추가적인 관리 필요

• 메모리 검색 시간 증가 → 적절한 크기의 공간을 찾기 위해 시간이 오래 걸릴 수 있음

예시

메모리 단편화

1) 외부 단편화 (External Fragmentation)

• 메모리가 남아 있지만, 연속된 공간이 부족하여 할당 불가능한 상태

• 해결 방법: 메모리 압축(Compaction) 또는 페이징(Paging) 기법 사용

2) 내부 단편화 (Internal Fragmentation)

• 고정 분할 방식에서 할당된 공간보다 작은 프로그램이 로드될 때 남는 공간

• 해결 방법: 가변 분할 방식 사용
  

  ---

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

[섹션 03]

알고리즘

재귀함수 (Recursive Function)란?

자기 자신을 호출하는 함수를 재귀 함수라고 함
문제를 작은 부분으로 나누어 해결하는 방식으로, 주로 반복적인 구조의 문제를 해결할 때 사용

재귀 함수의 탈출 조건 (Base Case)이란?

재귀 호출이 무한히 반복되지 않도록 종료되는 조건을 기저 조건(Base Case) 이라고 함
만약 기저 조건이 없으면 무한 루프에 빠져 프로그램이 멈추지 않는 문제가 발생할 수 있음

• 재귀함수 예시: 팩토리얼 계산 c++

#include <iostream>
using namespace std;

// 팩토리얼 함수 (재귀)
int factorial(int n) {
    if (n == 0) return 1;  // 기저 조건 (탈출 조건)
    return n * factorial(n - 1);  // 재귀 호출
}

int main() {
    cout << factorial(5); // 5! = 5 * 4 * 3 * 2 * 1 = 120
    return 0;
}

factorial(0)의 경우 1을 반환하면서 재귀 호출이 종료

재귀적으로 생각하는 방법?

1. 작은 문제로 나눈다 → 현재 문제를 더 작은 문제로 분할
   2. 탈출 조건을 찾는다 → 가장 작은 입력에 대한 결과를 명확하게 정의
   3. 점화식(재귀 관계식)을 찾는다 → 현재 상태와 작은 문제 사이의 관계 정의
   4. 재귀 호출을 구현한다 → 주어진 입력에서 자기 자신을 호출하는 구조

예제: 피보나치 수열

int fibonacci(int n) {
    if (n <= 1) return n;  // 기저 조건
    return fibonacci(n - 1) + fibonacci(n - 2);  // 재귀 호출
}

fibonacci(0) = 0, fibonacci(1) = 1 → 기저 조건을 만족하면 종료

하노이 탑 문제 (Hanoi Tower)

• 세 개의 기둥과 여러 개의 원반이 있음

• 한 번에 하나의 원반만 이동 가능

• 작은 원반이 큰 원반 위에 올라가면 안 됨

재귀적 풀이
1. 가장 큰 원반을 제외한 나머지를 보조 기둥으로 이동
2. 가장 큰 원반을 목표 기둥으로 이동
3. 보조 기둥의 원반들을 다시 목표 기둥으로 이동

#include <iostream>
using namespace std;

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }
    hanoi(n - 1, from, aux, to); // n-1개를 보조 기둥으로 이동
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    hanoi(n - 1, aux, to, from); // 보조 기둥에서 목표 기둥으로 이동
}

int main() {
    hanoi(3, 'A', 'C', 'B');
    return 0;
}

정렬 알고리즘

버블 정렬 (Bubble Sort)

• 인접한 두 개의 값을 비교하여 정렬

• 가장 큰 값이 점점 오른쪽으로 이동하는 방식

시간 복잡도

• 최선(O(n)) → 이미 정렬된 경우

• 최악(O(n²)) → 완전히 뒤집힌 경우

   

   

  장점 & 단점

• 구현이 간단함

• 안정 정렬(Stable Sort)

• 시간 복잡도가 높아 비효율적

C++ 코드

#include <iostream>

using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    for (int i : arr) cout << i << " ";
    return 0;
}

선택 정렬 (Selection Sort)

• 가장 작은 값을 찾아서 앞쪽에 배치하는 방식

• 정렬된 부분과 정렬되지 않은 부분으로 나눠 진행

시간 복잡도

• O(n²) (최선, 최악 동일)

   

   

  장점 & 단점

• 비교 횟수가 일정하여 안정적

• 추가적인 메모리 사용이 적음

• 시간 복잡도가 높아 비효율적

• 안정 정렬이 아님 (같은 값의 순서가 바뀔 수 있음)

   

C++ 코드

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        swap(arr[i], arr[minIdx]);
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    for (int i : arr) cout << i << " ";
    return 0;
}

삽입 정렬 (Insertion Sort)

• 현재 원소를 정렬된 부분에 적절히 삽입하는 방식

• 버블, 선택 정렬보다 효율적

• 작은 데이터에서 성능이 좋음

시간 복잡도

• 최선(O(n)) → 거의 정렬된 경우

• 최악(O(n²)) → 역순 정렬된 경우

   

   

  장점 & 단점

   

• 정렬된 부분을 활용하여 효율적으로 정렬 가능

• 비교적 빠른 알고리즘 (특히 데이터가 거의 정렬된 경우)

• 큰 데이터에서는 비효율적

C++ 코드

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    for (int i : arr) cout << i << " ";
    return 0;
}

정렬 알고리즘 비교

• 배우고 느낀점

한 주가 지났다고 벌써 운영체제 앞부분의 기억이 희미해져서 강의를 보면서 다시 앞부분 내용을 일부 확인하는 과정이 있었습니다.. 복습을 다시 해야겠다는 생각을 하게 됐습니다.

CS를 알아야 컴퓨터의 모든 실행 과정(메모리 할당 및 컴파일 과정)을 알 수 있다는 것을 다시 한번 느끼게 되었습니다.

처음 접한 단어들이 많아서 다시 한번 학습해야 할 것 같습니다.

• 어려웠던 점

수학 지식이 부족해서 시간복잡도를 이해하기 힘들었습니다. (어떤게 빠르고 어떤게 느린건지)

전 주에 들었던 강의 내용을 일부만 기억해서 이번 과정을 이해하는데 힘들었습니다.

• 앞으로 개선할 점

운영체제 초반부분부터 다시 복습하기..

코드 구현 시 혼자 생각하면서, 구현 절차를 먼저 생각하는 데에 시간을 많이 소모한 후 구현하기

=> 먼저 구현하면서 구현 과정 중 생각하기 X