[3~4/14 Sprint] 운영체제

▪︎ 공유자원 Shared Resource : 한 시스템 안에서, 프로세스/쓰레드가 함께 접근할 수 있는 자원/데이터

 

▪︎ 경쟁상태 Race Condition : 공유자원에 두 개 이상의 프로세스/쓰레드가 동시에 읽기/쓰기를 시도하는 상태

▪︎ 임계영역 Critical Section : 둘 이상의 프로세스/쓰레드가 공유자원 접근 시, 순서 등에 따라 결과가 달라질 수 있는 코드 영역

• 상호배제 (Mutual Exclusion): 한 프로세스만 임계영역 진입가능
• 한정대기 (Bounded Waiting): 특정 프로세스가 영원히 임계영역에 들어가지 못하면 안됨(영구적 배제X)
• 진행-융통성 (Progress): 한 프로세스가 다른 프로세스 작업 방해X

→ 위의 3가지 조건을 만족하는 해결 방법

 

1. 뮤텍스[잠금 메커니즘]: 프로세스/쓰레드 설정 → lock()/unlock() 상태

2. 세마포어[신호 메커니즘](상호배제 명시적 구현 필요) → 정수 값(세마포어 값) + wait(P)함수/signal(V)함수으로 처리

• 바이너리 세마포어(0/1): Signal 오면 들어가서, Wait(+세마포어 값)
• 카운팅 세마포어(여러 자원-접근 제어)

3. 모니터(상호배제 자동): 공유 자원은 숨기고, 접근 인터페이스만 제공(모니터 큐에 작업 추가 후, 순차적 처리)

 

+ 점유대기 (Hold & Wait), 비선점 (No Preemption), 환형대기 (Circular Wait)

⇨ 교착상태 Deadlock: 두 개 이상의 프로세스가 서로 가진 자원을 기다리다 중단된 상태 (임계 영역 처리 방식에 따라 발생 가능)

• 자원할당 시, 위의 조건이 성립되지 않도록 설계
• 요청자원 최대치 설정 → 자원할당 가능 여부 파악(은행원 알고리즘 - 총 자원 양/할당 정도<불안정→안정>)
• 교착상태 발생시 문제 사이클 체크 후, 관련 프로세스 하나씩 삭제
• 교착상태 발생률은 낮은 편 & 처리 비용이 크기 때문에 → 작업 종료(응답 없음)

*기아상태 Starvation: 특정 프로세스가 우선순위 문제로, 자원을 계속 할당받지 못하는 상태

 

# 식사하는 철학자 문제

[문제] (Deadlock + Starvation 가능)

• 다섯 명+의 철학자가 둥근 식탁에 둘러앉아 있습니다. (철학자가 많아지면 언젠가는 교착상태--최대한 미루기)
• 철학자는 식사하거나 생각하는 두 가지 상태 중 하나에 있습니다.
• 식사하려면 각 철학자는 자신 앞에 놓인 두 개의 포크가 필요합니다. (왼쪽과 오른쪽의 포크)
• 이 포크들은 철학자들 간에 공유됩니다.

- 모든 철학자가 왼쪽 포크를 집을 경우, 모두 식사 불가능(=프로그램 대기/응답 없음)

공유 자원: 포크 / 쓰레드: 철학자

 

How to solve it? 예시: 4개의 교착 상태 발생조건 중, 1가지 이상을 해지

자원 계층(Resource Hierarchy) 사용: 모든 철학자가 특정 순서(예: 왼쪽 포크부터 집기)를 따라 포크를 집도록 강제하여 교착상태를 회피

세마포어(Semaphore) 사용: 포크의 유효성 검사 & 관리, 각 포크를 상징하는 세마포어를 통해 원자적(atomic)으로 접근권을 관리함으로써 교착상태 회피

모니터(Monitor), 조건 변수(Condition Variables): 각 철학자는 자신의 상태를 모니터로 관리하고, 주변 철학자의 상태에 따라 결정적으로 행동. 이를 통해 교착상태나 기아 상태를 피하면서 공정성을 유지

Section 1. 프로세스 & 쓰레드

프로세스: 실행되고 있는 프로그램(CPU 스케줄링의 대상이 되는 작업)

쓰레드: 프로세스 내 작업 흐름

 

HDD/SDD[프로그램]  인스턴스화→  RAM[프로세스](운영체제가 CPU 스케줄러에 따라 실행)

 

OS(CPU 스케줄러) → CPU 스케줄링 알고리즘에 따라 프로세스 작업 지시(쓰레드 단위 → CPU<소유권> 할당)= CPU 이용률 ↑, 주어진 시간에 많은 일 처리, 준비 큐-프로세스 적게/응답시간 짧게!

• 비선점형: 스스로 CPU 소유권 포기/컨텍스트 스위칭 부하 ↓

• FCFS, First Come First Served: 콘보이 현상 가능(길게 수행되는 프로세스로 인해, 준비 큐에서 대기 시간 ↑)
• SJF, Shortest Job First: 긴 시간을 가진 프로세스가 실행되지 않는 기아 상태 발생/평균 대기 시간 가장 짧음 *실제 실행시간 유추 불가 = 과거 실행시간 토대로 계산
• 우선순위: SJF + Aging에 따라 우선순위를 높임

• 선점형: 다른 프로세스에 CPU 소유권 강제 할당(운영체제 실제 사용 방식)

• 라운드 로빈(우선순위 알고리즘): 특정 시간 부여 후 프로세스 중단 → 준비 큐 뒤로 재배치 *(N - 1) x q 시간 후 재 차례 - 할당 시간이 너무 크면 FCFS & 짧으면 오버헤드(컨텍스트 스위칭/비용 ↑) - 전체 작업 시간은 길어지지만 평균 응답시간은 짧아짐 # 로드 밸런서(트래픽 분산 알고리즘) = 서버부하 분산 기술
• SRF, Shortest Remaining Time First: (SJF는 수행 완료 후 다음 수행) 중간에 더 짧은 작업이 들어오면 수행하던 프로세스 중지! 후 수행
• 다단계 큐: 우선순위 별로 준비 큐 여러개 - 각 큐마다 라운드로빈/FCFS 등 다른 스케줄링 알고리즘 적용 *큐 간의 프로세스 이동 안됨/스케줄링 부담X/유연성 ↓

 

■ 컴파일 과정[→프로그램/실행파일]

소스코드파일 → 전처리(주석제거/헤더파일 병합(#)→매크로 치환) → 컴파일러(오류 처리, 코드 최적화 → 어셈블리어) → 어셈블러(→ 목적 코드) → 링커(목적 코드 + 프로그램 내 라이브러리 함수/다른 파일 → 실행 파일)

* 정적 라이브러리: 프로그램 빌드 시(모든 코드를 실행파일에 삽입/시스템 환경-외부 의존도가 낮지만, 코드 중복-메모리 효율성 떨어짐)

* 동적 라이브러리: 프로그램 실행 시(DLL 함수 정보 참조) - 메모리 효율성+외부 의존도 ↑

 

◼︎ 프로세스 상태 값

• 생성[PCB 할당됨]: fork(부모 프로세스 주소 공간 복사/새로운 자식 프로세스 생성-상속 X), exec(프로세스 새롭게 생성)
• 대기: CPU 소유권 할당 대기, 메모리 할당(공간 충분하면)/ 대기 중단: 일시중단 상태에서 메모리 부족
• 중단: 이벤트 발생(I/O 디바이스 인터럽트)-프로세스 차단/일시 중단: 중단 상태에서 재 실행시도 - 메모리 부족
• 실행(CPU burst): CPU 소유권 & 메모리 할당 - 프로세스 수행
• 종료: 자연적-Terminated/process.kill(사용자)/abort(부모 → 자식 프로세스 강제종료)

◼︎ PCB[프로세스 메타 데이터(컨텐츠-설명)]: 커널 영역의 앞부분에 위치

• 프로세스 스케줄링 상태: 프로세스 CPU 소유권 얻은 후, 상태 값
• 프로세스 ID
• 프로세스 권한: 컴퓨터 자원 or I/O 디바이스 권한 정보
• 프로그램 카운터: 프로세스 실행 - 다음 명령어 주소에 대한 포인터
• CPU 레지스터
• CPU 스케줄링 정보: CPU 스케줄 - 중단시간 등 정보
• 계정 정보
• I/O 상태 목록: 프로세스 할당 된 디바이스 목록

● 컨텍스트 스위칭: PCB 교환 과정(싱글 코어 기준)

프로세스 - 할당시간 종료/인터럽트(시스템 콜)

설명) 프로세스 A 실행 중단(PCB 저장) & 프로세스 B 로드/실행

⇨ 중간에 유휴시간 발생(CPU 가용성 ↓) & 캐시미스(메모리 주소 오류 방지를 위해 캐시 클리어, 이후 → TLB에서 page-table로 가서 재로드 필요/비용 발생)

* 멀티 쓰레드(스택 제외 메모리 영역 공유)의 컨텍스트 스위칭: 프로세스 컨텍스트 스위칭보다는 비용+시간 적게 듬/동기화-문제

 

멀티 프로세싱
- 웹 브라우저 내, 제어/권한 분할: 브라우저 프로세스, 렌더러 프로세스, 플러그인 프로세스, CPU 프로세스
- IPC(프로세스 간 공유데이터 - 관리 메커니즘): 서버/클라이언트, 공유 메모리, 파일, 소켓, 익명 파이프, 명명 파이프, 메시지 큐
멀티 쓰레딩
- 웹 브라우저(렌더러 프로세스 내부): 메인 스레드, 워커 스레드, 컴포지터 스레드, 레스터 스레드
* 동시성/병렬성

멀티 스레싱 장점 & 단점)
→ 속도 향상과 자원 공유 & 동기화 문제와 자원 경쟁 문제

 

◼︎ 프로세스 메모리 구조

• 커널 영역
• Stack - 컴파일 단계에서 지역변수/매개변수(함수 호출/반환시)
• Heap - 런타임 단계에서 동적으로 메모리 할당(malloc(), free() 함수/Vector구조 저장 위치)
• BSS(초기화 값X)/Data(초기화 값O) Segment - Global/Static 변수
• Code segment - CPU에서 하나씩 명령어 실행

Section 2. 메모리 관리

메모리 계층 [레지스터 / 캐시(L1/L2) / 주기억장치(RAM) / 보조기억-저장장치(SSD/HDD)]

속도/용량 - 비용 감안

 

◼︎ 캐시: CPU와 메모리 사이, 병목현상 발생률 ↓ / 이런 역할 = 캐싱 계층

 

*캐시 데이터 설정 원리

1) 시간 지역성: 최근 사용 데이터 우선(For 문)

2) 공간 지역성: 최근 접근 데이터(Array)

 

*캐시 히트(원하는 데이터 찾음/CPU 내부버스)/캐시 미스(CPU → 시스템 버스로 가서, 제어장치 → 메모리 내 캐시로 데이터 세팅)

 

*캐시 매핑

• 직접 매핑: 1:1~10/2:11~20 - 처리 속도 ↑/충돌 발생 ↑
• 연관 매핑: 관련있는 캐시와 메모리 매핑 - 처리 속도 ↓/ 충돌 발생 ↓
• 집합 연관 매핑(직접+연관): 집합(블록화)내에서 무작위로 저장

- 웹 브라우저 캐시[쿠키(만료기한O/키-값)/로컬-스토리지/세션(만료X/키-값) 스토리지]

 

◼︎ 가상 메모리 [메모리 관리 기법]

메모리 자원 추상화(한정된 메모리 → 사용자 측, 사용 가능 메모리가 크게 보임)

가상 주소(Logical address)를 → [MMU, 메모리 관리 장치] → 실제 주소(Physical address)로 변환

- CPU 내부 [ MMU (TLB: 주소변환을 위한 캐시-페이지 테이블 내용 일부 보관) ]

- 메모리 내부 [ 페이지 테이블 ]

* 요구 페이징: 요구되는 프로세스 일부만 메모리 적재

* 페이지: 가상메모리 사용 최소 크기 단위

* 프레임: 물리 메모리 사용 최소 크기 단위

그림으로 그려보자면..? 페이지 > 블록 > 워드(레지스터)

 

● 스와핑: 메모리 사용하지 않는 영역 → 하드디스크 이동 / 하드디스크 → 일부분 메모리로 Swap!

- 가상 메모리에는 존재/실제 메모리에는 없는 데이터, 코드 접근 시 페이지 폴트 발생

Page Fault & Swapping Process

1. CPU → 물리 메모리 확인(가상 주소로, 페이지 검색) 후 해당 페이지 없으면 트랩 발동(운영체제 인지)
2. 운영체제 → CPU 중지됨
3. 디스크에서 가져와 물리 메모리에 적재(페이지 교체 알고리즘/스와핑)
4. 페이지 테이블 갱신 - 명령 재시작

● 스레싱(thrashing): Page Fault ↑(컴퓨터 성능 저하)

많은 프로세스 동시 적재 → 스와핑 발생률 ↑ & CPU 이용률 ↓ -> 착각(더 많은 프로세스 메모리 적재) - 악순환

* 하드웨어~해결방안: 메모리 업그레이드 or SSD 사용

* 소프트웨어~해결방안

• 작업 세트(working set): 프로세스 과거 사용 이력(지역성) 기반, 페이지 집합 미리 메모리 적재 - 탐색비용/스와핑 ↓
• PFF(Page Fault Frequency): 페이지 폴트 빈도 조절 - 상한선/하한선 설정 후 체크 & 프레임 조절

◻︎ 메모리 할당 (메모리 위치/할당 크기)

• 연속 할당

• 고정 분할 방식 - 내부 단편화(융통성X)
• 가변 분할 방식(동적으로 메모리 분할/외부단편화) - 최초 적합(시작부터 빈공간 검색), 최적적합(가장 작은 홀 검색), 최악적합(크기 차이가 가장 많이 나는 홀 선택)

• 불연속 할당(운영체제 사용방식)

• 페이징 기법(프로세스를 동일한 크기로 분할 - 일정 페이지에 저장, 홀 크기 균일~분산됨/But, 주소변환 복잡)
• 세그멘테이션 - 의미 단위<세그먼트>로 분할/프로세스의 4가지 영역을 부분으로 나눔(공유+보안 ↑/홀 크기 균일X)
• 페이지드 세그멘테이션 - 세그먼트로 분할 + 페이지로 분할(접근권한 설정/메모리 2번 접근)

◻︎ 페이지 교체 알고리즘 (한정된 메모리, 스와핑률 적게 설계 필요)

• 오프라인 알고리즘(성능 비교용): 미래에 사용(참조)될 페이지/현재 할당된 페이지 교체
• FIFO
• LRU(Least Recentely Used): 참조가 오래된 페이지 변경 (각 페이지마다 계수기, 스택 필요 - Aging 판단) *해시 테이블+이중 링크드 리스트
• NUR(Not Used Recently)[Clock 알고리즘]: 최근 참조(1)/그외(0) - 시계방향으로 돌면서 0을 찾고 프로세스 교체 → 1로 변환
• LFU(Least Frequently Used): 참조 횟수 적은(사용률 ↓) 페이지 교체

Section 3. 컴퓨터 구조

◼︎ 운영체제의 역할

• CPU 스케줄링 & 프로세스 관리
• 메모리 관리
• 디스크 파일 관리
• I/O 디바이스 관리

◻︎ 운영체제 구조 [프로그램 - GUI/CUI / 시스템콜(추상화 계층) - 커널 / 드라이버(하드웨어 제어 소프트웨어) - 하드웨어]

유저모드/쉘~커널<운영체제 핵심: 시스템 콜 인터페이스 제공/자원 활용>모드 전환 - mode bit(0/1)

*직접-자원: 네트워크 통신, 데이터베이스, 파일접근, 메모리, 보안, 파일 시스템, 프로세스, I/O 디바이스+요청 관리, 입출력 함수

 

◼︎ CPU(계산)

* CU, 제어장치(프로세스 조작 지시): 입출력 장치 간 통신 제어+명령어 읽고 해석+데이터 처리 순서 결정 → 메모리 ⟷ *레지스터(임시기억장치-CPU 직접 연결)

* ALU, 산술+논리 연산장치 (레지스터에 있는 값 계산)

* 인터럽트 = CPU 정지

• 하드웨어 인터럽트 - I/O 디바이스: 인터럽트 라이 설계 후, 운영체제 시스템 콜 호출 → 디바이스 로컬 버퍼 일 처리
• 소프트웨어 인터럽트(트랩) - 프로세스(오류) → 시스템 콜 호출

- DMA 컨트롤러: I/O 디바이스 메모리 직접 접근 (CPU 부담 ↓)

- 메모리(기록)

- 타이머: 프로그램 작동 제한 시간

- I/O 디바이스 내부[디바이스 컨트롤러(미니 CPU) & 로컬 버퍼(미니 메모리)]

 

---

# References

[도서] 면접을 위한 CS 전공지식노트 - 주홍철

https://seeun0210.tistory.com/m/40