이전 글에서 Virtual memory를 효율적으로 다룰 수 있는 방법 중 하나인 Paging에 대해서 알아보았고,Paging은 process마다 page table을 요구하기 때문에 큰 메모리를 차지한다는 것을 알 수 있었다. "page table을 저장하기 위해 physical memory의 큰 부분을 차지한다"이 말은 paging은 virtual address를 translate 할때마다 큰 메모리 look up 이 필요하다는 말과 같다.어떻게 Address Translation을 빠르게 할 수 있을까?이를 해결하기 위해서는 하드웨어와 OS(소프트웨어)의 지원이 필요하다.하드웨어는 MMU(memory-management unit)에 TLB(translation-lookaside buffer)을 제공..

이전 글들에서 OS가 메모리를 관리하기 위한 방법 중 하나인 Segementation에 대해 알아봤다.하지만 Segementation은 다양한 크기의 chunk로 나누어지기 때문에 Segmentation와 free space를 관리하는데 있어서 어려움이 있었다. OS가 메모리를 관리하기 위한 첫번째 방법이 Segementation이었고 두번째 방법도 존재한다.바로 Paging이라 불리는것이다. OS는 variable size로 메모리를 나누는 것이 아닌 fixed-size로 메모리를 나누고, 이것을 page라고 부른다. physical memory를 page frames이라고 불리는 고정된 크기의 slot 배열이라고 생각하는 것이다.  그럼 Paging은 정확히 어떤 장점이 있을까?첫번째로, flexib..

이번 챕터는 메모리 관리 측면에 대해 살펴 볼것이다. 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이란? 프로세스가 사용해야하는 자원의 몫을 나타낸다. 즉 티켓의 비율은 시스템 ..

Hash란? 임의의 데이터를 해시 함수를 통해 고정된 크기의 고유한 값으로 매핑하는 것을 말한다. 해시 함수는 주어진 입력에 대해 항상 동일한 출력을 생성하고, 최대한 서로 다른 입력에 다른 출력을 만들어 충돌을 최소화 한다. Hash Map이란? 해시 맵이란 해시를 사용해서 데이터를 저장하는 자료 구조 이다. 각 키에 해당하는 해시 값을 계산하여 해당 위치에 데이터를 저장한다. 따라서 해시 맵은 평균적으로 검색, 삽입 삭제 연산의 시간 복잡도가 O(1)이다.

1. 선택 정렬 (Selection Sort) 선택 정렬은 가장 간단 하면서 비효율적인 정렬 알고리즘이다. 1. 배열에서 최소값(또는 최대값)을 찾는다. 2. 최소값(또는 최대값)을 배열의 맨 앞의 원소와 교환한다. 3. 정렬된 부분의 배열을 제외하고 나머지 배열에서 위 과정을 반복한다. 자바로 구현하기 import java.util.Scanner; public class SelectionSort { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int num = Integer.parseInt(scanner.nextLine()); int[] arr = new int[num]; for (int i = 0;..