인프런 워밍업 클럽 스터디 3기 - CS 전공지식 <2주차 발자국>
'그림으로 쉽게 배우는 운영체제 2주차'[섹션 04]프로세스 동기화CPU 스케줄링에서 고려해야 할 사항CPU 스케줄러가 고려해야 할 요소는 다음과 같습니다.프로세스에게 CPU 리소스를 줘야 하는가?실행 가능한 프로세스 중에서 어떤 프로세스에 CPU를 할당할 것인지 결정.우선순위가 높은 프로세스를 먼저 실행할 것인지 고려해야 함.CPU를 할당받은 프로세스가 얼마 동안 실행되어야 하는가?특정 프로세스가 너무 오랫동안 CPU를 독점하지 않도록 타임 퀀텀(Time Quantum) 을 설정.선점형(Preemptive) 스케줄링과 비선점형(Non-preemptive) 스케줄링 방식 중 선택.CPU Burst와 I/O BurstCPU Burst: 프로세스가 연속적으로 CPU에서 실행되는 시간.I/O Burst: 프로세스가 I/O 작업을 수행하는 시간.CPU 작업과 I/O 작업이 번갈아 가며 실행됨.프로세스 간 통신 (IPC, Inter-Process Communication) 종류파일과 파이프(Pipe) 이용파일: 프로세스 간 데이터를 파일을 통해 공유하는 방식.파이프: 한 프로세스가 데이터를 쓰고 다른 프로세스가 읽는 구조 (ex. | 연산자).스레드(Thread) 이용같은 프로세스 내의 여러 스레드가 메모리를 공유하면서 데이터를 주고받는 방식.네트워크 이용소켓(Socket) 통신, 원격 프로시저 호출(RPC) 등을 사용하여 원격 프로세스와 데이터 교환.RPC (Remote Procedure Call, 원격 프로시저 호출)네트워크를 통해 다른 시스템에서 동작하는 프로세스의 함수를 호출하는 기법.클라이언트가 마치 로컬 함수처럼 호출하면, 원격 서버에서 실행되고 결과가 반환됨.공유 자원 & 동기화 문제공유 자원(Shared Resource): 여러 프로세스가 동시에 접근할 수 있는 자원 (예: 변수, 파일).동기화 문제(Synchronization Issue): 여러 프로세스가 공유 자원에 접근할 때 데이터 충돌이 발생할 위험이 있음.임계구역 (Critical Section)공유 자원에 접근하는 코드 영역.한 번에 하나의 프로세스만 임계구역에 접근해야 함.상호 배제(Mutual Exclusion) 매커니즘 요구사항 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); } 세마포어를 잘못 사용할 경우 발생할 위험성데드락(Deadlock)여러 프로세스가 세마포어를 무한정 대기하면 교착 상태 발생.기아 상태(Starvation)특정 프로세스가 세마포어를 계속 점유하면, 다른 프로세스는 계속 대기해야 함.우선순위 반전(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가지 조건이 동시에 만족해야 함이 중 하나라도 충족되지 않으면 데드락은 발생하지 않음!! 상호 배제 (Mutual Exclusion)한 번에 하나의 프로세스만 특정 자원을 사용할 수 있어야 함예: 한 개의 프린터를 여러 프로세스가 사용할 경우, 한 프로세스가 사용하는 동안 다른 프로세스는 대기해야 함.2. 점유와 대기 (Hold and Wait)프로세스가 이미 할당받은 자원을 보유한 채로 추가적인 자원을 기다려야 한다.예: 프로세스 A는 프린터를 가지고 있고, 프로세스 B가 사용하는 스캐너를 기다리는 상황비선점 (No Preemption)할당된 자원을 강제로 빼앗을 수 없음즉, 자원을 점유한 프로세스가 스스로 해제할 때까지 다른 프로세스는 기다려야 한다.순환 대기 (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]컴파일과 프로세스프로그램이 실행되는 과정 소스 코드 작성 (C, Java, Python 등)컴파일 (Compile)소스 코드를 기계어(바이너리 코드)로 변환링크 (Link)여러 개의 오브젝트 파일(.o, .obj)을 합쳐 실행 가능한 파일(.exe) 생성로드 (Load)실행 파일을 메모리에 로드실행 (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을 반환하면서 재귀 호출이 종료 재귀적으로 생각하는 방법?작은 문제로 나눈다 → 현재 문제를 더 작은 문제로 분할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
.png?w=560)
