이번 챕터는 메모리 관리 측면에 대해 살펴 볼것이다. frees space가 고정된 크기로 나뉘어 있으면 공관관리가 편할 것이다. 하지만 OS가 segementation으로 virtual memory를 관리하고, 사용자 레벨의 메모리 할당 라이브러리 (malloc, free등)로 인해 free space는 다양한 크기를 갖게 된다.이와 같이 free space가 서로 다른 크기의 조각으로 분리되는 것을 external fragmentation이라고 한다.만약 15k의 메모리를 요청할 때, 총 free space의 공간은 20k로 충분하더라도, 하나의 연속된 메모리 공간이 없기 때문에 실패할 것이다.그리고 free list는 위와 같이 표현될 수 있을것이다.반대로 10K보다 작은 메모리를 1K 메모리를 요..
이전 글에서 base, bounds 레지스터를 통해 OS는 physical memory의 다른 파트들을 프로세스에 relocate할 수 있었다. 하지만 큰 문제가 남아 있다.할당된 Address space에서 Heap과 Stack 사이의 사용하지 않는 메모리가 보이는가?이는 매우매우 낭비적이고, physical memory를 효율 있게 사용할 수 없게된다. 이 문제를 해결하기 위한 Segmentation 이라는 기술이 있다.해결법은 단순하다! MMU에 base레지스터와 bounds레지스터를 갖고 있는 대신에 address space의 segment마다 base레지스터, bounds레지스터 쌍을 갖고 있는건 어떨까? 한 segment는 특정 길이의 address space의 연속된 부분이다. 이 segme..
CPU와 마찬가지로 메모리를 가상화하는 이유는 각 프로그램이 private 메모리를 갖고 있게끔 착각을 주기 위해서이다.메모리 가상화는 어떤 방식으로 이루어지고, 또 어떤 기술이 필요할까? 이제부터 알아보도록 하자. 예시를 들기 전에, 말도 안되지만 몇가지 가정을 둘것이다.1. address space는 physical memory에 연속적으로 존재한다.2. address space의 크기는 physical memory보다 작다.3. 각 address space의 크기는 동일하다.위의 코드를 시킨다면 컴파일러는 아래와 같이 어셈블리어로 전환 할 것이다.코드는 매우 단순하다. 변수 x는 레지스터 ebx에 존재하고, ebx의 값을 레지스터 eax로 load한다.eax에 3을 더한 후, 결과 값을 ebx로 다..
요즘날의 OS는 멀티 프로세스들을 CPU를 time sharing하며 실행한다. 하지만 context switch를 할 때마다 실행했던 프로세스의 메모리, 상태(PC, registers 등)들을 disk에 저장하고, 이후에 다시 실행할 때 다시 disk에서 메모리로 load하는것는 상당히 비효율적이다(특히 프로그램의 메모리가 클수록 오래걸릴것이다). 따라서 아래 13.2와 같이 프로세스의 메모리를 계속 남겨두는것이 효율적일것이다. The Address Space OS는 프로세스에게 이런 메모리 구조를 추상화하여 제공한다. 각 프로세스의 address space는 프로세스의 모든 메모리 정보를 저장한다. 프로그램이 실행할때 생성되는 local variable, pass parameter, return va..
이번 챕터에서는 멀티프로세서 스케줄링에 대해 알아볼 것이다. 예전이야 cpu가 하나만 있었지만 현재 multiprocessor은 데스크탑, 랩탑, 모바일 등 매우 흔한것이 되었다. mulicore processor의 대중화는 좋은 현상이지만 이로 인해 몇가지 문제가 발생했다. 그중 하나는 과거에 개발된 전형적인 애플리케이션들은 하나의 cpu만 사용하기 때문에 cpu가 추가되었다고 해서 빨라지지 않는다는 것이다. 따라서 우리가 코드를 병렬적으로 rewrite할 필요가 있다. 다른 문제점으로는 OS가 multiprocessor scheduling을 해야한다는 점이다. 이런 문제점들을 이해하기 위해서는 우선 Multiprocessor의 아키텍처에 대해 이해해야될 것이다. Background : Multipro..
이 챕터에서는 fair-share 스케줄러라고도 부르는 proportional-share 스케줄러에 대해서 알아 볼거다. 이전의 Multiple-level Feed-back Queue(MLFQ)에서는 Completion time과 Response time의 최적화에 중점을 뒀다면, Proportion-share 스케줄러는 각 job들이 특정한 비율의 cpu 시간을 보장받을 수 있도록 하는 스케줄러이다. lottery scheduling이 proportion-share스케줄러로 잘 알려져 있다. Ticket : Represent Your Share lottery scheduling에는 ticket이라는 개념이 있다. ticket이란? 프로세스가 사용해야하는 자원의 몫을 나타낸다. 즉 티켓의 비율은 시스템 ..
Multi-level Feed-back Queue (MLFQ)는 두가지 문제를 개선하려 한다. 1. turnaround time 최적화 SJF또는 STCF가 프로세스의 실행시간과 같은 지식을 필요로 했던 것과 달리, 이러한 지식이 없는 상태에서 최적화를 해야한다. 2. response time 최소화 interactive유저들에게 반응적이어야한다. round robin은 response time을 줄였지만 turnaround time에서는 좋지 않았다. 즉, job의 길이에 대한 사전지식 없이 response time을 최소화 하는 동시에 turnaround time 또한 줄일 수 있는 스케줄러를 설계해야한다. MLFQ : Basic Rules OS마다 MLFQ에 대한 구현은 다 다르지만 알고리즘은 비슷..
이전에 process를 virtualization하기 위해서는 low-level machinery mechanism과 high-level intelligence가 필요하다 했고, 앞선 글에서 context switch등 low-level mechanism들에 대해서 알아보았다. 이제는 OS Scheduler를 위한 scheduling policies 혹은 disciplines를 알아보자. 우리는 scheduling policies를 점차적으로 개선해나가며 공부할 것이다. 하지만 스케줄링 정책을 만드는 것에 있어서 workload는 굉장히 중요한 부분이고 원활한 예시를 위해 몇가지 가정을 둘것이다. (물론 실제로 이 가정은 매우매우 비현실적이지만 공부를 위한것이다..) Workload Assumptions..
앞서, CPU를 virtualize하기 위해서는 OS가 동시에 동작하는 것처럼 보이는 프로그램들에게 물리적인 CPU를 공유해야한다고 설명했다. 기본 아이디어는 한 프로세스를 잠시 실행했다, 다른 프로세스를 실행하고, 또 다른 프로세스를 돌아가며 실행하는 것이다. 이걸 CPU의 time sharing이라고 한다. 하지만 time sharing에는 몇가지 문제들이 있다. 1. Performance 과도한 오버헤드 없이 좋은 성능을 유지하며 time sharing을 할 수 있을 것인가. 2. Control 어떻게 cpu를 컨트롤하며 효율적으로 프로세스들을 실행할 수 있을 것인가. Basic Technique : Limited Direct Execution 프로그램을 빠르게 실행하기 위해서 OS는 limited..
앞서 2번글에서 OS가 프로세스를 위한 인터페이스를 제공한다고 했다. 이번 글에서는 OS가 process API를 어떻게 제공하는지 실제로 코드를 알아보자. 코딩은 UNIX가 제공하는 시스템으로 진행 할 것이다. The fork() System Call fork()는 새로운 process를 생성하는 시스템 콜이다. fork() 시스템 콜을 호출하면 새로운 프로세스를 생성하고, fork()를 호출한 프로세스를 부모 프로세스, 새로 생성된 프로세스를 자식 프로세스라고 한다. 프로세스는 각 프로세스를 식별하기 위해 id를 가지고 있는데, 이를 PID라고 한다. fork()를 통해 프로세스 생성에 성공 했을 때 새로 생성된 자식 프로세스에는 0을 반환하고, 부모 프로세스에는 자식 프로세스의 pid를 반환한다. ..