inflearn logo
강의

강의
N
챌린지

챌린지
멘토링

멘토링
N
클립

클립
로드맵

로드맵
지식공유

인프런 워밍업 클럽 스터디 3기 - CS 전공지식 <2주차 발자국>

jinwoo2511
1

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

[섹션 04]

프로세스 동기화

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

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

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

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

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

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

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

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

CPU Burst와 I/O Burst

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

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

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

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

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

  2. 스레드(Thread) 이용

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

  3. 네트워크 이용

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

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

공유 자원 & 동기화 문제

임계구역 (Critical Section)

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

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

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

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

세마포어 (Semaphore)

세마포어 메커니즘

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)란?

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


[섹션 05]

데드락

 

데드락(Deadlock)이란?

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

예제:

 

교착 상태 (Deadlock)

정의:


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

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

 

  1. 상호 배제 (Mutual Exclusion)

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

  1. 비선점 (No Preemption)

  1. 순환 대기 (Circular Wait)

 

데드락 해결 방법

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

 

데드락 예방 (Prevention)

데드락 회피 (Avoidance)

 

교착 상태 검출 및 복구

교착 상태 검출

1) 가벼운 교착 상태 검출

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

[섹션 06]

컴파일과 프로세스

프로그램이 실행되는 과정

 

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

  2. 컴파일 (Compile)

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

  3. 링크 (Link)

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

  4. 로드 (Load)

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

  5. 실행 (Execute)

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

    [섹션 07]

     

    메모리

     

    메모리의 종류

    image

 

메모리 주소

1) 물리 주소 (Physical Address)

2) 논리 주소 (Logical Address)


재배치 레지스터 (Relocation Register)

메모리 오버레이 (Memory Overlay)

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

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

특징

장점

단점

예시

image

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

특징

장점

단점

 

예시

image

메모리 단편화

1) 외부 단편화 (External Fragmentation)

2) 내부 단편화 (Internal Fragmentation)

 

 

 

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

[섹션 03]

알고리즘

 

 

재귀함수 (Recursive Function)란?

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

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

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

#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)

시간 복잡도

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)

시간 복잡도

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)

시간 복잡도

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

 

정렬 알고리즘 비교

image

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

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

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

 

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

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

 

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

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

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

답변 0