티스토리 뷰
* 운영체제
사용자와 컴퓨터 하드웨어간의 인터페이스로서 동작하는 시스템 소프트웨어의 일종.
사용자가 컴퓨터를 편리하게 사용할 수 있게 하며 자원 스케줄링, 신뢰성 향상 등의 목적을 가짐
- OS의 성능 평가 기준: Throughput, Turnaround Time, Availability, Reliability
- OS의 발전 과정
1) 일괄처리 시스템 (Batch): 입출력 버퍼링을 통해 처리해야할 작업을 기억장치에 모아놓고 일괄 처리.
2) 다중 프로그래밍 시스템: 여러 프로그램들이 탑재되어 처리장치를 번갈아서 사용. 처리량 극대화
3) 시분할 시스템 (Time Sharing): 여러 사용자들의 프로그램을 컴퓨터가 번갈아가며 처리. 응답시간 최소화
4) 다중 처리 시스템: 여러개의 CPU를 사용하여 여러 프로그램을 동시 처리
5) 실시간 처리 시스템: 말 그대로. Time-critical한 작업들을 수행하기에 적합
6) 다중 모드 시스템: 위의 여러 시스템들을 쓰까놓은 것
7) 분산 처리 시스템: 여러 대의 컴퓨터들에 작업을 나눠서 처리하고 결과는 통신망으로 연결하여 전송
* 언어 번역 프로그램
소스 코드를 기계어로 바꿔주는 것.
1) 어셈블러: 어셈블리어로 작성된 프로그램 -> 기계어로 번역
2) 컴파일러: 고급 언어로 작성된 프로그램 -> 기계어로 번역
3) 인터프리터: 소스코드를 각 줄마다 번역하면서 즉시 실행 (Object File을 생성하지 않음)
* 링커와 로더
Linker: Object File을 실행 가능한 로드 모듈로 변환해주는 프로그램
Loader: Object File을 실행 가능한 파일로 변환하기 위해 주기억 장소를 할당하거나 여러 Object File을 연계하는 등의 역할
- Loader의 실행 순서
1) 할당 (Allocation): 프로그래머에 의해 수행. 주기억장치에 저장할 공간을 확보
2) 연결 (Linking): 프로그래머에 의해 수행. 필요한 프로그램들을 결합하여 주기억 장치에 적재하고 보조기억장치에 이미지를 보관해두는 작업
3) 재배치 (Re-location): 번역 프로그램에 의해 수행. 보조기억장치에 저장된 프로그램이 사용하는 각 주소를 실제 할당된 기억장소로 매핑시키는 작업
4) 적재 (Loading): 로더에 의해 수행. 실행 프로그램을 할당된 기억 공간에 실제로 옮기는 작업
- Loader의 종류
1) Complie-and-GO: 컴파일러가 번역 후 로더 기능까지 수행. 할당/재배치/적재를 컴파일러가, 연결은 링커가 수행
2) Absolute: 적재 기능만 수행. 할당/연결은 프로그래머가, 재배치는 컴파일러가 수행
3) Direct Linking: 위 4과정을 수행하는 가장 일반적인 로더.
4) Dynamic; 프로그램을 한꺼번에 적재하지 않고 필요한 일부분만 차례로 적재
- Preprocessor: 소스코드를 기계어로 번역하는 대신 기존의 고레벨 컴파일러 언어로 전환하기 위해 처리나 준비 (매크로 확장, 기호 변환 등) 작업을 하는 것
* 매크로
- 어셈블리로 프로그램을 작성할 때 반복되는 연산을 효과적으로 하기 위함
- 여러 프로그램에서 공통적으로 자주 사용되는 매크로를 모아놓은 '매크로 라이브러리' 가 존재
- 매크로의 기본 기능: 호출 인식, 정의 인식, 정의 저장
* 프로세스와 스레드
- 프로세스: 실행 중인 프로그램, 프로시저의 활동, OS가 관리하는 실행 단위
- PCB (Process Control Block): OS가 프로세스에 대한 정보를 저장해놓는 저장 장소. 각 프로세스마다 PCB를 가진다 (fork로 자식 프로세스를 만들어도 PCB가 따로 생김).
> PCB에 저장된 정보
1) 프로세스의 현재 상태
2) 우선순위
3) CPU 레지스터 정보
4) 할당된 자원 정보
- 프로세스 상태 전이: 준비 - 실행 - 대기
1) 준비 상태: CPU를 할당받기 위해 대기하고 있는 상태.
-> Dispatch (CPU에 프로세스가 배정) -> 실행 상태
2) 실행 상태
-> 할당받은 시간이 지남 -> 종료
-> I/O 인터럽트 등이 발생해 잠깐 중지 -> Block -> 대기 상태
3) 대기 상태: 다시 CPU를 할당받으면 실행 상태가 됨
- 스레드
제어의 흐름. 프로세스에서 실행의 개념만을 떼온 것.
하나의 프로세스 내에서 병행성을 증대시키기 위함.
프로세스의 특성을 일부 갖고 있으므로 Light Weight Process라고 부르기도 함.
* 병행 프로세스와 데드락
- 병행 프로세스: 2개 이상의 프로세스들이 동시에 실행중인 것
- 임계 구역 (Critical Section)
여러 프로세스가 공유하는 자원이나 데이터. 한 시점에서 하나의 프로세스만 사용할 수 있도록 해야 함
- 동기화 기법
1) 세마포어 (Semaphore): 각 프로세스가 크리티컬 섹션에 접근할 때 P, V 플래그를 이용하여 상호 배제
2) 모니터 (Monitor): 세마포어로 이루어진 더 하이레벨의 구조
- 교착 상태 (Deadlock): 2개 이상의 프로세스들이 서로 자원을 요구하면서 기다리다가 무한히 대기하는 현상
> 데드락의 발생 조건
1) 상호 배제 (Mutual Exclusion): 한번에 한개의 프로세스만이 공유자원을 사용할 수 있음
2) 점유와 대기 (Hold & Wait): 이미 자원을 가진 프로세스가 다른 자원의 할당을 요구
3) 비선점 (Non-preemption): 이미 할당된 자원은 강제로 빼앗을 수 없음
4) 환형 대기 (Circular Wait): 이미 자원을 가진 프로세스가 앞이나 뒤 프로세스의 자원을 요구
> 데드락의 해결 방법
1) 예방: 위의 4가지 조건 중 하나를 사전 차단
2) 회피: 데드락 발생이 예상될 경우 그 가능성을 피해가도록 함. 주로 쓰이는게 은행원 알고리즘
3) 회복: 데드락을 일으킨 프로세스를 종료시키거나 자원을 강제로 선점
* 프로세스 스케줄링
시스템의 자원을 여러 프로세스에 할당할 때 어떤 정책을 적용할 것인가?
- 비선점 스케줄링 (Non-preemptive)
다른 프로세스가 이미 CPU를 할당받은 프로세스의 CPU를 빼앗을 수 없다. 일괄 처리 시스템에 적합하며 리얼타임 시스템에는 부적합하다.
> 스케줄링 기준: CPU Utilization, Throughput, Turn-around Time, Waiting Time, Response Time
1) FCFS (First Come First Service)
큐에 도착한 순서대로 CPU를 할당. 어떤 순서로 들어왔느냐에 따라 대기시간의 차이가 심하다.
2) SJF (Shortest Job First)
큐에서 대기중인 프로세스 중 실행시간이 가장 짧은 프로세스에게 먼저 할당. 평균대기시간을 최소화한다.
3) HRN (Highest Response-ratio Next)
우선순위 = (대기시간 + 서비스받을 시간) / 서비스받을 시간
을 계산해서 높을수록 먼저 할당.
4) Priority: 3번같은 우선순위 계산식이 아니라 미리 사용자가 지정한 우선순위에 따라 할당.
5) Deadline: 작업별 Deadline이 있을 때 어떻게든 그것만은 지키도록 할당.
6) Aging: 4번의 우선순위 방식은 우선순위가 낮은 프로세스는 무한정 대기 (Starvation: 굶어죽음) 하는 현상이 발생할 수 있는데 이를 해결하기 위해 대기시간에 비례하여 우선순위를 점차 높여주는 것
ex) 실행시간이 각각 P1 = 20초, P2 = 6초, P3 = 5초일때 SJF를 써서 스케줄링하면 평균 대기시간은?
> P3 -> (5초) -> P2 -> (6초) -> P1 순서대로 실행
> P2는 5초를, P1은 11초를 기다렸다. 평균 대기시간은 16 / 3 = 5.333... 초
- 선점 스케줄링 (Preemptive)
프로세스가 CPU를 할당받아 사용중이라도, 더 중요한 다른 프로세스가 들어오면 CPU를 강제로 뺏어올 수 있다.
긴급한 프로세스가 먼저 처리될 수 있으므로 시분할/리얼타임 시스템에 적합.
1) SRT (Shortest Remaining Time)
실행중인 프로세스의 남은 시간과 큐에 새로 도착한 프로세스의 실행시간을 비교해서, 실행시간이 짧은 프로세스에게 CPU를 할당하는 방법
2) RR (Round Robin)
프로세스를 일정 시간주기 (Time Slice) 로 나눠서 돌아가면서 실행하는 방법.
Time Slice를 적절하게 설정하는 것이 중요: 너무 길면 FCFS랑 다를게 없고, 너무 짧으면 Context Switching (프로세스 바꿔올리는 작업) 오버헤드가 커진다.
3) MQ (Multi-level Queue)
대기 큐를 하나가 아니라 우선순위에 따라 여러개 두는 것.
4) MFQ (Multi-level Feedback Queue)
대기 큐를 여러개 두고, 각 큐마다 부여된 Time Slice 안에 처리하지 못한 프로세스는 다음 레벨로 넘기는 방법.
최하위 레벨에서는 작업이 완료될때까지 RR로 처리.
짧은 작업이나 입출력 위주 작업에 우선순위를 높게 준다.
* 메모리 관리
- Fetch 전략: 프로그램이나 데이터를 언제 메모리로 가져올 것인가? - 요구 반입 / 예상 반입
- Placement 전략: 메모리의 어디에 입력 데이터를 저장할 것인가?
1) First-Fit: 빈 공간 중 순서대로 첫번째 주소에 배치
2) Best-Fit: 빈 공간 중 입력 데이터 크기와 가장 비슷한 곳에 배치
3) Worst-Fit: 빈 공간 중 입력 데이터 크기와 가장 비슷하지 않은 (= 공간이 많이 남아있는) 곳에 배치
- Replacement 전략: 메모리 공간 확보를 위해 뭘 먼저 뺄 것인가?
> FIFO, OPT, LRU, LFU, NUR, SCR 등
* 메모리 할당 기법
- 연속 할당 (Contiguous): 프로세스가 메모리상의 연속된 공간에 존재하도록 함. 관리 및 구현이 용이하지만 External Fragmentation이 발생한다.
- 불연속 할당: 프로세스를 조각으로 나눠서 여기저기 배치하는 방법으로 Paging 기법, Segmentation 기법이 대표적. Fragmentation 문제를 해결하므로 요즘은 이걸 많이 쓴다.
* 단일/다중 분할 할당 기법
- 단일 분할 할당 기법
1) 오버레이 기법: 메모리 용량보다 큰 프로그램도 실행가능하게 하기 위해 보조기억장치에 사용하지 않는 부분을 일부 옮겨놓는 것? 프로그램을 잘라서 순차적으로 탑재.
2) 스와핑 기법: 오버레이랑 비슷한 역할을 수행하는데 순차적이 아니라 순서 상관없이 Swap한다.
- 다중 분할 할당 기법
1) 정적 할당 (고정분할 할당기법): 메모리 영역을 고정된 크기로 분할해 할당.
2) 동적 할당 (가변분할 할당기법): 그때그때 필요한만큼 할당. Fragmentation이라던지 효율성 면에서 이쪽이 더 낫다
* 단편화 (Fragmentation)
메모리의 각 부분이 할당되고 반납되고를 반복하다가 메모리에 애매한 조각 공간들이 생기는 현상
- Internal Fragmentation: 할당될 공간이 커서, 할당된 후 남은 공간
- External Fragmentation: 할당될 공간이 작아서 할당되지 못하는 남은 공간
- 해결 방법
> 통합 (Coalescing): 인접한 낭비공간들을 모은다
> 압축 (Compaction): 서로 떨어져있는 공백들을 모은다
ex) 빈 메모리 공간이 20K, 16K, 8K, 40K 짜리가 있을 때 17K짜리 프로그램이 들어왔다. Worst-Fit을 사용한다고 했을 때 내부 단편화의 크기는?
-> Worst-Fit이면 제일 공간이 큰 40K짜리에 배치될 것이고 그러면 23K짜리 조각이 남으므로 답은 23K
* 가상 기억 장치
보조기억장치의 일부를 메인 메모리처럼 쓰는 것. 구현방법으로 페이징 기법과 세그멘테이션 기법이 있다.
- 페이징 (Paging)
불연속 할당 기법의 일종. 프로그램과 메모리 영역을 페이지라는 일정한 크기로 나눈다.
> 가상 메모리 - 메인 메모리 사이의 매핑을 위한 Page Table (또는 Page Map Table) 이라는게 필요.
> 주소 매핑의 종류: 직접 매핑, 연관 매핑, 직접 연관 매핑
> 페이지 크기가 작으면 Segmentation이 감소하여 공간 효율성 증가, 그러나 입출력 오버헤드 증가
페이지 크기가 커지면 반대로 오버헤드가 적어지고 관리가 쉬워지지만 Segmentation이 증가
> MMU (메모리 관리 유닛) 라는 장치를 이용함.
> Page Table도 메모리에 있기 때문에 추가 메모리 액세스가 발생하는데, 이를 해결하기 위해 MMU를 위한 특별한 캐시 메모리를 둔다. (TLB)
- 세그멘테이션 (Segmentation)
가상 메모리에 보관된 프로그램을 Segment라는 다양한 크기의 논리적 단위로 나눠서 적재. 페이지는 고정된 단위였다.
마찬가지로 Segment Map Table이라는게 필요하다. 크기가 가변적인 Page라고 봐도 얼추 비슷함
* 페이지 교체 알고리즘
참조할 페이지가 메인메모리에 없어서 가상메모리에 갔다오는 걸 Page Fault라고 함.
이게 발생했을 때 메인메모리에서 어떤 페이지를 교체할 것인지 결정하는 알고리즘
1) OPT (Optimal replacement): 가장 오랫동안 사용되지 않을 것 같은 페이지를 예측해서 (?) 교체. 현실적으로 어렵다.
2) FIFO: 가장 먼저 적재됐던 페이지를 먼저 교체.
3) LRU (Least Recently Used): 가장 오랫동안 사용되지 않았던 페이지를 교체.
+ LRU Approximation Algorithm: 참조 비트라는걸 둬서 참조가 되면 이 비트를 1로 바꿔준다. 참조 비트가 0인 페이지를 우선적으로 교체.
4) LFU (Least Frequently Used): 가장 참조횟수가 적었던 페이지를 교체.
5) NRU (Not Recently Used): 최근에 사용되지 않은 페이지를 교체 (LRU랑 차이가 뭐지?)
6) SCR (Second Chance Replacement): LRU Approximation처럼 참조비트를 두는데, 페이지를 쭉 돌면서 일정 시간마다 참조비트를 1 -> 0으로 바꿔버림. LRU + FIFO를 섞은 방법
ex) 페이지 프레임이 3개이고 C, D, E, B, D, E, C 순서로 페이지 요청이 들어왔다. LRU 기법을 쓴다면 Page Fault의 발생 횟수는?
- C, D, E까지는 순서대로 페이지 폴트가 발생하면서 프레임에 들어옴
- B가 들어올 때 페이지 폴트가 발생하면서 가장 오래 전에 참조됐던 C가 빠짐
- D, E는 이미 있음
- C가 다시 들어왔는데 아까 빠졌으므로 페이지 폴트 발생
-> 5번
* 가상 메모리 관련 기타 용어
- 쓰레싱 (Thrashing)
프로세스가 CPU를 써서 작업을 해야하는데 계속 Page Fault가 나서, Page Swap하느라 정상 작업을 수행 못하는 현상
아래의 Working Set을 이용하면 줄일 수 있으나 그래도 안되면 프로세스를 강제로 중지시켜야 하기도...
- 구역성 (Locality)
프로세스가 실행되는 동안 자주 참조되는 일부 페이지가 있다는 경향성.
> 시간 구역성 (Temporal): 최근에 참조된 주소가 한동안 계속 참조되는 경향성이 있음
> 공간 구역성 (Spatial): 하나의 주소가 참조되면 그 근처가 계속 참조되는 경향성이 있음
- 워킹 셋 (Working Set)
프로세스를 효과적으로 실행하기 위해 메인 메모리에 유지해야하는 페이지의 집합
> 쓰레싱을 줄일 수 있다
> Locality 특성을 이용하여 결정. 과거 X개의 상태를 보고 미래를 예측한다.
> 시간이 지남에 따라 워킹 셋은 변화
> 워킹셋 안에 있는 페이지는 유지하고 나머지는 쫓아낸다
> 워킹셋이 너무 작으면 원하는 Locality를 모두 포함 못할 수 있고, 너무 크면 쓸데없는 것까지 다 들어감. 시스템에 따라 적당히 설정해주는 것이 중요