인프런 워밍업 클럽 스터디 3기 - CS 전공지식 <둘째 주 발자국>
[Day 06]
Algorithm
재귀(Recursion): 어떠한 것을 정의하는 과정에서 자기 자신을 참조하는 것.
재귀함수(Recursive Function)을 구현할 때 탈출 조건(기저 조건)을 정의해놓지 않으면 콜 스택(Call Stack)에 스택 프레임(Stack Frame)이 무제한으로 쌓이게 되어 사용이 불가능함.
Stack Overflow: Call Stack이 메모리의 잉여 용량을 초과하여 프로세스가 OS에 의해 강제 종료되는 현상.
재귀함수를 사용할 때 쉽게 해결 가능한 문제: Factorial(n)
재귀함수를 사용할 때 쉽게 해결 가능한 문제: 깊이 우선 탐색(Depth-First Search; DFS)(참고: 1, 2, 3)
Operating System
프로세스 간 / 프로세스 내 통신
프로세스 간 통신(Inter-process Communication; IPC) (참고: 1, 2, 3)
개요
통신 방식에 따른 분류
공유 메모리(Shared Memory) 방식 (참고: 1, 2, 3)
개요
여러 프로세스가 공동으로 사용할 수 있는 가상 메모리 영역을 활용해 통신하는 방식.
모든 IPC 방식 중 가장 통신 속도가 빠르다는 장점과 동기화 문제가 생기기 쉽다는 단점이 있음.
대표적인 활용 예시로 복붙이 있음(예: 워드의 텍스트를 인터넷 창에 가져오기).
일반적인 순서
UNIX 계열
부모 프로세스 생성 및 가상메모리 영역 할당.
부모 프로세스가 자신에게 할당된 메모리 영역 중 일부를 공유 메모리로 사용하겠다고 커널에 요청.
커널이 프로세스가 접근 가능한 고정 길이의 공유 메모리 영역을 생성 및 할당해 줌.
고정 길이라는 점을 왜 강조하신 걸까? -> 왜 용량 할당 기준이 다른 걸까?
(참고) 메모리 할당 방식과 동기화 문제 발생 가능성의 차이 때문임.
fork() 함수로 자식 프로세스 복제(이때 공유 메모리 주소도 복사됨).
프로세스 동기화(Process Synchronization) (※ 병형 제어(Concurrency Control)라고 부르기도 함) (참고: 1, 2, 3)
정의 및 특징
프로세스 접근 순서 및 방식을 OS의 동기화 메커니즘을 사용하여 조정하는 것.
각 프로세스가 공유 자원에 접근하는 순서는 시분할 CPU 스케줄링을 하는 OS만 알고 있으므로, OS 단위로 해결할 수밖에 없음.
대부분의 프로세스 동기화 방법은 상호 배제(Mutual Exclusion) 메커니즘의 일부 또는 전부에 기반함.
공유 메모리 방식에서 가장 발생하기 쉬운 문제지만, 다른 방식에서도 얼마든지 발생할 수 있는 문제.
동기화 문제 해결 방법 (Deadlock 해결 방법은 Day 07 참조)
Race Condition 해결 방법
뮤텍스(Mutex) (참고: 1, 2, 3)
추가 예정.
개요 및 특징
멀티프로그래밍 환경에서 Critical Section에 동시에 접근할 수 있는 프로세스의 최대 개수를 제한하기 위해 사용되는 정수형 변수(링크 내 정의를 참고해 보강함).
뮤텍스와 달리 Critical Section에 접근 가능한 프로세스 개수를 2개 이상으로 지정할 수 있다는 게 차이점!
뮤텍스=열쇠(잠긴 동안 누구도 못 감), 세마포어=미리 발급된 n개의 출입증(다 떨어진 순간 못 들어감)이 더 좋은 비유라고 생각함.
사용법 자체는 쉽지만
wait()함수와signal()함수를 잘못 사용하면 꼬일 수 있음(참고).
활용 방법
wait()함수로 세마포어의 수를 1 줄여 프로세스 하나가 Critical Section에 들어갔음을 OS에 전달함.이때 이미 세마포어가 0이라면 이후 코드는 실행되지 않음.
코드를 진행하다
signal()함수를 만나면 세마포어의 수를 1 늘려 프로세스 하나가 Critical Section에서 나갔음을 OS에 전달함.
모니터(Monitor) (참고: 1, 2, 3)
개요 및 특징
공유 자원에 대한 동시 접근을 안전하게 제어하기 위해 상호 배제와 조건 변수를 결합한 고수준의 동기화 기법(by ChatGPT o3-mini-high)
프로그래밍 언어 차원에서 여러 프로세스에서 동시에 실행될 수 없는 함수를 만드는 방식으로 구현함.
파이프(Pipe) 방식
개요
OS가 각 프로세스와 연결된 단방향 통신용 메모리 공간(=Circular Buffer)을 생성해 데이터를 전달함.
기본적으로는 바이트스트림(Bytestream) 데이터만 전달 가능하며(참고: 1, 2, 3), 다른 데이터타입을 전달하려면 직렬화(Serialization)해야 함.
부모-자식, 형제 등 통신 대상이 정해진 두 프로세스가 단방향 통신(Half Duplex)할 때 사용함(예: fork()).
양방향 통신(Full duplex)을 위해선 익명 파이프가 두 개 필요한데, 이는 구현이 복잡함.
Anonymous Pipe가 확장된 형태로, 파일 시스템에 이름이 부여된 파이프를 말함.
메세지 큐(Message Queue)
네트워크 방식
소켓
RPC
스레드 간 통신(Inter-thread Communication; ITC)
데이터 영역에 있는 전역 변수(=공유 메모리)나 힙을 이용해 통신함.
"전역 변수보단 공유 메모리라는 명칭을 선호한다." - 곰책으로 쉽게 배우는 최소한의 운영체제론
[Day 07]
Algorithm
Recursive Thinking
재귀라는 테크닉을 제대로 활용하려면 하향식(Top-down) 계산식으로 문제를 변형할 수 있어야 함.
하향식 계산 활용 1: 배열 각 원소의 총합 구하기
하위 문제: arr.length === n-1인 배열 각 원소의 총합 구하기 + 마지막 원소
하향식 계산 활용 2: 문자열 길이 계산하기
하위 문제: str.length === n-1인 문자열의 갯수 구하기 + 1
하향식 계산 활용 3: 지수함수 계산하기
하위 문제: n^m-1 * n
Operating System
교착 상태 제어(Deadlock Control)
Deadlock: 두 개 이상의 프로세스가 서로가 가진 자원의 해제를 기다리며 무한 대기하는 상태.
Deadlock의 필요조건 (넷 중 하나라도 빠지면 Deadlock이 발생·유지되지 못함)
상호 배제(Mutual Exclusion), 비선점(No Pre-emption),
점유와 대기(Hold and Wait),
원형 대기(Circular Wait)
Deadlock 해결 방안 (참고:
Deadlock Prevention (참고: 1, 2, 3)
교착상태가 애초에 일어나지 않도록 Deadlock 필요조건 중 하나를 제거하는 것.
이론적으로만 가능하고 현실적으로 불가능하거나(상호 배제 및 비선점), 유저 사용성과 시스템 유연성을 해치게 되므로(점유와 대기,
원형 대기) 현실적으로 적용 불가함.
Deadlock Avoidence
OS가 시스템 자원과 프로세스들의 현재 할당 자원 및 최대 요구 자원을 종합적으로 고려해 시스템이 되도록 안정 상태(Safe State)를 유지할 수 있는 만큼만 시스템 자원을 할당하는 것.
각 메모리의 최대 요구 CPU 리소스는 어떻게 아는 걸까?
(참고) 추정치가 아니라 상한선이다!
비용이 비싸고, 비효율적이라는 단점
교착상태 검출
가벼운 교착상태 검출
프로세스가 정해진 시간 동안 작업을 진행하지 않는다면 OS가 이를 교착상태로 판단함.
교착상태가 되면 가장 최근의 Checkpoint로 프로세스 상태를 되돌림.
오버헤드가 적지만 멀쩡한 프로세스를 롤백해버릴 수 있음.
무거운 교착상태 검출
OS가 자원 할당 그래프를 지속적으로 관찰하다가 원형 대기 상태를 발견하면 이를 교착상태로 판단함.
교착상태가 되면 가장 최근의 Checkpoint로 프로세스 상태를 되돌림.
멀쩡한 프로세스를 롤백할 일이 없지만 오버헤드가 큼.
[Day 08]
Algorithm
하노이의 탑(The Tower of Hanoi)
1883년 프랑스의 수학자 Édouard Lucas가 처음으로 발표한 게임으로, 재귀함수 예제로 활용됨.
하향식(Top-down) 접근
가장 큰 원반을 기둥 3으로 옮기기 -> 나머지 원반을 기둥 2로 옮겨야 함
그보다 작은 원반을 기둥 3으로 옮기기 -> 더 작은 나머지 원반을 기둥 2로 옮겨야 함 (이게 하위문제!)
구현하기
첫 번째 구현: 강의 보며 구현 (Done)
두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 (Done)
세 번째 구현: 리팩토링 (원반 이동 횟수 출력, 원반 이동 On/Off 기능 추가)
(Done)
마지막 구현: 익숙한 파이썬으로 구현(+리팩토링) (Done)
Operating System
컴파일과 프로세스
[Day 09]
Algorithm
정렬 알고리즘(Sorting Algorithm)
개요
대표적인 정렬 알고리즘
버블 정렬(Bubble Sort) (※ Sinking Sort라고도 함)
배열의 정렬되지 않은 영역에서 서로 인접한 두 원소 크기가 순서대로 되어 있지 않으면 서로 교환하는 방식으로 모든 원소를 정렬하는 알고리즘.
최악의 경우,
O(n^2)의 시간복잡도를 가짐.구현하기
첫 번째 구현: 강의 보며 구현 (Done)
두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현
세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현
네 번째 구현: 아무것도 안 보고 구현
마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링)
선택 정렬(Selection Sort)
배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져오는 알고리즘.
최악의 경우,
O(n^2)의 시간복잡도를 가짐.구현하기
첫 번째 구현: 강의 보며 구현 (Done)
두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현
세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현
네 번째 구현: 아무것도 안 보고 구현
마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링)
Operating System
메모리의 종류
휘발성 메모리(Volatile Memory)
종류 및 특징
개요 및 특징
CPU 내부에서 처리할 명령어나 연산의 중간 결과값 등을 일시 저장하는 임시 기억장치.
CPU 내부에는 다양한 종류의 레지스터가 있음(각 레지스터의 종류와 특징은 후술).
CPU가 연산해야 할 데이터를 RAM에서 가져와 여기에 저장한 후에 연산을 시작함.
Register의 크기가 32bit인지 64bit인지에 따라 CPU 종류가 달라짐.
종류와 특징
재배치 레지스터(Relocation Register)
논리 주소를 물리 주소로 변환하는 데 사용되는 레지스터.
프로그램을 다른 메모리 위치로 이동해도 주소 수정 없이 실행 가능함.
CPU와 메인 메모리 간 데이터 접근 속도의 차이를 최소화하기 위해 사용되는 CPU 내 고속 임시 저장소(by ChatGPT-o3-mini-high).
속도와 용량에 따라 Level 1, Level 2, Level 3 Cache로 세분화되어 탑재되어 있음(시스템마다 다름).
CPU가 자주 사용할 만한 데이터를 RAM에서 미리 가져와놓고(=Caching), CPU가 필요할 때 RAM보다 우선적으로 접근함.
Cache Hit이 많으면 시스템의 성능이 올라가겠지만 Cache Miss가 많으면 추가 Latency가 발생해 오히려 Cache Memory가 없는 시스템보다도 시스템의 성능이 떨어질 수 있음.
따라서 Cache Hit Ratio를 향상시키는 게 중요함(향상 기법 설명).
RAM(Random Access Memory) (참고: 1, 2, 3, 4)
개요 및 특징
CPU가 즉각적으로 접근할 수 있으며, 프로그램 실행과 데이터 처리를 위해 일시적으로 명령어나 데이터를 저장하는 휘발성 메모리 장치(by ChatGPT 4.5).
Stack, Heap, Code, Data 영역으로 구성되어 있어 각 영역이 가상 메모리(Virtual Memory)를 통해 각 프로세스에 할당됨.
RAM의 종류
RAM의 구성요소
OS의 RAM 관리 방법
메모리의 주소 공간(Address Space) (참고: 1, 2, 3, 4)
관리의 최소 단위를 주소(Address)라 하며, 1 byte(8 bits)의 크기를 가짐.
1 byte 단위마다 지정된 각 주소는 편의상
0x??????(16진수)로 표시됨(참고).RAM에서는 논리(가상) 주소와 물리(절대) 주소로 주소 공간을 분리하여 관리함.
왜 이렇게 구분? OS 영역 침범 방지 + 메모리 관리의 편의성
물리 주소(Physical Address) (※ 절대 주소(Absolute Address)라고도 함) (참고)
논리 주소(Logical Address) (※ 가상 주소(Virtual Address)라고도 함)
각 유저 프로세스 관점에서 바라 본 주소 공간으로, 각 주소마다
0x0부터 시작함.각 프로세스마다 새로 할당되므로 시스템 전체(OS) 관점에서 보면 같은 주소가 여러 개 존재할 수 있음.
OS 영역과 유저 영역으로 구분되어 있음.
OS는 프로세스 생성 및 메모리 할당 시 가상 주소-물리 주소쌍이 담긴 페이지 테이블(Page Table)을 만들어 RAM에 저장함(참고).
프로세스 실행 시 CPU는 P.T의 맵핑 정보를 참고하여 명령어나 데이터를 참조함.
상대 주소(Relative Address)는 프로세스 내에서 특정 주소 기준으로 얼마 떨어진 주소를 가리킬 때 사용하는 개념으로, 강의에서의 설명과는 소폭 다름(참고).
메모리 할당 방식 (참고: 1, 2, 3)
개요
RAM의 빈 물리 주소 공간에 각 프로세스의 가상 주소 공간을 할당·관리하는 방법.
연속적인 Swapping, Context Switching 상황에서도 최소한의 빈 공간과 Overhead를 유지하는 것이 메모리 할당 방식 연구의 목표.
메모리 오버레이(Memory Overlay) (참고: 혼공컴운 391p., 2, 3, 4, 5)
프로그램을 여러 개의 독립된 모듈로 나누고, 한 번에 필요한 모듈만 메모리에 적재하여 실행하는 방식(참고)
.
Manual Overlay에서 Dynamic Loading과 Dynamic Linking으로 발전함.
위 기술들은
종류
가변 분할
각 프로세스에 메모리를 프로세스 크기만큼 연속 할당하는 방식.
외부 단편화로 인한 Overhead 발생
고정 분할
각 프로세스에 메모리를 특정 크기만큼 연속 할당하는 방식.
구현이 쉽고 오버헤드가 적다 vs. 내부 단편화 발생
버디 시스템
짬뽕
비휘발성 메모리(Non-volatile Memory)
Secondary Memory (참고: 1, 2, 3)
[Day 10]
데이터 지향 설계(Data-Oriented Design) (참고: 1, 2, 3)
소프트웨어를 설계할 때 데이터 자체와 그 흐름에 초점을 맞추어, 프로그램의 성능과 메모리 사용 효율을 극대화하는 방법론(by ChatGPT-o3-mini-high).
프로세서 캐시(cache) 효율을 높이고, 불필요한 메모리 접근 오버헤드를 줄이며, 데이터 처리 속도를 극대화하는 것이 목표.
데이터를 배열에 담아 특정 인덱스 데이터를 호출하면 Cache Locality에 따라 해당 인덱스와 인접한 데이터들이 캐시 메모리에 올라감.
CS를 공부하면 새로운 라이브러리/프레임워크를 배우기 쉽다.
[Week Review]
일주일 동안 공부하면서 배우고 느낀 점
감자님의 운영체제 강의는 너무 좋다. 눈에 쏙 들어오고 이해도 잘 된다. 하지만 엉성하게 감이 잡힌 상태에서 그 이상을 궁금해하기 시작하면 지옥이 펼쳐진다....
예를 들어 (이후에 나오는지는 모르겠지만) IPC는 강의에서 주로 다룬 공유 메모리 방식 말고도 파이프 방식도 있는데, 이에 대해 검색하니 뭐 데이터스트림이라느니 Message Passing 방식이라느니 알 수 없는 내용들이 쏟아진다.
이 강의(워밍업 클럽)로 큰 줄기를 그린 다음 오랜 기간에 걸쳐 꾸준히 학습하며 디테일을 채워 나가야겠다. 나는 비전공자인데다, 머리도 나쁘고, 근육병에, 기초수급자에다, 남들은 당분간 알아주지 않을 길을 오래 걸어가야 하니까.
자료구조 및 알고리즘을 공부하니 프로그램 설계 능력 향상에도 도움이 되는 것 같다.
잡식으로 필요한 것 혹은 필요해 보이는 기술 같은 것들만 공부하며 버텨온 시간들을 뒤로 하고 내실을 다지고자 별 기대 없이 시작한 워밍업 클럽인데, 의외로 소프트웨어 설계에 큰 도움이 되는 듯하다.
이번 주 중간점검 때는 질문할 게 별로 없었다. 궁금한 게 없어서가 아니라 뭐부터 질문해야 할지 모를 정도로 머릿속이 혼란스러운 게 첫째, 궁금한 것들이 대부분 감자님 강의에 없는 내용들이라는 점이다.
어제 중간점검 때 감자님께서 "강의 내용 정도면 컴공 전공자들이 배우는 지식과 크게 다르지 않다."고 말씀하셨는데, 내가 전공자가 되어보진 않았어도 "그건 아니다."라고 단언할 수 있다. 내 목표가 전공ㅈ
어려웠던 점
(참고) IPC 부분을 조금 깊이 파고들다 보니 강의에 설명되지 않은 부분이 정말 많아서 혼란이 심했다.
특히 Process Synchronization 문제와 그 해결 방식들에 대해 공부한 후에, "그래서 저 수많은 IPC 방법들 중 Process Synchronization 문제는 어떤 방법을 쓸 때 발생하는 거지?"가 헷갈렸다.
감자님 답변으로 "어떤 방법을 쓰는가보다는 공유자원의 존재 유무로 동기화 이슈가 발생할 수 있다"는 걸로 대강 이해했다.
(참고) 동기화 부분을 정리하면서 강사님께서 말씀하시는 동기화 문제가 공유 메모리 방식에서 주로 발생하는 것 같다고 이해했다. 근데 다른 강사님의 강의에서 "파일 기반 IPC는 OS가 필요한 용량을 할당해줄 때 기준이 느슨한데, 메모리 기반 IPC는 OS가 필요한 용량을 할당해줄 때 기준이 엄청 깐깐하다."는 말이 나왔고, 왜 그런 차이가 나는지 궁금해져서 질문을 올렸다.
답변에 틀린 부분은 없었지만 뭔가 명쾌한 느낌도 아니었다. 그래서 챗지피티에게 물어보니 메모리 할당 방식과 동기화 문제 발생 가능성을 이유로 설명했다. 이 답변을 바탕으로 정리에 두었더니 훨씬 명확해졌다.
IPC를 공부할 때 통신 과정을 순서대로 정리해두니 확 이해도 되고 머릿속에 남는 것 같다!
앞으로 개선할 점
아무리 열심히 공부하기 위한 목적이라지만... 이거 공부 및 정리에 너무 많은 시간을 쓰고 있다. 기본적인 걸 무조건 끝내놓고 남는 시간에 내용 보충을 해야겠다.
기타 잡담
강의 보면서 웃겼던 부분ㅋㅋㅋㅋㅋㅋ 빌린 돈도 안 갚아놓고 더 빌려 달라니 뭔 심보여
댓글을 작성해보세요.
