inflearn logo
강의

강의
N
챌린지

챌린지
멘토링

멘토링
N
클립

클립
로드맵

로드맵
지식공유

[인프런 워밍업 클럽 3기 CS전공지식] 2주차 발자국

영욱
1

1일차

프로세스 동기화와 통신,재귀

 

프로세스 간 통신

프로세스는 독립적으로 실행될 수도 있지만 다른 프로세스와 데이터를 주고받으며 통신하기도 합니다.

통신 방식은 한 컴퓨터 내의 프로세스 간 통신과 네트워크를 통해 다른 컴퓨터의 프로세스와 통신하는 방법으로 나눌 수 있습니다.

 

프로세스 간 통신 방법

  1. 파일(File) 이용

    • 통신하려는 프로세스들이 공통된 파일을 이용하여 데이터를 읽고 씁니다.

  2. 파이프(Pipe) 이용

    • 운영체제가 생성한 파이프를 통해 데이터를 읽고 쓰는 방식입니다. 한 프로세스가 파이프에 데이터를 쓰면, 다른 프로세스가 이를 읽습니다. 

쓰레드를 이용한 통신

네트워크를 이용한 통신

 

 

공유 자원과 임계 구역

공유 자원

경쟁 조건 (Race Condition)

**임계 구역 (Critical Section)

여러 프로세스가 동시에 접근하면 안 되는 코드 영역을 임계 구역이라 합니다.

 

임계 구역 문제 해결 - 상호 배제 매커니즘(Mutual Exclusion)

 

 

프로세스 동기화 기법

세마포어 (Semaphore)

**교착 상태 : 여러 프로세스가 서로 필요한 자원을 기다리면서 무한정 대기하는 상태입니다. 세마포어의 wait() 함수를 잘못 사용하면 교착 상태가 발생할 수 있습니다.

**경쟁 상태 : 세마포어의 signal() 함수를 잘못 사용하면 여러 프로세스가 동시에 임계 구역에 접근하여 데이터 불일치 등의 문제가 발생할 수 있습니다.

 

세마포어의 사용 코드 예제(JAVA)

    public static void main(String[] args) throws InterruptedException {
        Semaphore semaphore = new Semaphore(1);
        semaphore.acquire(); // acqurie()는 wait()과 같은 역할을 담당
        System.out.println("wait 실행");
        semaphore.release(); // release()는 signal()과 같은 역할을 담당
        System.out.println("signal 실행");
    }

 

모니터 (Monitor)

 

그럼 세마포어의 문제점을 보완한게 모니터니까 모니터를 사용하는게 가장 좋은건가??

모니터의 사용 코드 예제(JAVA)

    public static void main(String[] args) {
        Object lock = new Object(); // 락으로 사용할 객체
        synchronized (lock) {
            // 락이 있을경우 해당 메서드에 진입해 실행
            System.out.println("Inside synchronized block.");
            //실행문 종료 후 별다른 명령어 없이 자동으로 lock 반납
        }
    }

 

 

뮤텍스 (Mutex)

뮤텍스의 사용 코드 예제(JAVA)

    public static void main(String[] args) {
        ReentrantLock lock = new ReentrantLock(); 
        lock.lock(); // lock 활성화
        System.out.println("Lock acquired.");
        lock.unlock(); // lock 반납
        System.out.println("Lock released.");
    }


재귀 (Recursion)

재귀란?

재귀 함수의 종료 조건

**콜 스택 (Call Stack)

 

재귀, 반복문

// 반복문
int sum = 0;
for (int i = 1; i <= n; i++) {
    sum += i;
}

// 재귀 함수
int recursiveSum(int n) {
    if (n == 1) {
        return 1;
    }
    return n + recursiveSum(n - 1);
}

 

팩토리얼 예제(JAVA)

public class FactorialExample {
    public static int factorial(int n) {
        if (n == 1) return 1; // 탈출 조건
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5)); // 120 출력
    }
}

2일차

프로세스 동기화와 통신,재귀

 

교착상태 (Deadlock)

교착상태란?

교착상태(Deadlock)는 여러 프로세스가 서로 다른 프로세스가 보유한 자원을 기다리며 무한히 대기하는 상태를 의미합니다. 이 상태에 빠지면 어떤 프로세스도 작업을 진행하지 못하게 됩니다.

 

 

교착상태의 필요조건

교착상태가 발생하기 위한 4가지 필요조건이 있으며, 이 중 하나라도 충족되지 않으면 교착상태가 발생하지 않습니다.

  1. 상호 배제 (Mutual Exclusion)

    • 어떤 자원이 한 프로세스에 의해 점유되었다면, 그 자원은 다른 프로세스와 공유되지 않아야 함.

  2. 비선점 (No Preemption)

    • 다른 프로세스가 점유한 자원을 강제로 빼앗을 수 없어야 함.

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

    • 어떤 프로세스가 자원을 점유한 상태에서 추가 자원을 기다려야 함.

    • 즉, 이미 할당된 자원을 보유하면서 다른 자원을 요청하고 대기하는 상태여야 합니다.

  4. 원형 대기 (Circular Wait)

    • 점유와 대기 상태의 프로세스들이 원형으로 연결되어 있어야 함.

    • 예를 들어, 프로세스 A는 프로세스 B가 가진 자원을 기다리고, 프로세스 B는 프로세스 C가 가진 자원을 기다리고, 프로세스 C는 프로세스 A가 가진 자원을 기다리는 식입니다.

 

 

교착상태 해결 방법

교착 상태는 여러 프로세스가 서로 필요한 자원을 기다리며 무한히 대기하는 상황을 의미합니다. 이러한 교착 상태를 해결하기 위한 다양한 방법 중 하나가 바로 **교착 상태 회피입니다.

**교착 상태 회피란?

** 은행가 알고리즘의 특징

안정 상태의 예시

자원 할당 순서

불안정 상태의 예시

자원 할당 상태

 

 

교착상태가 발생한지 알아내는 방법

 

**자원 할당 그래프

자원할당 그래프의 사이클이 존재하는 지 그림으로 확인

image해당 그림처럼 프로세스와 자원 간의 사이클이 존재한다면 교착상태이고

 

image해당 그림처럼 프로세스와 자원간의 사이클이 없으면 교착상태가 아니다

하지만 사이클이 있어도 교착상태에 안걸리는 경우도 존재하는데
imageP2와 P4가 작업을 완료하고 자원을 반납하면

  1. R1과 R2의 자원을 반납

  2. P1과 P3가 필요한 자원을 얻을 수 있음.

  3. 원형 대기 상태가 깨지므로 교착상태가 해소됨.

 

 

재귀적으로 생각하기

 

패턴 1: 단순 반복의 재귀적 구현 (비효율적)

반복문으로 간단하게 해결할 수 있는 문제를 재귀 함수로 구현하는 것은 일반적으로 비효율적입니다.
재귀 호출은 콜 스택 공간 사용을 발생시키므로 단순 반복 작업은 for 문을 사용하는 것이 좋습니다.

// 반복문 (효율적)
public static int sum1(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

// 재귀 함수 (비효율적)
public static int sum2(int n) {
    if (n == 1) {
        return 1;
    }
    return n + sum2(n - 1);
}

 

패턴 2: 하위 문제 기반 문제 해결 (하향식 vs. 상향식)

재귀는 하위 문제의 결과를 기반으로 현재 문제를 해결하는 데 특히 유용합니다. 대표적인 예가 팩토리얼 계산입니다.

재귀함수를 이용한 팩토리얼 자바코드 예시

public static int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

for문을 이용한 팩토리얼 자바코드 예시

public static int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

 

재귀와 반복문

 

재귀와 for문을 이용해 배열의 합 구현

// 재귀 함수
public static int arraySum(int[] arr, int n) {
    if (n == 0) {
        return 0;
    }
    return arr[n - 1] + arraySum(arr, n - 1);
}

// 반복문
public static int arraySum(int[] arr) {
    int total = 0;
    for (int num : arr) {
        total += num;
    }
    return total;
}

 

문자열 길이 계산

    public static int strLength(String arr) {
        if (arr == null || arr.isEmpty()) { 
            return 0;
        }
        return strLength(arr.substring(1)) + 1;
    }

 

 

지수 함수 하향식 구현

public static int power(int x, int y) {
    if (y == 0) {
        return 1;
    }
    return x * power(x, y - 1);
}

 

3일차

컴파일과 프로세스, 재귀 - 하노이 탑

 

컴파일과 프로세스

프로그래밍 언어의 종류

프로그래밍 언어는 컴파일 언어와 인터프리터 언어로 구분할 수 있습니다.

 

 

컴파일 언어로 작성된 파일이 프로세스가 되기까지

C 언어로 작성된 test.c 파일이 실행 파일이 되고, 최종적으로 프로세스가 되는 과정

1. 컴파일 과정

  1. 전처리

    • 컴파일러가 실행되면 가장 먼저 전처리기가 동작합니다.

    • 전처리기는 #include, #define 등 전처리 구문을 처리합니다.

    • 주석 제거를 수행한 후 전처리된 코드를 .i 파일로 저장합니다.

  2. 컴파일

    • 전처리된 코드를 기계어에 가까운 어셈블리어로 변환합니다.

    • 이 과정에서 문법 오류 체크도 함께 이루어집니다.

    • 결과물은 어셈블리 코드가 담긴 .s 파일입니다.

  3. 어셈블

    • 어셈블리어를 기계어 코드(오브젝트 코드)로 변환합니다.

    • 생성된 오브젝트 파일은 .o 확장자를 가집니다.

    • 이 오브젝트 파일에는 코드 영역과 데이터 영역이 나눠져 있습니다.

  4. 링커

 

2. 프로세스 생성 과정

실행 파일이 프로세스가 되려면 다음 과정을 거칩니다

  1. 프로그램 실행

    • 사용자가 .exe 파일을 실행합니다.

    • 운영체제가 프로세스를 생성합니다.

  2. 메모리 할당

    • 운영체제는 실행 파일에 있는 코드 영역과 데이터 영역을 가져와 프로세스의 코드 영역과 데이터 영역에 로드합니다.

    • 그리고 빈 스택(Stack)과 힙(Heap) 영역도 할당합니다.

  3. PCB 생성

    • 운영체제는 PCB를 생성하여 프로세스를 관리합니다.

    • PCB에는 프로세스 상태, 프로그램 카운터(PC), CPU 레지스터, 메모리 정보 등이 저장됩니다.

  4. 프로그램 카운터 설정

    • 프로그램 카운터(PC) 는 다음 실행할 명령어의 주소를 가리킵니다.

    • 처음에는 코드 영역의 첫 번째 명령어의 주소를 가리킵니다.

  5. CPU 스케줄링

    • 운영체제의 CPU 스케줄러가 프로세스를 준비 상태에 놓고, CPU를 할당받으면 실행 상태로 전환되어 명령어가 실행됩니다.

 

 

 

재귀-하노이탑

자바 코드 사용 예시

     public static void hanoi(int count, String from, String to, String temp) {
         if (count == 0) {
             return;
         }
         hanoi(count - 1, from, temp, to);
         System.out.println(count + "를 " + from + "에서 " + to + "로 이동");
         hanoi(count - 1, temp, to, from);
     }

     public static void main(String[] args) {
       hanoi(3, "A", "C", "B"); // 3은 옮겨야할 갯수 A는 시작위치 C는 도착해야할 위치 B는 거쳐갈 위치
     }

결과창

image

4일차

메모리 관리,버블정렬과 선택정렬

 

메모리의 종류

  1. 레지스터

    • 가장 빠른 기억 장소로 CPU 내부에 존재합니다.

    • 컴퓨터의 전원이 꺼지면 데이터가 사라지므로 휘발성 메모리입니다.

    • CPU의 32비트, 64비트는 레지스터 크기를 의미합니다.

    • CPU는 연산 시 메인 메모리(RAM)에 있는 데이터를 레지스터로 가져와 계산하고, 결과를 다시 메인 메모리에 저장합니다.

     

  2. 캐시(Cache)

    • 레지스터와 메인 메모리 사이에 위치하여, 데이터 접근 속도를 향상시키는 역할을 합니다.

    • CPU는 필요한 데이터를 메인 메모리에서 가져오기 전에 L1 캐시 → L2 캐시 → L3 캐시 순으로 확인합니다.

    • 캐시에 가져올 데이터가 없으면 메인 메모리에서 데이터를 가져옵니다.

     

  3. 메인 메모리(RAM)

     

    • 실제 운영체제와 프로세스가 로드되는 공간입니다.

    • 휘발성 메모리로, 전원이 꺼지면 데이터가 사라집니다.

    • 속도는 HDD/SSD보다 빠르지만, 가격이 비싸기 때문에 실행 중인 프로그램만 저장합니다.

     

  4. HDD/SSD

    • 비휘발성 메모리로, 전원이 꺼져도 데이터가 보존됩니다.

    • 속도는 메인 메모리보다 느리지만, 가격이 저렴하여 데이터 저장 용도로 사용됩니다.

 

 

메모리 할당 방식

메모리 오버레이:

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

    • 프로세스 크기에 따라 메모리를 연속된 공간에 동적으로 할당합니다.

    • 장점: 연속된 공간으로 할당하기 때문에 내부 단편화가 발생하지 않습니다.

    • 단점: 외부 단편화가 발생합니다.

    • 예시: 프로세스 A(50MB), B(30MB), C(15MB), D(10MB)가 메모리에 차례로 로드
      이후 A와 D가 종료되어 빈 공간(50MB + 10MB)이 생기고 새로운 프로세스 E(60MB)를 로드하려고 할 때
      이 공간들은 연속되어 있지 않아 할당할 수 없는데 이를 외부 단편화라고 하며, 조각 모음을 통해 빈 공간들을 하나로 합쳐야 합니다.
      이 과정은 메모리에 있는 프로세스를 일시 중지하고 공간을 이동시키는 작업이므로 오버헤드가 발생합니다.

     

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

    • 메모리를 고정 크기 블록으로 나눠 프로세스를 할당합니다.

    • 장점: 구현이 간단하고 오버헤드가 적습니다.

    • 단점: 프로세스 크기와 상관없이 고정된 크기로 메모리를 할당하므로 내부 단편화가 발생합니다.

    • 예시: 메모리를 2MB로 나눈다 가정할 때 프로세스 A(1MB), B(2MB), C(5MB)를 할당할 경우,
      A는 2MB 블록에 할당되어 1MB의 내부 단편화가 발생합니다.
      B는 2MB 블록에 할당되고 B는 2MB이기 때문에 정확히 떨어짐.
      C는 총 5MB이기 때문에 2MB 블록을 3개의 구역에 나눠서 저장해 1MB의 내부 단편화가 발생.

     

  3. 버디 시스템(Buddy System)

    • 가변 분할 방식과 고정 분할 방식을 혼합하여 단점을 보완합니다.

    • 메모리를 2의 제곱수 크기로 나누고, 필요할 때마다 나눠 프로세스를 할당합니다.

    • 장점: 외부 단편화를 방지하고, 메모리 합병(병합)이 간단합니다.

    • 단점: 약간의 내부 단편화가 발생할 수 있습니다.

 

그럼 메모리 할당 방식은 둘의 단점을 최소화한 버디 시스템이 최고인가??

버디 시스템의 내부 단편화와 작은 크기의 블럭을 지나치게 나누면 생기는 메모리 관리 오버헤드가 커질수있어
최신 운영체제는 페이징 기법을 활용하거나, 세그멘테이션과 조합해서 사용

페이징 기법 (Paging)

페이지 프레임과 페이지란???

페이지는 프로세스를 나눈 조각

페이지 프레임은 메모리를 나눈 조각

고정 분할 방식과 페이징 기법은 비슷하지만 고정 분할 방식은 메모리를 나눈 후 프로세스를 맞춰 넣는 방식이고,
페이징은 프로세스를 나눈 후 메모리에 퍼즐처럼 넣는 방식

 

 

세그멘테이션 (Segmentation)

요약:

 

 

 

버블 정렬과 선택 정렬

정렬 알고리즘은 데이터를 특정 순서로 나열하는 방법을 정의
버블 정렬과 선택 정렬은 가장 기본적인 정렬 알고리즘으로 이해와 구현이 쉽지만 성능은 다소 아쉬움

1. 버블 정렬 (Bubble Sort)

 

자바코드로 예시 구현

    public static void bubble(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) { // arr 배열의 길이에서 -1만큼만 반복
            for (int j = 0; j < n - i - 1; j++) { 
                if (arr[j] > arr[j + 1]) { // arr[j]번쨰 값이 arr[j]다음의 값보다 크다면
                    int temp = arr[j]; // 현재 arr[j]번째의 값을 저장해두고
                    arr[j] = arr[j + 1]; // arr[j]의 값을 arr[j] 다음의값으로 변경
                    arr[j + 1] = temp;// arr[j] 다음의값을 이전에 temp에 저장해둔 arr[j]값으로 변경
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 3, 1};
        bubble(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

image

 

 

 

2. 선택 정렬 (Selection Sort)

 

자바코드로 예시 구현

    public static void selection(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // 정렬되지 않은 부분의 첫 번째 원소를 최소값으로 가정
            // 정렬된 부분은 반복에서 제거하기위해 사용
            int minValueIndex = i;
            // 정렬되지 않은 부분에서 최소값을 찾음
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minValueIndex]) {// arr[j]값이 arr[minValueIndex] 값보다 작을경우
                    minValueIndex = j; // 정렬할 인덱스 값을 넣어주고
                }
            }

            // 최소값을 정렬되지 않은 부분의 첫 번째 원소와 교환
            int temp = arr[i]; // 현재 arr[i]의 값을 temp에 저장
            arr[i] = arr[minValueIndex]; // arr[i]의 값을 arr[minValueIndex] 변경
            arr[minValueIndex] = temp; // arr[minValueIndex]값을 이전에 temp에 저장해둔 값으로 변경
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 1, 3};
        selection(arr);
        System.out.print("실행 결과 :");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

 

 

정리


2주차 회고

 

잘한 점

저번주에 다짐했던 그날그날 강의를 듣고 정리하는건 잘지켰고 확실히 그날 배운 내용을 바로바로 정리하니 저번주보다 죽은지식이 덜했습니다.

저번주는 몰아서 정리하다보니 아 이거 뭐였지 하며 다시 찾아보고 하는 경우가 많았는데 현저히 줄어든게 느껴졌습니다.

 

아쉬운 점

운영체제는 역시 여전히 어려웠습니다.

아무래도 강의가 기본으로 쉽게 이해하려는데 초점이 맞춰져있다보니 아주 쉽게 동작원리를 알려주다보니 하나의 내용을 던져주고 궁금해서 그걸 가지고 파다보면 끝도없는 용어와 또 다른 내용이 튀어나와 역시 쉽지않았습니다.

자료구조와 알고리즘은 재귀 버블정렬 등 해당 알고리즘의 개념을 이해만 한다면 코드로 녹여내는건 생각보다 어렵지않았고 오히려 정말 재밌게 공부했었습니다.

이무래도 코드를 작성하면 시각적으로 결과가 바로바로 보여지다보니 좀더 흥미를 느꼈던거같습니다.

 

개선할 점

이제 다음주가 마지막 주차인데 이번주 보다 공부 시간을 좀 더 늘리겠습니다.

 

목표

이번주 역시 로드맵에 맞게 해당 강의 영상을 듣고 바로바로 발자국으로 내용 정리하기

2주차에 투자한 공부시간보다 더 늘리기

질문 더 많이하기

 

 

 

답변 0