멀티 스레드와 디자인 패턴

Process & Thread 차이 Thread는 서로 메모리 공유 O 문제 모든 Thread가 하나의 자료구조(e.g. queue)를 공유하면 자료구조가 망가질 것 해결책: 배타제어 (=동기화) Concurrent Class (동시성 컬렉션) Lock 특정 코드 구간을 반드시 한 Thread만 실행하도록 막음 (크리티컬 섹션) Lock을 건 코드 구간의 실행시간이 길수록 성능저하가 발생 최악의 경우 Single Thread가 차라리 나음 One Process, One Thread Architecture가 나온 이유 Redis도 처음에 이 아키텍처를 따름에도 매우 빨라서 인기 얻음 Lock Free Lock을 사용하지 않고 배타제어 관련 키워드: interlocked.increment(), Atomic Operation, Lock-Free 알고리즘, Non-Blocking 알고리즘, CAS(compare and set) Thread Safe하게 일반 Class 사용하기 Write는 한 Thread에서만, Read는 여러 Thread에서 진행하면 유용 Process는 서로 메모리 공유 X 문제 Process끼리는 메모리 공유가 안되기 때문에, 통신이 필요 (HTTP, TCP…) MSA를 지향하는 현대 사회에서는 Process간 통신 필수 MSA = Multi Process Multi Process 필요성 서버 머신 한 대 성능에는 한계, Scale Out 필수! 서버 Architecture 구상하는 입장에서는 Process 하나가 작은 기능을 담는 것이 훨씬 유리 (One Process, One Thread가 설득력 얻는 부분) 언어가 다른 Process끼리는 서로 패킷 주고 받는게 스트레스 해결책: Multi Process 간 통신 방법 서버 간 통신 방법 Google Protobuf, Apache Avro (Good) IDL 파일에 모델을 정의해두면 Java, C++, JS, C# 등 여러 언어에서 사용 가능 JSON (Bad) 필드 추가시 상대방에게 알려주기 어려움 오타로 인한 디버깅 Cost 데이터를 어딘가에 올려놓고 필요한 서버가 알아서 가져가게 하는 방법 Redis Pub/Sub 특정 key에 데이터를 넣고 Pub/Sub Queue 이용하기 (AWS SQS) Queue에 넣고 데이터가 추가됐을 때, 특정 Topic으로 Event 받기 제 3 스토리지를 이용하는 것이므로 상대적으로 느림 빠르게 통신할 필요가 없는 경우 이용 웹서비스는 느리다는 느낌은 안듦 TCP 실시간 통신 서비스는 느리다 느낄 수 있음 Thread Thread란? 흐르는 시냇물 위에 띄워놓은 돛단배 스레드 스타트 이후 계속 원하는 작업들이 진행될 것이고 내 손을 떠나도 계속 돌아감 Entrypoint (진입점) public static void Main(String[] args) {} Process가 맨 처음 실행하는 함수, 함수가 종료되면 Process도 종료 Main Thread에서 실행 쓰레드 사용하기 var thread = new Thread(Func); 스레드 생성 thread.Start(); Thread 생성자에 넣어준 함수를 별도의 스레드에서 실행 thread.Join(); 스레드가 종료될 때까지 대기함 (Blocking) Blocking & Non-Blocking Blocking 함수를 실행하고 모든 코드가 완료된 후 리턴 Non-Blocking 실행한 함수의 코드가 완료되지 않고 리턴 Non-Blocking 함수의 실행과 완료를 아는 방법 Polling 주기적으로 확인하기 어떤 스레드에서 isFinish에 true 값을 넣으면 스레드 실행의 완료를 파악 while(true) { if (isFinish == true) { Break; } sleep(1000); //CPU 100%되지 않게 } e.g. HTTP 통신 Event Event가 발생했을 때 내가 원하는 함수를 호출해줌 setTimeout(callback, 1000); //1초 후 callback 함수 실행 콜백 지옥 유의 (요즘은 async & await 사용) async & await 장점은 무엇인가요? 멀티스레드 프로그래밍(비동기 실행)을 하지만 Blocking 방식으로 진행해서 편함 **콜백지옥 피할 수 있음 ** public async function Task<string> GetString() { ... } string result = await GetString(); Console.Write(result); getString() 함수는 다른 스레드에서 실행되지만 Blocking 방식으로 호출 = 비동기로 실행하지만 Blocking 방식 Server Thread Model 웹 서버, TCP 서버 등 서버 구현에 일반적으로 사용되는 스레드 모델 생산자 소비자 문제와 일치 생산자: I/O 스레드 (혹은 Worker 스레드라 부르기도 함) 네트워크 카드가 요청 데이터를 읽으면, I/O 스레드에서 해당 데이터를 Job Queue로 넘김 네트워크 카드 메모리가 매우 작으므로, 패킷이 가득차지 않게 작업만 빠르게 넘김 웹 서버나 프레임워크가 생산을 처리해 줌 Buffer: Job Queue Job Queue는 메인 메모리에 위치 e.g. 웹이라면 request들이 담김 소비자: Worker Thread (혹은 Logic 스레드라 부르기도 함) Worker Thread가 Job Queue에 작업들을 읽어서 처리 무거운 작업들 실행 (DB 접속, Redis 통신) 무거운 작업이라 오래 걸리지만, 최대한 빨리 실행되도록 해야 함 빨리 동작하지 않으면 Job Queue에 데이터가 차서 서비스 응답이 느려짐 일반적으로 개발자가 짠 로직은 Worker 스레드에서 돌아가는 코드를 짠 것 IOCP, EPoll OS에서 제공하는 비동기 I/O 작업을 하기 위한 기술이다. 즉, I/O 요청을 하면 비동기로 처리해주고 결과도 비동기로 받게 된다. Windows에는 IOCP, Linux에는 Epoll이라는 기능이 이에 해당한다. Guarded Suspension 패턴 할 일이 없는 Thread는 대기열에 넣고 할 일이 생기면 대기열에서 빼서 실행해주는 패턴 작업이 있으면 깨우고 없으면 쉼 Balking 패턴 내가 해야될 작업이 있는지 주기적으로 확인 (반복문) 작업이 있으면 하고 없으면 무시 (RUNNABLE) 스레드가 계속 동작하므로 작업이 없을 때 해야할 동작을 지정할 수도 있음 Read-Write Lock 패턴 Read 락과 Write 락을 따로 두는 락 메커니즘 한 스레드가 Write할 때는 다른 스레드가 Read 및 Write 모두 불가능 한 스레드가 Read할 때는 다른 스레드도 Read 가능 Read 스레드가 많고 Write 스레드가 좀 적다면, Read 성능 효율이 향상 Read 할 때는 Write를 하는지 안하는지만 판단 Read를 더 편하고 자유롭게 할 수 있음 만일, 사용한다면 각 언어에 구현된 클래스 찾아 사용할 것 Thread-Per-Message 패턴 하나의 작업 당 하나의 Thread가 실행하도록 위임 스레드 개수가 너무 많아지면 컨텍스트 스위칭 오버헤드가 높아져 성능 저하 Future 패턴 Main 스레드가 다른 스레드에 작업을 위임하고 본인 스스로도 다른 작업을 할 수 있게 하는 패턴 Thread-Specific Storage 패턴 스레드 마다 별도의 저장 공간을 가지게 하는 패턴 = 스레드 로컬: 각 스레드 별로 사용할 수 있는 변수 Reference Backend 멀티쓰레드 이해하고 통찰력 키우기

Computer Science · 2024-09-29

9-2. 가상 메모리

Page replacement - 다양한 캐싱 환경 캐싱 기법 한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식이다. 즉, 한 번 썼던 데이터는 빠른 접근이 가능한 캐쉬 메모리에 저장해두었다가 가까운 시기에 해당 데이터에 대한 접근이 요청되면 빠르게 제공해준다. Paging system과 더불어 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용되는 방식이다. 캐싱 기법의 운영상 시간 제약 다만, 이러한 캐싱 기법은 운영상 시간 제약이 존재한다. 교체 알고리즘이 삭제할 항목을 결정하는 일에 지나치게 많은 시간을 소요하지 않아야 한다. 예를 들어, Buffer caching이나 Web caching의 경우 시간 복잡도가 O(1) ~ O(logN) 정도까지 허용한다. 반면, Paging system에서는 기존의 LRU, LFU 등의 삭제 항목 결정 알고리즘이 실제로 사용되기는 어렵다. Paging system의 경우 page fault가 생길 때만 OS가 관여하기 때문에, 페이지가 이미 메모리에 존재하는 상황에서의 참조 시각 정보는 OS가 알 수 없다. 즉, 특정 상황의 참조 시각과 참조 빈도 등을 알 수 없으므로, 앞에서 살펴봤던 LRU, LFU 등의 알고리즘은 실제 시스템에서는 사용되기 어렵다. Clock Algorithm (=Second Chance Algorithm) 캐싱 제약을 극복하기 위해, paging system에서는 일반적으로 Clock Algorithm이 쓰인다. 이 알고리즘에서는 각각의 page table entry에 최근에 참조함을 나타내는 reference bit을 둔다. 그리고 이미 메모리에 올라와 있는 페이지에 대해 참조가 일어날 경우, 하드웨어가 reference bit을 1로 바꿔 최근에 참조함을 기록한다. 그리고 메모리에 새로운 page를 올려할 상황이라 OS가 내쫒을 page를 결정할 때에는 위와 같은 과정으로 reference bit을 참고해 오래된 page를 내쫒는다. 또한, 조금 더 개선된 성능을 위해 modified bit을 둬서 page에 write가 일어났는지 여부를 기록한다. 만일, modified bit이 1인 page가 있다면 해당 페이지는 메모리에 올라와서 최근에 내용이 변경된 것이기 때문에, backing storage로 쫒아낼 때 변경된 내용을 반영하고 쫒아내야 한다. Page Frame의 Allocation 지금까지는 페이지가 어떤 프로세스에 속하느냐를 구체적으로 고려하지 않고 작업을 수행했다. 하지만, 각 프로세스마다 얼마만큼의 page frame을 할당한 것인가는 중요한 문제이다. 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지를 동시에 참조하게 되는데, 이 명령어 수행을 위해 최소한 할당되어야 하는 frame 수가 있기 때문이다. 예를 들어, 반복문을 구성하는 page가 3개라고 한다면, 3개가 한번에 할당되는 것이 좋다. 2개가 할당된다면, 매 loop마다 page fault가 일어나 원활한 수행에 방해가 된다. 3가지 Allocation 방법 (∝ Local repacement) Equal Allocation: 모든 프로세스에 똑같은 갯수 할당 Proportional Allocation: 프로세스 크기에 비례하여 할당 Priority Allocation: 프로세스의 priority에 따라 다르게 할당 Global replacement VS Local replacement Global replacement는 따로 프로세스마다 할당되어야할 frame 개수를 정해놓지 않더라도 알고리즘을 수행하다보면 알아서 필요한 프로세스에 page가 더 많이 할당되는 것을 말한다. 반면에, Local replacement는 프로세스마다 할당할 page 개수를 정해둔 것을 말한다. Thrashing 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못한 경우 발생한다. 위 그래프와 같이, 메모리에 동시에 올라온 프로세스 개수가 많아질수록, 특정 순간에 CPU 이용률이 급감해버리는 thrashing 현상이 발생한다. 보통 위와 같은 과정을 거쳐 thrashing으로 이어진다. 이를 해결하기 위해 두 가지 알고리즘을 소개한다. Working-Set Algorithm VS PFF (Page-Fault Frequency) Scheme (∝ Global repacement) Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-06-11

9-1. 가상 메모리

이번 챕터부터는 메모리 관리 기법 중 paging 기법을 사용하는 것을 가정한다. 실제로도 대부분의 시스템은 paging 기법을 채택하고 있다. Demand Paging 실제로 특정 page에 대한 요청이 있을 때 해당 page를 메모리에 올리는 것을 말한다. 프로그램에는 안정적인 실행을 위해 방어적으로 넣은 자주 쓰이지 않는 코드 영역들이 매우 많이 존재한다. 그렇기에 실제로 쓰이는 코드들만 메모리에 올리면, I/O 양과 메모리 사용량을 크게 감소시킬 수 있고 더 많은 사용자들이 멀티 프로세싱할 수 있는 환경이 만들어진다. Demand Paging에서 페이지 테이블의 entry에 존재하는 valid/invalid bit의 역할을 살펴보자. Invalid는 주소 영역에서 사용되지 않는 부분이나 페이지가 물리적 메모리에 올라와 있지 않은 상황을 의미한다. 처음에는 모든 page entry가 invalid로 초기화되어 있다. 그리고 주소 변환시 해당 페이지가 invalid로 세팅되어 있다면, page fault를 일으킴과 동시에 trap을 걸어 운영체제에게 CPU를 넘기고 page fault가 난 페이지를 메모리에 올리게끔 한다. Page fault에 대한 처리 루틴은 운영체제에 정의되어 있으며, 구체적으로는 위 그림과 같은 과정을 거친다. Backing storage에서 메모리에 페이지를 올리는 디스크 I/O는 시간이 오래걸리기 때문에, page fault가 얼마나 나느냐에 따라 메모리 접근 시간에 차이가 날 수 있다. 위의 Effective Access Time에서 p는 보통 굉장히 작아서 대부분의 경우 page fault가 나지 않는다. 하지만, 적은 확률로 page fault가 나는 상황에서는 위의 붉은 글씨의 요인들처럼 큰 시간적 오버헤드가 발생함을 유의한다. Page replacement 메모리에 여유 공간이 필요할 때, 운영체제가 어떤 frame을 빼앗아서 page를 쫒아낼지 결정하는 것을 Page replacement라고 한다. 이것을 구현하는 알고리즘을 Replacement Algorithm이라고 하는데, page fault rate을 최소화하는 방향으로 page를 쫒아내도록 알고리즘을 잘 설정해야 한다. Optimal Algorithm (실제로 쓰이진 않음) Optimal Algorithm은 가장 먼 미래에 참조되는 page를 replace하는 방식으로 Page fault를 최소화하는 알고리즘이다. 위 예시처럼, 미래의 page 참조를 전부 안다고 가정하고 진행하기 때문에 실제로 시스템에서 쓰이진 않지만, 가장 최고의 성능을 나타내는 지표로서 다른 알고리즘들의 성능에 대한 upper bound를 제공한다. FIFO Algorithm (실제로 쓰임) 간단하게 먼저 올라온 page를 먼저 쫒아내는 방식이다. 특이한 점은 frame 수를 늘리면 성능이 좋아져야 할 것 같지만, FIFO 알고리즘에서는 오히려 성능이 떨어지는 현상이 발생하는데, 이를 FIFO Anomaly 혹은 Belady’s Anomaly라고 부른다. LRU (Least Recently Used) Algorithm (실제로 쓰임) LRU(Least Recently Used) 알고리즘은 참조의 측면에서 가장 오래 전에 참조된 page를 쫒아내는 방법이다. 얼핏보면 FIFO와 비슷하지만, FIFO보다 효율적으로 동작하여 더 많이 쓰이는 알고리즘이다. LFU (Least Frequently Used) Algorithm (실제로 쓰임) LFU(Least Frequently Used) 알고리즘은 참조 횟수가 가장 적은 page를 쫒아내는 방법이다. 동일한 참조 횟수를 기록 중인 page가 여럿 있을 때는 일반적으로 큰 의미를 두지 않고 알고리즘이 임의로 쫒아낸다. 다만, 그 중에서도 가장 오래 전에 참조된 page를 쫒아내도록 알고리즘을 설계하는 것이 성능 향상에 이로울 수 있다. LRU VS LFU LRU는 참조 시점의 최근성을 반영한다. 반면에 LFU는 장기적인 측면에서 page의 인기도를 더 정확히 반영하는 장점이 있다. 다만, LFU는 LRU보다 구현이 복잡하다. LRU의 경우는 시간에 따라 일렬로 줄 세우고 가장 최근에 참조했던 페이지를 내쫒으면 된다. 따라서, Linked List 자료구조로 구현하여, 페이지를 내쫒는 작업을 O(1) 시간 복잡도로 수행하게끔 한다. 반면에, LFU는 페이지의 참조 빈도가 계속 바뀌기 때문에, heap 자료구조를 사용하여 지속적으로 정렬하는 방법을 사용한다. 이 경우 페이지를 내쫒는 작업은 O(log n)의 시간 복잡도로 수행된다. Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-06-10

8-2. 메모리 관리

Allocation of Physical Memory 메모리는 일반적으로 Interrupt vector와 함께 낮은 주소 영역을 사용하는 OS 상주 영역과 높은 주소 영역을 사용하는 사용자 프로세스 영역 둘로 나뉜다. 사용자 프로세스 영역의 할당 방법 1. Contiguous allocation (연속 할당) 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것이다. 연속 할당 방식은 두 가지가 존재한다. 고정 분할 방식 프로그램이 들어갈 사용자 메모리 영역을 미리 파티션(partition)으로 나눠놓는 것을 말한다. 이 경우, 동시에 메모리에 load되는 프로그램의 수가 제한되고 최대 수행 가능 프로그램 크기도 제한된다. 위 그림을 예시로 보면 메모리 영역은 이미 고정되어 나뉘어져 있고 프로그램 A와 B는 각각 자신의 크기에 맞는 파티션을 찾아 그 위에서 실행된다. 이 과정에서 프로그램을 담을만큼 충분한 용량을 가지지 못해 남겨진 메모리 영역을 의미하는 외부 조각과 파티션에서 프로그램이 실행되고 남은 메모리 영역을 의미하는 내부 조각이 발생한다. 가변 분할 방식 사용자 메모리 영역을 미리 나눠놓지 않는 방법을 말한다. 가변 분할 방식은 프로그램의 크기를 고려해 프로그램들을 차곡차곡 메모리 영역에 할당한다. 이 때, 앞서 실행된 프로그램이 종료되거나 새로운 프로그램이 실행됨에 따라 남겨져버는 메모리 영역, 즉 외부조각이 발생할 수 있다. 이 가용 메모리 공간을 Hole이라고 하는데, 운영체제는 할당 공간과 흩어져 있는 가용 공간(hole)을 잘 고려해서 프로그램의 실행을 매끄럽게 도와야 한다. 한편, 가변 분할 방식에서는 미리 정해진 파티션이 없기 때문에 내부 조각은 발생하지 않는다. Dynamic Storage Allocation Problem 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제를 말한다. First-fit과 Best-fit이 Worst-fit보다 속도와 공간 이용률 측면에서 더 효과적인 것으로 알려져 있다. First-fit Size가 n이상인 것 중에 최초로 찾아지는 hole에 할당하는 방법이다. Best-fit Size가 n이상인 가장 작은 hole을 찾아서 할당하는 방법이다. 많은 수의 아주 작은 hole들이 생성되며, hole들의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야 한다. Worst-fit 가장 큰 hole에 할당하는 방법이다. 이 역시 hole들의 리스트가 크기순으로 정렬되어 있지 않으면, 모든 리스트를 탐색해야 하고, Best-fit과는 달리 상대적으로 아주 큰 hole들이 생성된다. Compaction 사용 중인 메모리 영역을 한 군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만듦으로써 외부조각 문제를 해결하는 방법이다. 다만, Run time binding이 지원되어야 수행 가능하고, 최소한의 메모리 이동을 고려하는 복잡한 문제를 해결해야 하기 때문에 비용이 매우 많이 든다는 단점이 있다. 2. Noncontiguous allocation 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있는 방법을 말한다. Paging 기법 프로세스의 virtual memory를 동일한 사이즈의 page로 나누는 방법이다. 따라서 virtual memory의 내용이 page 단위로 비연속적으로 저장되며, 일부는 backing storage에, 일부는 physical memory에 저장된다. Paging 기법을 사용하기 위해서 physical memory를 동일한 크기의 frame으로, logical memory를 동일한 크기의 page로(frame과 같은 크기) 나눠야 한다. 그리고 기존과 달리 page table을 사용해서 logical address를 physical address로 주소 변환한다. 이 기법을 사용하면 가장 마지막 페이지로 인해 발생하는 내부 조각은 존재할 수 있지만, 마지막 page를 제외한 모든 page와 frame의 크기가 동일하기 때문에 외부 조각은 발생하지 않는다. 위 그림으로 조금 더 자세히 살펴보자. CPU가 어떤 논리적 주소를 주면, 논리적 주소의 앞 부분 p는 페이지 번호가 되고, 뒷 부분 d는 페이지 번호의 주소에서 얼마나 떨어져 있는지 알려주는 offset이 된다. 따라서, p를 page table의 entry(=index)로 사용하면, 페이지 번호에 해당하는 frame 번호 f를 구할 수 있고 논리적 주소를 물리적 주소로 변환할 수 있게 된다. 그렇다면 위의 page table의 구현은 어떻게 이루어질까? 앞서 살펴본 기존의 연속 할당 방식에서는 MMU를 이용한 2개의 레지스터(base register, limit register)만으로 주소변환을 충분히 할 수 있었다. 하지만 불연속 할당 방식을 사용하는 paging 기법에서는 page table을 따로 두고 기존과 다르게 처리한다. 일단, Paging 기법에서 프로세스는 주로 4KB의 크기의 수많은 페이지로 나뉘어진다. 그래서 상당히 많은 entry 정보를 저장해야 하는 page table은 그 용량을 감당하기 위해 physical memory에 상주하게 된다. 즉, CPU의 논리적 주소를 주소 변환하기 위해서는 총 2번(page table 접근 한 번, 실제 data/instruction 접근 한 번) physical memory에 접근하게 된다. Page table 운용에 사용되는 Register의 경우에는 page table을 가리키는 Page-table base register(PTBR)과 테이블 크기를 보관하는 Page-table length register(PTLR)이라는 2개의 register를 사용한다. 또한, 속도를 높이기 위한 하드웨어 측면의 방책으로 associative register나 translation look-aside buffer(TLB)라는 고속 lookup hardware cache를 사용한다. TLB에 대하여 그림으로 살펴보자. 위 그림처럼 paging 기법에서 주소 변환을 수행하려면 두 번의 메모리 접근을 해야 하기 때문에, TLB라는 하드웨어의 지원을 통해 속도를 더 빠르게 가져갈 필요가 있다. TLB는 실제 캐쉬 메모리와는 다르지만 주소 변환만을 위한 일종의 캐쉬 메모리 역할을 하는데, page table에서 자주 쓰이는 일부 entry들을 TLB에 저장해두고 메모리보다 조금 윗단에서 entry를 빠르게 가져다 쓸 수 있게 해주는 역할을 한다. 즉, CPU가 주는 논리적 주소를 주소 변환할 때 먼저 TLB를 살펴보고, 만약에 TLB에 해당 entry가 있다면 한 번의 메모리 접근을, TLB에 entry가 없다면 원래대로 두 번의 메모리 접근을 한다. 유의할 점은 page table의 경우 page number를 index로 바로 frame number를 알 수 있는 반면, TLB는 page number와 frame number가 쌍으로 이루어져 있어서 frame number를 알고 싶다면 전체 TLB의 원소를 모두 다 검색해봐야 검색 유무를 판단할 수 있다는 것이다. 따라서, 이 검색을 원활히 진행시키기 위해 associative register들로 parallel search가 가능하도록 해 단번에 frame number를 알 수 있도록 만든다. 또한, page table은 각 프로세스마다 다르게 존재하므로, 이에 대응하기 위해 context switch가 일어날 때마다 TLB는 flush되어야 한다. 앞서 살펴본 것을 토대로 메모리 접근 시간을 파악해보면 위와 같다. 결론적으로 1보다 작은 값 입실론과 1에 아주 가까운 알파 값으로 인해 EAT(Effective Access Time)는 2보다 작아지게 되어, 적어도 메모리에 두 번 접근하는 것보다 나은 방법이 된다는 것이 증명된다. Two-Level Page Table (2단계 페이지 테이블) Two-Level Page Table은 위와 같이 바깥 page table과 안쪽 page table 두 개를 활용하는 방법이다. 본래의 Page Table에서는 공간적 낭비가 발생하기 때문에, 이를 막고자 나타난 것이 Two-Level Page Table이다. 현대 컴퓨터는 address space가 매우 큰 프로그램도 잘 지원할 수 있는데, 용량이 큰 프로세스라고 할지라도 대부분의 프로그램은 자신의 주소 공간의 매우 일부분만 사용한다. 이 경우, 기존의 page table은 배열이기 때문에 논리적 주소의 일부분만 사용되어 빈공간이 생기더라도 전체의 주소 공간을 저장할 수 있게끔 생성된다. 즉, 이 과정에서 생기는 빈공간들이 공간적 비효율성을 야기한다. 사실 바깥 page table과 안쪽 page table 두 가지를 사용하니까 시간적으로나 공간적으로나 더 낭비가 클 것 같지만 실제로는 충분한 이점이 있다. 앞서 말햇듯이 프로세스의 주소 공간 중 거의 쓰이지 않는 부분이 훨씬 많기 때문에, 바깥 page table에서 해당 부분들을 Null로 처리해버리면 Null로 처리된 곳에는 안쪽 page table이 생성되지 않아 공간적인 낭비가 감소하는 효과가 있다. Two-Level Page Table은 위와 같이 바깥 page table 속의 entry마다 안쪽 page table을 둬서 이 page table들을 두 번 거친 후에 물리적 메모리 주소에 도달하게 한다. 이 때, 안쪽 page table 각각의 크기는 4KB로 본래의 page의 크기와 동일하게 된다. Two-Level Page Table의 주소 공간에 대한 bit 수 분배는 위의 예시와 같으니 참고하도록 하자. Multi-Level Paging 프로세스의 주소 공간이 더 커지면, 다단계 페이지 테이블이 효율적이다. 페이지 테이블이 더 많아져 메모리 접근 횟수 역시 더 많아질 수 있지만, 공간 낭비를 더욱 줄일 수 있다. 또한, TLB를 사용하면 메모리 접근 횟수 및 총 소요 시간도 크게 줄일 수 있다. 예를 들어, 4단계 페이지 테이블을 이용하는 경우만 해도 위와 같이 메모리 접근 시간이 크게 소요되지 않음을 알 수 있다. Paging 기법에 관한 몇 가지 Issue 페이지 테이블의 Valid / Invalid bit 페이지 테이블에는 해당 페이지가 실제로 사용되느냐 안되느냐를 표현하는 valid-invaild bit이 존재한다. Valid는 해당 주소의 frame에 프로세스를 구성하는 유효한 내용이 있어 접근을 허용함을 뜻하고, invalid는 해당 주소의 frame에 유효한 내용이 없어 접근을 허용하지 않음을 뜻한다. Invalid에서 해당 주소 frame에 유효한 내용이 없다는 것은 프로세스가 해당 주소 부분을 사용하지 않는 경우 혹은 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우를 말한다. 만일 프로세스의 주소 공간에서 거의 쓰이지 않는 영역에 해당하는 페이지라면 invalid임을 표시해 구분하는 것이 유용하다. Frame number를 0으로 두는 것만으로는 그것이 0번 frame을 의미하는 것인지 메모리에 올라와 있지 않다는 것을 말하는지 분별할 수 없기 때문이다. 페이지 테이블의 Protection bit 페이지 테이블에는 또 하나의 bit이 존재한다. Protection bit이라고 불리는 이 bit은 해당 page의 연산(read/write/read-only)에 대한 권한을 부여한다. 프로세스에는 code, stack, data 영역이 있는데, code 부분에 해당하는 page의 경우 내용이 바뀌면 안되기 때문에 read only 연산만 가능하게 설정하고 다른 영역은 read, write 모두 가능하게 설정한다. Inverted Page Table 기존 page table의 큰 공간 낭비 문제를 해결하기 위한 또 하나의 방법이다. 기존 page table이 page number에 따라 page table entry를 만드는 것과 달리, inverted page table은 frame number에 따라 page table entry를 만든다. 그렇기에 page table도 프로세스마다 존재하는 것이 아니라 시스템에 단 하나 존재한다. 그리고 이를 보완하기 위해 page table 각각의 entry에 프로세스 ID를 추가로 넣어줘 어떤 프로세스의 page인지 구분할 수 있도록 한다. Inverted 방식의 page table은 한 개만 존재함으로써 공간 낭비를 극적으로 줄일 수 있다. 다만, 주소 변환을 하기 위한 시간적 overhead는 커지기 때문에, associative register를 활용해 병렬적으로 page table 검색을 하게끔하는 방식을 보완해 사용한다. Shared Page Shared page는 shared code가 page로 나뉠 때 사용되는 용어이다. Shared Code(=Re-entrant Code =Pure code)는 프로세스마다 동일한 프로그램을 실행함으로 인해 같은 코드가 쓰이는 경우에 read-only 상태로 공유하고 메모리에 올리는 하나의 코드를 말한다. 예를 들어, Text editor나 compiler, window systems 같은 프로그램들은 굳이 코드를 여러번 중복할 필요가 없기 때문에, shared code로 공유한다. 이러한 shared code는 모든 프로세스의 논리적 주소 공간에서 동일한 위치에 있어야 하며, 각 프로세스의 독립적인 private code와 data는 프로세스의 논리적 주소 공간 어디에 위치해도 상관없다. Segmentation 기법 이제 또 다른 대표적인 불연속 할당 방식으로 Segmentation 기법을 알아보자. Segmentation은 프로그램을 의미 단위로 구성된 여러개의 segment로 나누어 할당하는 방식이다. Segment는 크게는 프로그램 전체, 작게는 함수 하나하나로 정의 될 수 있는데, 일반적으로 code, data, stack 영역이 하나씩 segment로 분류된다. Segmentation에서 논리적 주소는 segment-number와 offset으로 구성된다. 또한 Paging 기법과 비슷하지만 다르게 사용되는 segment table이 존재하며, 테이블 내 각각의 entry에는 segment의 물리적 주소 시작점을 담는 base와 segment의 길이를 담는 limit이 존재한다. 또한, 물리적 메모리에서 segment table의 위치를 담는 Segment-table base register(STBR)와 프로그램이 사용하는 segment의 수를 기록하는 Segment-table length register(STLR)가 존재한다. 위의 그림에서 CPU가 논리적 주소를 주게 되면, segment table에서 논리적 주소의 segment 번호 s에 해당하는 entry를 찾게 된다. 그리고 entry에서의 base 값과 논리적 주소의 offset d를 이용해 물리적 주소에 접근한다. 또한, 물리적 메모리에 접근하기 전에 해당 entry에서 limit 값을 확인하여, 논리적 주소의 offset 값이 프로그램의 주소 범위를 벗어나지 않았는지 파악한다. Paging 기법과 달리 각각의 Segement는 길이가 다르기 때문에, entry에 존재하는 limit 값을 통해 segment의 길이를 결정짓는 것이 중요하고, 이를 활용해 프로그램의 범위를 벗어나는 악의적인 접근에 대해 trap을 건다. Segmentation은 segment 각각의 길이가 동일하지 않으므로 외부조각이 발생하는 문제가 있다. 하지만, read/write/execution 등의 권한을 부여하는 protection 작업이나 각각의 프로세스가 동일한 코드를 공유하는 sharing 작업에서는 의미 단위를 강조하는 Segmentation이 매우 효과적이라는 장점도 있다. 위 그림은 Segmentation의 한 예시인데, paging 기법의 크기가 4KB인 수많은 page 개수에 비하면 segment의 개수는 현저히 적음을 알 수 있다. 프로그램이 의미 단위로 큼직큼직하게 쪼개지기 때문에 위 예시에서는 segment의 개수가 5개밖에 되지 않는다. 대신 segment의 용량은 4KB로 크기가 고정되어 있는 page에 비하면 매우 커질 수 있다. 또한, segment의 개수가 적어짐에 따라 segment table의 entry 개수도 적어지므로, page table과 달리 table로 인한 공간 낭비가 현저하게 감소한다. Paged Segmentation (=Segmentation with Paging) Paged Segmentation은 Paging 기법과 Segmentation 기법을 혼합하여 Segmentation된 각각의 segment에 paging을 적용하는 방법이다. 이렇게 혼합 방식을 사용하면 Segmentation에서 발생하는 외부 조각 문제를 해결하고 protection과 sharing은 본래의 의미 단위대로 처리할 수 있어 유용하다. 실제로도 순수한 Segmentation만을 사용하는 컴퓨터는 없으며 Segmentation을 사용한다면 이렇게 Paging과 혼합적으로 운용한다. Paged Segmentation의 과정을 살펴보자. 위 그림에서 CPU가 논리적 주소를 주면 segment 번호 s를 사용해 segment table의 해당 entry에 접근한다. 그리고 offset d가 해당 entry의 limit 값을 넘어가지 않는다면, d에 존재하는 페이지 번호 p를 사용해 해당 segment에 mapping된 page table의 entry에 접근한다.(offset d가 limit 값을 넘어간다면, trap을 건다.) 그 후, entry에 해당하는 프레임 번호 f와 d에 존재하는 offset d’을 더해 물리적 주소로 변환을 완료한다. Memory Management 챕터에 관하여 메모리 관리 챕터는 물리적 메모리에 관하여 다뤘다. 이 메모리 접근 과정에서 운영체제의 역할은 없었고, 오직 하드웨어의 역할만 있었음을 유의하자. Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-06-09

8-1. 메모리 관리

Symbolic Address VS Logical Address VS Physical Address 1. Symbolic Address 프로그래머 입장에서 메모리를 다룰 때, 숫자가 아닌 변수명, 함수명 등으로 메모리를 조작하는 상징적 주소 Symbolic Address가 compile되면 숫자로 된 Logical Address가 됨 2. Logical Address (=Virtual Address) 프로세스마다 독립적으로 가지는 주소 공간 각 프로세스마다 0번지부터 시작 CPU가 보는 주소 3. Physical Address 실제 메모리에 올라가는 위치 프로그램이 실행될 때, Logical Address를 Physical Address로 주소 변환 (주소 바인딩) 주소 바인딩 (Address Binding) 어떤 프로그램이 실행되기 위해서는 물리적 주소에 올라가야 하는데, 물리적인 주소 어디로 올라갈지 결정하는 것을 의미한다. 현대 컴퓨터는 어떤 프로그램을 실행할 시 프로그램 내 instruction들을 산발적으로 여러 메모리 상 위치에 나눠 실행하지만, 여기서는 하나의 프로그램을 통째로 메모리 상 균일한 위치에 올린다고 가정하고 진행한다. 1. 주소 바인딩이 실현되는 3가지 시점 Compile time binding Physical Address가 컴파일 시에 정해져서 Logical Address와 Physical Address와 같음 이 때, 컴파일러가 생성한 코드를 절대 코드(absolute code)라고 지칭 메모리가 많이 비어있을 때도 특정 위치부터 주소를 바인딩하기 때문에 비효율적 시작 위치 변경시 재컴파일해야 함 과거에 쓰이던 방식 Load time binding 프로그램이 실행되는 타이밍에 Loader가 Physical Address를 부여함 정해진 위치가 아닌 비어 있는 메모리 위치에 주소를 바인딩 이 때, 컴파일러가 생성한 코드는 재배치가능 코드(relocatable code)라고 지칭 Execution time binding (=Run time binding) Physical Address를 부여하는 타이밍과 방식은 Load time binding과 동일 프로그램 실행 중에도 프로세스의 메모리 상 위치가 바뀔 수 있다는 점이 특징 CPU가 주소를 참조할 때마다 binding을 점검 이를 위해서 하드웨어적인 지원이 필요 (ex. MMU) 주소 바인딩이 되더라도 Logical Address는 코드상에 남아 있으므로, CPU는 Physical Address가 아닌 이 Logical Address를 참조하고 요청해 연산을 수행한다. 2. MMU (Memory-Management Unit) Logical Address를 Physical Address로 mapping해 주는 Hardware device Execution time binding을 지원 2개의 register를 이용해 주소 변환 지원 (relocation register, limit register) Relocation register(=base register): 접근할 수 있는 물리적 메모리 주소의 최소값 Limit register: 논리적 주소의 범위 user program은 logical address만 다루며, 실제 physical address는 볼 수 없고 알 필요도 없음 MMU scheme 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register 값을 더한다. 아래에 예시를 살펴보자. 위 그림은 process p1이 실행되어 있는 상황에서 CPU가 p1의 한 instruction을 요청하는 과정을 담고 있다. 먼저 왼쪽 하단의 p1 그림은 p1의 논리적 주소를 보여준다. p1은 0~3000번지까지의 논리적 주소를 가진다. 이 때, limit register는 p1의 가장 끝 주소인 3000을 기억한다. 또한, 현재 CPU는 0~3000까지의 논리적 주소 중 346번지에 있는 instruction을 요청한 상황이다. 물리적 주소 입장에서 보면, p1은 실행될 때 14000~17000번지까지의 주소를 부여 받았다. 논리적 주소의 범위인 3000만큼을 물리적 주소도 동일하게 받았다. 이 때, relocation register는 p1의 물리적 주소 시작위치인 14000을 기억한다. 그렇다면 CPU가 요청한 instruction의 물리적 메모리 상 위치는 어떻게 될까? CPU가 요청한 논리적 주소 346번지 instruction은 relocation register에 저장된 물리적 위치 시작 주소 14000에 346을 그대로 더한 14346번지 물리적 주소에 존재한다. 즉, 논리적 주소는 상대적으로 표현한 것이기 때문에 실제 위치에서 상대적으로 계산하면 원하는 instruction의 물리적 주소를 알 수 있다. 한편, limit register는 어떤 프로그램이 악의적으로 프로세스의 메모리 범위를 벗어나는 주소를 요청하는 경우를 막기 위해 존재한다. 예를 들어, 위 그림에서 CPU가 요청한 논리적 주소가 4000이라고 하면 p1의 물리적 주소 범위인 14000~17000을 벗어나 18000의 주소를 요청한 것이기 때문에 limit register가 이를 막는다. MMU의 지원을 받아 주소 변환을 하는 과정을 일반화하면 위와 같이 도식화할 수 있다. CPU가 어떤 instruction의 logical address를 요청하면 그 주소가 limit register에 저장된 값을 넘지 않는지(논리 주소가 프로그램의 크기를 넘어가지 않는지) 확인한다. 만약에 값을 넘어가면, trap이 걸려 운영체제가 해당 프로그램의 CPU 제어권을 앗아가고 범위를 벗어난 악의적인 시도에 대해 프로그램을 종료시키는 등의 제제를 가한다. 값이 벗어나지 않는다면, 요청한 logical address 값에 relocation register에 저장된 값을 더해 physical address로 주소 변환을 하고, 해당 주소에 존재하는 내용을 CPU에게 전달한다. Dynamic Loading 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것을 말한다. 프로그램의 코드는 모든 코드가 항상 일정하게 쓰이는 것이 아니라 오류 처리 루틴같은 상대적으로 덜 쓰이는 부분이 존재한다. Dynamic Loading은 이렇게 가끔씩 사용되는 많은 양의 코드를 다루는 경우에서 메모리의 효율성을 크게 증대시킨다. 다만, 이 개념은 운영체제가 제공하는 라이브러리로 프로그래머가 직접 구현하는 것을 의미하며, 운영체제가 스스로 메모리에 올리고 쫒아내는 것을 관리하는 paging system과는 다른 개념임을 유의해야 한다. Overlays 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올리는 것을 말한다. Dynamic Loading과 그 의미가 거의 동일하나 초창기 컴퓨터 시스템에서 사용되던 말이다. 작은 공간의 메모리에 큰 프로그램을 실행시키기 위해 프로그래머가 직접 수작업으로 프로그램을 분할해 메모리에 올리던 방법으로, 운영체제의 지원없이 구현했기 때문에 프로그래밍이 매우 복잡했다. Swapping Swapping 프로세스를 일시적으로 메모리에서 backing store로 쫒아내는 것을 의미한다. 메모리에서 쫒았다가 다시 올리는 작업이므로, 프로세스가 특정 위치에 반드시 복귀해야 하는 Compile time binding, Load time binding보다는 빈 메모리 영역 아무곳에나 프로세스를 올릴 수 있는 Execution time binding에서 더 적합하다. Swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)에 해당한다. Backing store (=swap area) 하드 디스크의 일부분으로, 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간을 말한다. Swap in / Swap out 프로세스가 메모리에서 쫒겨나 backing store로 내려가는 것을 Swap out이라고 하고, backing store에서 다시 메모리로 올라가는 것을 Swap in이라고 한다. 일반적으로 중기 스케줄러가 메모리에 올라와 있는 프로세스들의 CPU priority를 고려하여 swap out시킬 프로세스를 선정한다. Dynamic Linking Linking을 실행 시간(execute time)까지 미루는 기법이다. 본래의 Linking(=Static Linking)은 실행 파일을 만들 때, 라이브러리 실행 코드가 실행 파일 코드에 포함되어 실행 파일의 크기가 커진다. 즉, 같은 라이브러리를 쓰는 프로세스라고 하더라도 각각의 프로세스 주소 공간에 라이브러리 코드가 매 번 들어 있는 실행파일이 생성된다. 반면에, Dynamic Linking은 만들어진 실행 파일 속에 라이브러리 루틴의 위치를 찾기 위한 포인터(stub라고 하는 작은 코드)만 넣어 두고 라이브러리 코드 전체는 포함시키지 않는다. 그리고 실행 파일에서 해당 라이브러리를 호출할 시, 포인터로 라이브러리 파일의 위치를 찾아 해당 라이브러리 코드를 메모리에 올리고 실행한다. 만일, 다른 프로세스가 라이브러리를 호출해 이미 메모리에 올라와 있는 경우, 실행만 한다. 본래의 Linking에 비해 메모리 공간을 덜 잡아먹고 실행 파일의 크기가 줄어든다는 점에서 효율적이다. Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-06-08

7. Deadlock

Computer Science · 2021-06-03

6-2. Process Synchronization 문제

Computer Science · 2021-05-27

6-1. Process Synchronization 문제

Computer Science · 2021-05-27

5-2. CPU 스케줄링

Multi-level queue 우선도가 다른 ready queue Ready queue를 foreground(interactive)와 background(batch - no human interaction)으로 분리한다. 그리고 foreground에는 RR, background에는 FCFS 등으로 각 큐에 독립적인 스케줄링 알고리즘을 설계한다. 또한 어떤 큐에게 CPU를 줄 지 (그 이후에는 큐에 있는 어떤 프로세스에게 CPU를 줄 지)결정하는 작업이 필요한데, 이를 큐에 대한 스케줄링으로 해결한다. Fixed priority scheduling은 우선도를 최우선으로 하여 우선도가 높은 foreground에게 먼저 scheduling하고 그 다음 background에게 주는 방식이다. 이 방식에서는 starvation이 단점이 될 수 있다. 이에 대한 대안으로 Time Slice가 있는데, 이 스케줄링은 각 큐에 CPU time을 적절한 비율로 할당한다. (ex. foreground에 80% background에 20% CPU time 분배) Multi-level feedback queue 우선도가 높은 queue여도 상황에 따라 낮은 우선도 queue가 높은 우선도 queue보다 우선될 수 있다. Multi-level queue의 고정된 우선도라는 단점을 극복하기 위한 대안이다. 예를 들어, 들어오는 프로세스를 우선도가 가장 높은 queue에 줄 세우고 RR 방식을 사용하되, 우선도가 낮은 queue일수록 time quantum을 길게 준다. 그래서 time quantum 내에 프로세스가 완료되면 큐에서 내보내고, 완료되지 않았으면 다음으로 우선도가 높은 큐에 해당 프로세스를 줄 세운다. 이렇게 하면 CPU burst가 짧은 프로세스에 우선 순위를 더 많이 주고, CPU burst가 긴 프로세스의 우선도는 더 낮출 수 있다. 특수한 상황에서의 CPU Scheduling 1. Multiple-Processor Scheduling (간략히 다룸) Homogeneous Processor라면 Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있는가하면 어떤 프로세스는 특정 프로세서에서만 수행되어야 하는 경우가 존재하므로 이를 고려해야 한다. Load sharing 일부 프로세서에 job이 몰리지 않게 하는 적절한 메커니즘이 필요하다. 모든 CPU가 공동 큐를 사용하는 방법 혹은 각각의 CPU마다 별개의 큐를 사용하는 방법이 있다. Symmetric Multiprocessing (SMP) 각 프로세스가 각자 알아서 스케줄링을 결정한다. Asymmetric Multiprocessing 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 그것에 따른다. 2. Real-Time Scheduling Time sharing과 달리 미리 스케줄링을 계획하고 데드라인이 보장되도록하는 방식 Hard real-time systems 정해진 시간안에 반드시 끝내도록 스케줄링하는 것 Soft real-time computing (많이 쓰임) 영화 스트리밍과 같이 time sharing 시스템에서 다른 일반적인 프로세스들과 섞여서 실행되지만, 일반 프로세스에 비해 높은 priority를 갖게해 데드라인을 지키도록 지향하는 스케줄링. (조금은 데드라인을 어기는 것이 허용됨) 3. Thread Scheduling Local Scheduling User level thread의 경우 운영체제가 thread의 존재를 모르기 때문에, 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정한다. (운영체제는 CPU를 프로세스에게 전달만 하고 어떤 스레드에 CPU를 줄지는 해당 프로세스 내부에서 결정한다.) Global Scheduling Kernel level thread의 경우 운영체제가 thread의 존재를 알고 있기 때문에, 일반적인 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정한다. Algorithm Evaluation 1. Queueing models (Server를 CPU로 보자.) 확률분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산한다. (이론적 측면에서 많이 사용하는 방법) 2. Implementation (구현) & Mesurement (성능 측정) 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 및 비교한다. ex) 리눅스 커널에 나의 CPU 스케줄링 알고리즘을 구현해보고, 실제 프로그램을 돌려서 원래의 리눅스 환경과 나의 알고리즘이 적용되어 있는 리눅스 커널의 성능을 비교해본다.) 3. Simulation (모의 실험) 알고리즘을 모의 프로그램으로 작성 후 trace(실제 프로그램으로부터 추출한 input data)를 입력으로 하여 결과를 비교한다. Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-05-26

5-1. CPU 스케줄링

CPU Burst & I/O Burst 어떤 프로그램이 실행된다는 것은 CPU Burst와 I/O Burst가 번갈아 가며 일어나는 것을 의미한다. 프로그램의 종류에 따라 두 Burst의 빈번함이 다를 수 있는데, ① 사용자 관여가 많은 (키보드 입력, 모니터 출력 등이 잦은) 프로그램(interactive job)은 CPU Burst 시간이 짧아지면서 두 Burst가 번갈아 빈번히 나타나고, ② 과학 계산용 프로그램 같은 연산 시간이 긴 프로그램은 CPU Burst 시간이 길어지면서 I/O 비중이 크게 줄어든다. 위 그래프는 CPU Burst 시간과 그 빈도에 따라 프로그램들을 분류한 것인데, CPU Burst 시간이 짧을수록 프로그램의 CPU Burst 빈도가 잦음을 알 수 있다. 이 같이 CPU를 잡고 계산하는 것보다 I/O에 더 많은 시간을 사용하는 프로그램들을 I/O bound job이라고 하며, 반대로 계산 위주로 구성된 프로세스는 CPU bound job이라고 부른다. 여러 종류의 job(=process)이 섞여 있기 때문에, 그들을 적절한 CPU Scheduling이 필요하다. → CPU bound job이 CPU를 너무 오래 사용하면 효율성이 떨어지므로, I/O bound job(=Interactive한 job)에게 우선적으로 CPU를 주도록 지향하는 것이 CPU Scheduling의 주요한 목표이다. CPU Scheduler & Dispatcher 1. CPU Scheduler 운영체제의 여러 코드 중 CPU schedule 기능을 담당하는 코드를 지칭하는 용어다. Ready 상태의 프로세스 중 어떤 프로세스에게 CPU를 줄 지 결정한다. 2. Dispatcher 역시 운영체제의 여러 코드 중 특정 코드를 지칭하는 용어다. CPU 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다. 이 과정을 문맥 교환(Context Switch)이라고 한다. CPU Scheduling이 필요한 경우 1, 4의 스케줄링은 nonpreemptive(=자진 반납, 비선점형), 나머지 모든 스케줄링은 preemptive(=강제로 뺏음, 선점형, 대부분의 현대적인 CPU 스케줄링에서 사용) 3의 경우 일반적으로 원래 CPU를 점유하던 프로세스에게 timer가 끝날 때까지 CPU를 다시 쓰게 하지만, 만약 우선순위가 가장 높은 프로세스의 I/O가 완료된 것이었다면 해당 프로세스에게 CPU를 바로 넘기게 된다. Scheduling Criteria (CPU 스케줄링 성능 척도) 1. 시스템 입장에서의 성능 척도 : CPU 하나로 최대한 일을 많이 시키자! CPU utilization (이용률) : 전체 시간 중 CPU가 놀지 않고 일한 시간의 비율 Throughput (처리량) : 주어진 시간 동안 완료한 작업(process)의 수 2. 프로그램 입장에서의 성능 척도 : 내가 CPU를 빨리 얻어서 내가 빨리 끝나는 게 중요! Turnaround Time (소요시간, 반환시간) : CPU를 사용하기 위한 대기시간을 포함해 CPU를 사용완료하고 빠져나갈 때까지 걸린 총 시간 (다른 프로세스와 번갈아 CPU를 사용하게 되어도 그 모든 시간을 합하여 계산한다.) 프로세스가 CPU를 쓰러 대기열에 들어와서 CPU를 사용하고 I/O하러 나갈 때까지의 시간 ex) 중국집 손님이 코스요리를 시켰을 때, 중국집에 들어와서 요리를 기다리고 먹고를 반복하다가 다 먹고 나갈 때까지의 모든 시간 Waiting Time (대기시간) : Ready queue에서 대기하며 걸린 순수한 시간 CPU Burst와 I/O Burst가 번갈아 반복된다면, 그동안 생긴 여러 번의 대기 시간을 모두 합하여 계산하는 것이 아래의 Response Time과의 차이점이다. ex) 손님이 코스요리 음식을 기다린 모든 시간 Response Time (응답시간) : Ready queue에 들어와서 처음 CPU를 얻기까지 걸린 시간 (∝ time sharing) ex) 첫 번째 음식이 나올 때까지 기다린 시간 CPU Scheduling Algorithm 1. FCFS (First-Come First-Served) - nonpreemptive (비선점형) 먼저 들어온 프로세스를 먼저 처리한다. 먼저 들어온 프로세스가 CPU bound job일 경우 처리 시간이 길어지므로, 효율적인 스케줄링은 아니다. ex 1) 0초 대에서 프로세스들이 간발의 차이로 P1, P2, P3 순으로 들어왔을 때 ex 2) 0초 대에서 프로세스들이 간발의 차이로 P2, P3, P1 순으로 들어왔을 때 FCFS는 ex 1과 ex 2의 waiting time 같이 들어온 작업의 순서에 따라 결과 차이가 크게 나타나는 비효율성이 있다. 이처럼 작업 시간이 긴 프로세스에 의해 작업 시간이 짧은 프로세스들이 실행되지 못하는 상황을 Convoy effect(호위 효과)라고 한다. 2. SJF (Shortest-Job-First) CPU Burst가 짧은 프로세스에게 CPU 제어권을 제일 먼저 스케줄한다. 이 때, 각 프로세스의 다음 번 CPU Burst time을 고려하여 스케줄링에 활용한다. Nonpreemptive SJF 일단 CPU를 잡으면 해당 프로세스의 CPU Burst가 완료될 때까지 CPU를 선점(preemption)당하지 않는다. → 프로세스가 CPU를 다 사용하고 나가는 시점에 CPU 스케줄링을 결정 ex) Preemptive SJF (SRTF = Shortest-Remaining-Time-First) 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗는다. 주어진 프로세스들에 대하여 minimum average waiting time을 보장한다. (어떤 알고리즘도 이 waiting time 보다 빠를 수 없다.) → 새로운 프로세스가 들어올 때와 프로세스가 빠져 나갈 때, 두 가지 시점에서 CPU 스케줄링이 이뤄진다. ex) SJF의 문제점 Starvation (기아 현상) : 우선도가 낮은 프로세스(=CPU burst time이 긴 프로세스)는 영원히 실행되지 못할 수 있다. CPU burst time의 추정 : CPU burst time은 추정만 가능하기에 실제 정확한 시간을 알고 SJF를 수행하기는 어렵다. CPU burst time 추정은 과거의 CPU 사용 흔적을 바탕으로 exponetial averaging 기법을 사용해 이뤄진다. 이 기법은 과거의 흔적일수록 덜 반영하고 최근 흔적일수록 많이 반영하는 흐름을 가진다. 3. Priority Scheduling 높은 우선 순위를 가지는 프로세스에게 CPU를 할당한다. 작은 정수가 high priority를 나타낸다. (SJF도 일종의 Priority Scheduling → priority = predicted next CPU burst time) Nonpreemptive : CPU를 선점한 프로세스에게서 CPU를 빼앗지 않는다. Preemptive : 우선도에 따라 CPU를 빼앗긴다. (SJF 설명과 유사) Problem : Starvation (기아 현상)!!! → Solution) Aging : 시간이 지남에 따라 우선도가 낮은 프로세스의 우선도를 높인다. 4. Round Robin (RR) - Preemptive (선점형), 현대적 CPU Scheduling 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가지며 이 할당 시간이 지나면 CPU를 선점당하고 ready queue의 제일 뒤로 가서 다시 줄을 선다. n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다. (어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.) RR의 특징 Response Time 빨라지는 장점 Waiting Time은 CPU burst time이 긴 프로세스일수록 길고 반대의 경우 짧음 Performance q large → FCFS q small → context switch 오버헤드가 커진다. ex) Time quantum이 20일 때 → 일반적으로 SJF보다 average turnaround time이나 waiting time은 길어질 수 있지만 response time은 더 짧다. 또한, CPU 실행 시간이 동일한 프로세스들일 경우 RR이 비효율적일 수 있지만, 일반적으로는 CPU 실행 시간이 다르기 때문에 대부분에서 효율적이다. Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-05-26

4-2. 프로세스 관리

프로세스의 생성, 실행 및 종료에 관한 시스템 콜 프로세스 관리 시스템 콜 정리 1. fork() 시스템콜 위 그림의 두 코드는 부모 프로세스(좌), 자녀 프로세스(우)이다. 처음 부모 프로세스가 코드를 수행하다가 fork 시스템 콜을 만나면, 부모 프로세스를 똑같이 복사해 자녀 프로세스를 만들고 이후 명령을 계속 실행한다. 자녀 프로세스는 부모 프로세스의 Program Counter를 그대로 복제했기 때문에, 부모 프로세스와 마찬가지로 fork의 바로 밑 코드부터 실행한다. 또한, 부모 프로세스는 fork의 return 값으로 양수, 자녀 프로세스는 0을 pid에 취해 서로를 구분한다. 2. exec() 시스템콜 fork로 복사한 프로세스를 다른 프로그램으로 다시 덮어쓰기 위해 exec 시스템콜을 사용한다. 위와 같은 경우는 execlp 함수를 만나면, exec 시스템 콜이 발생해 복사한 자녀 프로세스에 새로 date 파일을 덮어써 실행하게 된다. 따라서, date가 실행되면 위 그림에 보이는 원래의 자녀 프로세스의 코드로는 다시 돌아갈 수 없다. 3. wait() 시스템콜 부모 프로세스가 wait 시스템 콜을 걸면, 부모 프로세스는 자식 프로세스가 종료될 때까지 blocked 상태가 된다. 자식 프로세스가 종료되면 부모 프로세스는 위 그림 처럼 wait 뒤에 있는 S2 코드를 계속 실행한다. (자식이 종료될 때까지 부모가 기다리는 모델에 해당) ex) 쉘 프롬프트의 커서가 깜빡이는 상태에서 프로그램을 실행 시 자식 프로세스 형태로 실행되고, 쉘 프롬프트 프로그램은 부모 프로세스로서 자식 프로세스가 종료될 때까지 기다렸다가(blocked 상태) 다시 실행된다. 4. exit() 시스템콜 자발적 종료 마지막 statement 수행 후 exit() 시스템 콜을 통해 이루어진다. 프로그램에 명시적으로 적어주지 않아도 main 함수가 리턴되는 위치로 컴파일러가 넣어준다. 비자발적 종료 부모 프로세스가 자식 프로세스를 강제 종료 시킬 때 ex) 자식 프로세스가 한계치를 넘어서는 자원을 요청할 때, 자식에게 할당된 태스크가 더 이상 필요하지 않을 때 부모가 종료될 때 (프로세스는 항상 자식이 먼저 종료되고 부모가 종료됨) 키보드로 kill, break 등을 칠 때 프로세스 간 협력 독립적 프로세스 프로세스는 각자의 주소 공간을 가지고 수행되므로 원칙적으로 하나의 프로세스는 다른 프로세스의 수행에 영향을 미치지 못한다. 협력 프로세스 어떤 경우에는 프로세스 협력 메커니즘을 통해 하나의 프로세스가 다른 프로세스의 수행에 영향을 미치며 서로 정보를 교환하는 것이 효율적일 수 있다. 프로세스 간 협력 메커니즘 (IPC: Interprocess Communication) massage passing : 커널을 통해 메시지를 전달한다. (프로세스들끼리 직접은 불가능하다.) Message system : 프로세스 사이에 공유 변수를 일체 사용하지 않고 통신하는 시스템 Direct Communication : 통신하려는 프로세스의 이름을 명시적으로 표시 Indirect Communication : mailbox(혹은 port)를 통해 메시지를 간접 전달 (프로세스 이름을 명시하지 않으므로 다른 프로세스가 열어볼 수 도 있음) shared memory : (원칙적으로는 안되지만) 서로 다른 프로세스 간에도 일부 주소 공간을 공유하게 하는 메커니즘 Thread는 하나의 프로세스이므로 프로세스 간 협력으로 보기에는 어렵다! Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-05-26

4-1. 프로세스 생성과 종료

프로세스의 생성 부모 프로세스가 자식 프로세스를 Copy-on-write(COW) 기법으로 생성한다. COW는 무언가의 변경(write)이 있을 때, 부모의 주소 공간 중 변화가 있는 부분을 copy해 자식의 주소 공간을 만드는 기법이다. 또한, 자식이 자식을 생성하고 그 수가 많아지면 프로세스는 트리를 형성한다. 자식은 부모 프로세스의 ① 주소 공간(binary & OS data)을 복사해 ② 그 공간에 새로운 프로그램을 올린다. ex) 유닉스에서는 fork() 시스템 콜이 주소 공간을 복사하고 exec() 시스템 콜이 새로운 프로그램을 메모리에 올린다. 생성된 프로세스는 자원을 운영체제로부터 받거나 부모 프로세스와 공유한다. (부모와 공유하지 않는 것이 일반적) 수행 : 부모와 자식이 공존하며 수행되는 모델 / 자식이 종료될 때까지 부모가 기다리는 모델 프로세스의 종료 프로세스는 마지막 명령을 수행한 후 exit이라는 시스템콜을 통해 운영체제에게 이를 알려준다. 프로세스 종료는 항상 자식이 먼저 종료되고 그것을 부모 프로세스가 정리하는 원칙이 있다. 그리고 wait 시스템콜을 사용해 자식 프로세스는 자신이 종료될 때 부모 프로세스에게 output data를 보내며 각종 자원들을 운영체제에 반납한다. 부모 프로세스가 자식의 수행을 abort 시스템콜로 강제 종료시키는 경우도 있다. 자식이 할당 자원의 한계치를 넘어설 때 (비유: 자식이 돈을 펑펑 쓸 때) 자식에게 할당된 태스크가 더 이상 필요하지 않을 때 (비유: 자식에게 시키던 일이 전부 끝나서 자식이 필요 없을 때) 부모가 종료될 때, 여러 개의 자식 프로세스들을 차례차례 단계적으로 죽이고 부모가 죽는다. 프로세스의 세계는 꽤 잔인하다! Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-05-26

3-2. 스레드

Thread (= lightweight process) (↔ heavyweight process, 전통적인 개념의 프로세스) 하나의 프로세스 내부에 CPU 수행 단위를 여러 개 두는 것을 말한다. 각각의 스레드는 CPU 수행과 관련된 정보만 제외하고 프로세스의 모든 것을 공유한다. 동일한 일을 수행하는 프로세스를 여러 개 띄워 놓고 싶다면, 하나의 주소 공간에 여러 개의 스레드를 사용하는 것이 효율적이다. 따라서, Program Counter를 여러 개 두고 register의 값들을 별도로 기억해두어 각각의 스레드가 스스로에게 필요한 code를 실행하게끔 한다. 함수 호출 및 return과 관련해서 stack도 스레드마다 따로 둔다. 스레드의 구성 1. Thread의 구성 program counter register set stack space 2. Thread가 동료 thread와 공유하는 부분 (=task) code section data section OS resources 3. Thread의 장점 Responsiveness(=빠른 응답성) 다중 스레드 태스크 구조에서는 하나의 서버 스레드가 blocked(waiting) 상태인 동안에도 동일한 태스크 내의 다른 스레드가 실행(running)되어 빠른 처리가 가능하다. ex) 웹페이지를 읽어오는 작업(I/O)이 오래걸리면 웹브라우저는 아무것도 못하는 blocked 상태가 된다. 반면에, 여러 개의 스레드로 웹브라우저를 만들면, 그림을 불러오는 작업이 오래 걸리더라도 다른 빠른 작업들을 먼저 화면에 보여줄 수 있다. (일종의 비동기식 입출력) Resource Sharing 메모리 자원을 효율적으로 사용할 수 있다. (자원 절약) Economy Thread를 Creating & CPU switching(문맥교환)하는 것은 process의 그것보다 훨씬 overhead가 작다. 동일한 일을 수행하는 다중 스레드가 협력하여 높은 처리율(throughput)과 성능 향상을 얻을 수 있다. Utilization of MP Architectures (CPU가 여러 개 달린 컴퓨터(Multi-Processor)에서만 해당) 병렬성을 높일 수 있다. ex) 행렬 곱셈 작업을 각 스레드가 다른 CPU에서 서로 다른 행과 열을 병렬로 계산 가능 4. Thread 구현 방법 Kernel Threads Kernel에 의해 지원된다. 스레드가 여러 개 있다는 사실을 운영체제가 알고 있어서 하나의 스레드가 다른 스레드에게 CPU를 넘기는 작업도 운영체제가 CPU 스케줄링하듯 진행한다. User Threads Library에 의해 지원된다. 프로세스 안에 여러 개의 스레드가 있다는 사실을 운영체제가 모르고 유저 프로그램 스스로 여러 개의 스레드를 관리한다. 따라서, 구현 상의 제약이 더 있을 수 있다. 몇몇의 real-time threads Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-05-18

3-1. 프로세스

프로세스(Process)의 개념 1. 프로세스 실행중인 프로그램을 의미한다. 2. 프로세스의 문맥(Context) 프로세스의 현재 진행 상태를 알려주는 것 time sharing, multitasking 등의 실현은 각 프로세스의 문맥을 정확히 기록해두어야 가능하다! 하드웨어 문맥 : CPU의 수행 상태를 나타냄 ex) Program Counter, 각종 register → CPU 관점에서 파악! 프로세스의 주소 공간 : 어떤 자료구조가 어떤 값을 가지고 있는지, 어떤 함수가 호출되고 return되는지 등을 파악함 ex) code, data, stack → 메모리 관점에서 파악! 프로세스 관련 커널 자료 구조 ex) PCB(Process Control Block), Kernel stack(프로세스마다 다른 커널 스택을 가지기에 개별로 상태 파악 가능) → 운영체제 관점에서 파악! (운영체제가 프로세스를 어떻게 평가하는지) 프로세스의 상태 (Process State) Running : CPU를 잡고 Instruction을 수행 중인 상태 Ready : 메모리에 올리는 것 등 다른 조건을 모두 만족하고 CPU를 기다리는 상태 Blocked (wait, sleep) : CPU를 주어도 당장 Instruction을 수행할 수 없는 상태 ex) 프로세스 자신이 요청한 event(ex. I/O)가 즉시 만족되지 않아 기다리는 상태, 프로세스 주소 공간 중 필요한 부분이 메모리에 아직 올라와 있지 않을 때 등 현대 컴퓨터에 중기 스케줄러의 등장으로 추가된 상태 Suspended (stopped) : 외부적 이유로 프로세스의 수행이 정지된 상태. 프로세스는 통째로 디스크에 swap out된다. ex) 메모리에 너무 많은 프로그램이 올라와 있을 때 (by 중기 스케줄러), 사용자가 프로그램을 일시 정지시킨 경우 Blocked : 자신이 요청한 event가 만족되면 Ready Suspended : 외부에서 resume해 주어야 Active 있을 수도 없을 수도 있는 상태 New : 프로세스가 생성 중인 상태 Terminated : 수행(Execution)이 끝난 상태 프로세스의 상태도 프로세스 상태도 - suspended 상태 추가 위의 프로세스 상태도는 운영체제의 입장에서 프로세스 상태를 명시한 것이다. 따라서, monitor mode에서도 운영체제가 running하고 있다고 말하지 않고, 사용자 프로세스가 Running 상태에 있다고 말한다. 또한, interrupt 혹은 system call을 진행 중일 때, 사용자 프로세스는 (커널모드 혹은 유저모드에서) Running 상태에 있다고 간주한다. Suspended 상태의 경우, 외부적인 이유로 메모리에서 벗어나 있는 상태로서 inactive하다고 말하고, Blocked에서 벗어났느냐 Ready에서 벗어났느냐에 따라 Suspended Blocked, Suspended Ready로 나뉜다. 또한, Suspended Blocked 상태에서 이전에 요청한 I/O 작업이나 event가 마무리되면 Suspended Blocked이 Suspended Ready로 바뀌기도 한다. 프로세스 진행과 queue 커널 주소 공간의 자료구조 Queue 위 상태도에서 나오는 하드웨어 및 CPU의 Queue들은 머릿 속에서는 모두 흩어져 있는 것으로 분류되지만, 사실은 모두 커널 주소 공간 중 Data 영역에서 queue 자료구조를 만들어 관리하는 것이다. PCB (Process Control Block) 운영체제가 각 프로세스를 관리하기 위해 프로세스당 유지하는 정보 PCB의 구조 PCB의 구성 요소 (구조체로 유지) OS가 관리상 사용하는 정보 ex) Process state, Process ID, scheduling information & priority CPU 수행 관련 하드웨어 값 (프로세스 문맥 정보) ex) Program Counter, registers 메모리 관련 (프로세스 문맥 정보) ex) code, data, stack의 위치 정보 파일 관련 (프로세스 문맥 정보) ex) open file descriptors 문맥 교환 (Context Switch) CPU를 한 프로세스에서 다른 프로세스로 넘겨주는 과정 문맥 교환 흐름 위 그림의 프로세스 A가 프로세스 B에게 CPU를 넘겨줄 때, 운영체제는 정확히 그 시점부터 프로세스 A가 다시 시작할 수 있게 프로세스 A의 PCB에 레지스터들의 저장된 값, Program Counter 값, 메모리 위치 정보 등을 저장한다. 새롭게 CPU를 얻게 되는 프로세스 역시 운영체제가 해당 프로그램의 PCB에서 상태를 읽어와 저장된 시점부터 다시 작업을 수행한다. 문맥 교환이 일어나는 경우와 아닌 경우 System call이나 Interrupt 발생 시 항상 문맥 교환이 일어나진 않는다. 보통은 위 그림의 (1)의 경우처럼 원래 작업 중이던 프로세스에게 다시 CPU 제어권을 넘겨 timer가 정한 시간에 도달할 때까지 작업을 수행하게 한다. 그러나 timer가 정한 시간이 다 되거나 I/O 요청으로 인해 프로세스가 blocked 상태가 되는 (2)의 경우에는 문맥 교환이 발생한다. 물론 (1)의 경우에도 커널 code를 실행하기 위해 CPU 수행 정보 등 약간의 context를 PCB에 저장해야 되지만 문맥 교환만큼 부담이 크지 않다. ex) Cache memory flush(캐시 메모리를 비우는 것)는 overhead가 큰데, 문맥 교환 시에는 이러한 캐시 메모리를 비워야 하는 반면, 단순한 커널모드와 유저모드 사이의 변환에서는 캐시 메모리를 비울 필요까지는 없다. 프로세스를 스케줄링하기 위한 큐 (Queue) Job queue : 현재 시스템 내에 있는 모든 프로세스의 집합 (Ready queue와 Device queue의 프로세스를 포함) Ready queue : 현재 메모리에 있으면서 CPU를 잡아 실행되기를 기다리는 프로세스의 집합 (혹은 줄) Device queue : I/O device의 처리를 기다리는 프로세스의 집합 (혹은 줄) 스케줄러 Long-term scheduler (장기 스케줄러 or job scheduler) 시작 프로세스 중 어떤 것에게 memory를 주고 ready queue로 보낼지 결정한다. degree of Multiprogramming(메모리에 올라가 있는 프로세스의 수)을 제어 메모리에 올라가 있는 프로그램 수가 너무 많아도 너무 적어도 안좋다. 그러나 현대의 대부분 컴퓨터의 time sharing system에서는 사용하지 않는다. (무조건 메모리에 프로세스를 올린다. = ready) Short-term scheduler (단기 스케줄러 or CPU scheduler) 어떤 프로세스에게 CPU를 주고 running 상태로 만들지 결정한다. 빠른 속도 (millisecond 단위) Medium-term scheduler (중기 스케줄러 or Swapper) 메모리 여유 공간을 마련하기 위해 메모리에 있는 프로세스를 통째로 디스크로 쫒아낸다. Long-term scheduler를 대신해 현대 컴퓨터의 degree of Multiprogramming을 제어 (프로그램은 실행 시 무조건 메모리에 올라가므로 어떤 것을 쫒아낼지가 이슈가 된다.) Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-05-04

2-2. 프로그램의 실행

Computer Science · 2021-05-02

2-1. 컴퓨터 시스템 구조

Computer Science · 2021-04-25

1. 운영체제 개요

운영체제(Operating System, OS)란? 하드웨어 바로 위에 설치되어 사용자 및 소프트웨어를 하드웨어와 연결시켜주는 시스템 소프트웨어이다. 협의의 운영체제 : 보통 커널을 지칭한다. 커널은 운영체제의 핵심 부분으로 메모리에 상주한다. 전공자 입장에서 주로 이 의미로 많이 쓰인다. 광의의 운영체제 : 컴퓨터 부팅 시, 커널 및 커널과 함께 실행되는 주변 시스템 유틸리티를 모두 총칭하는 개념이다. 운영체제의 목적 1. 컴퓨터 시스템 자원의 효율적 관리 효율성 : 주어진 하드웨어 자원(CPU, 기억장치, 입출력장치 등)을 활용하여 최대한 성능을 내도록 한다. ex) 실행 중인 프로그램들에게 짧은 시간 간격으로 CPU를 번갈아 할당하거나 메모리 공간을 적절히 분배하는 것 형평성 : 특정 사용자가 차별받지 않도록 사용자 간의 형평성을 고려하여 자원을 분배한다. 소프트웨어 자원(프로세스, 파일, 메시지)을 관리하거나 사용자 및 운영체제 스스로를 보호하기도 한다. 2. 사용자에게 편리한 컴퓨터 시스템 이용 환경 제공 실제로는 하나의 컴퓨터를 이용하는 여러 사용자들이 마치 자신만의 독자적 컴퓨터에서 프로그램을 실행시키는 듯한 느낌을 받게 한다. 또한, 하드웨어를 직접 다루는 복잡한 역할을 대신해준다. 운영체제의 분류 1. 동시 작업 가능 여부 단일 작업(single tasking) : 한 번에 하나의 작업만 처리한다. ex) MS-DOS 다중 작업(multi tasking) : 동시에 두 개 이상의 작업을 처리한다. ex) UNIX, MS Windows 2. 사용자 수 단일 사용자 ex) MS-DOS, MS Windows 다중 사용자 ex) UNIX, NT server 3. 처리 방식 시분할(time sharing) 여러 작업을 수행할 때, 컴퓨터 처리 능력을 일정한 시간 단위로 분할하여 사용하는 방식이다. 우리가 주로 사용하는 현대적 범용 컴퓨터는 대부분 이 방식을 사용한다. 일괄 처리 방식에 비해 짧은 응답시간을 가지지만 사용자의 수에 따라 처리시간이 달라진다. (0.01초의 처리시간이 사람이 많아질수록 0.1초, 1초와 같이 느려진다.) 이로 인해, Interactive한 속성(컴퓨터에 무언가를 입력하면 바로 화면에 결과가 나오는 방식)을 느낄 수 있으며, 실시간 방식과 달리 처리 시간의 제약이 따로 존재하진 않는다. 실시간(Realtime OS) 정해진 Deadline에 어떠한 작업이 무조건 마무리되어야 하는 실시간 시스템을 위해 만들어진 OS이다. 따라서, 한 치의 오차도 발생해서는 안 되는 공장 제어, 미사일 제어, 반도체 공정 등 특수 목적 시스템에 많이 사용된다. · Hard realtime system(경성 실시간 시스템) : 시간을 어기면 큰 문제가 생기는 시스템 ex) 공정 파이프라인 · Soft realtime system(연성 실시간 시스템) : 약간의 시간 어김이 허용되는 시스템 ex) 영화 스트리밍 영화 스트리밍, 웹서핑 등에 사용하는 보통의 범용 컴퓨터는 시분할 방식의 OS를 사용하지만 내비게이션 앱이나 블랙박스 영상 촬영 등은 잠깐의 시간 어김도 허용되서는 안 된다. 따라서, 범용 컴퓨터의 OS가 Realtime을 요구하는 Application들을 어떻게 지원해줘야 할 지에 대한 연구도 진행되고 있다. 일괄처리(batch processing) 과거의 컴퓨터 처리 방식 중 하나로 현대에는 익숙지 않은 방식이다. 작업 요청을 일정량 모아서 한꺼번에 처리하는 방식으로 interactive하지 않다. 다음 작업을 위해서는 작업이 완전히 종료될 때까지 기다려야 하는 불편함이 있다. 요즈음의 범용 컴퓨터 OS는 다중 작업, 다중 사용자, 시분할 처리 방식의 속성을 가진다. 다중 작업 관련 용어 정리 아래의 모든 용어는 ‘컴퓨터에서 여러 작업이 동시에 수행되는 것’을 의미한다. Multitasking Multiprogramming : 여러 프로그램이 메모리에 올라가 있음을 강조한다. Time sharing : CPU의 시간을 분할하여 사용하는 것을 강조한다. Multiprocess : process는 실행 중인 프로그램을 뜻하여, 여러 개의 실행 중인 프로그램을 말한다. Multiprocessor : 하나의 컴퓨터에 여러 CPU(processor)가 붙어 있음을 뜻한다. (하드웨어적으로 강조) 운영체제의 예 1. 유닉스(UNIX) 초기의 대형 컴퓨터(서버)를 위해 만들어진 운영체제로, multitasking과 다중 사용자가 가능하다. 복잡한 어셈블리어로 유닉스를 만든 것에 한계가 있어, 보다 high level에 해당하는 C언어가 탄생했다. 코드의 대부분이 C언어로 작성된 유닉스는 덕분에 기계어 집합이 전혀 다른 컴퓨터에도 이식하는 것이 쉬워져 높은 이식성을 보였다. (C언어 코드를 단순히 컴파일하면 되었다.) 유닉스는 최소한의 핵심적인 커널 구조만 가지며 메모리를 아꼈고, 복잡한 시스템에 맞게 확장이 용이했다. 또한, ‘공개 Software 정신’의 개념 하에 소스 코드를 공개하며 수많은 유닉스 기반의 OS들을 배출했다. System Ⅴ, FreeBSD(버클리 대학교 제작), SunOS, Solaris, Linux 등의 다양한 버전이 그 예이다. 특히, Linux는 개인용 컴퓨터를 비롯해 여러 환경에서 사용 가능한 특징을 보인다. 2. Microsoft 운영체제 단일 작업, 단일 사용자를 상정하며 시작되었다. DOS(Disk Operating System) : 단일 사용자용 운영체제이며, 640KB의 적은 메모리는 한계점이다. 이러한 한계가 있는 DOS에 새로운 기능이 계속 추가되며 DOS의 코드는 복잡해지고 누더기(?)가 되었다. 그 이후, DOS 위에서 Windows를 실행시키는 것이 가능해지고 점차 Windows가 독자적인 OS로 독립하였다. MS Windows : 제작된 다중 작업이 가능한 GUI 기반 운영체제이다. 하드웨어를 연결하면 별도의 사용자 조작이나 프로그램 설치 없이 바로 사용 가능한 Plug and Play 지원(그 당시엔 혁신적이었다.), DOS용 응용 프로그램과의 호환성, 풍부한 지원 소프트웨어 등의 특징이 있다. 3. 이외에도 애플 OS(Macintosh OS→Mac OS), 소형 디바이스(Handleheld device)를 위한 OS(PalmOS, Pocket PC(WinCE), Tiny OS) 등이 존재했고, 점차 iOS 같은 스마트 디바이스(Smart device)를 위한 OS 등 여러 형태의 운영체제로 발전하였다. 운영체제의 Issue 운영체제의 구조 CPU 스케줄링 : 빠른 처리 속도를 가진 CPU지만, 작업들을 어떤 순서로 할당하는 게 가장 효율적일지 고민한다. 메모리 관리 : 한정된 메모리를 어떤 작업들에 많게 혹은 적게 배분하고 제외시킬지에 관한 주제이다. 파일 관리 : 디스크에 파일을 어떻게 보관할지에 관한 주제이다. 디스크 헤드의 효율적인 움직임을 고민한다. 입출력 관리 : 다양한 입출력 장치와 컴퓨터 간의 정보 교환을 어떻게 할지 고민한다. 입출력 장치의 느린 처리속도를 극복하기 위해 빠른 처리 속도를 가진 CPU를 순간적으로 멈추는 Interrupt도 이 주제에서 다룬다. 프로세스 관리 : 컴퓨터 소프트웨어(프로그램)들을 어떻게 관리할지에 대한 주제이다. 보호 시스템, 네트워킹, 명령어해석기(Command Line Interpreter) 등의 주제도 존재한다. 내 스스로가 운영체제가 되었다고 생각하며 공부해보자 :) Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-04-24

Lucian Log

Contact

OS