인프런 워밍업 클럽 - CS Day 12
AlgorithmMerge Sort재귀로 구현하는 정렬 알고리즘Divide and Conquer복잡한 문제를 더 작고 관리하기 쉬운 하위 문제들로 나누어 해결하는 알고리즘 설계 기법구현 방법분할(Divide): 정렬할 배열을 거의 같은 크기의 두 부분 배열로 나눈다.정복(Conquer): 각 부분 배열을 재귀적으로 정렬한다.결합(Combine): 정렬된 부분 배열들을 하나의 정렬된 배열로 병합한다.1 ~ 3을 부분 배열의 크기가 1이 될 때까지 반복한다.시간 복잡도분할 과정: 배열을 반으로 나누는 과정이 log n번 일어납니다.병합 과정: 각 단계에서 n개의 요소를 비교하고 병합합니다.→ 전체 시간 복잡도 : O(n) * O(log n) = O(n log n)장점속도가 빠르다.시간 복잡도 : O(n log n)단점병합 과정에서 임시 배열이 필요하여 추가적인 메모리 공간을 사용한다.이해와 구현이 복잡하다.OS지역성 이론(90 : 10 법칙)프로그램이 실행될 때 90%의 시간이 10%의 코드에서 소요된다.조만간 쓸 데이터만 메모리로 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑영역으로 보내 성능을 향상시킨다.디맨드 페이징필요할 것 같은 데이터를 메모리로 가져오고, 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동시키는 정책지역성 이론을 구현한 정책메모리에서 데이터를 가져오는 정책Swap in스왑 영역에서 물리 메모리로 데이터를 가져오는 과정Swap out물리 메모리에서 스왑 영역으로 데이터를 보내는 과정Page Table Entry(PTE)페이지 테이블을 이루고 있는 행접근 비트페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트메모리에 읽기나 실행 작업을 했다면 1로 변경된다.변경 비트페이지가 메모리에 올라온 후 데이터에 변경이 있었는지 알려주는 비트메모리에 쓰기 작업을 했다면 1로 변경된다.유효 비트페이지가 물리 메모리에 있는지 알려주는 비트유효비트 1 : 페이지가 스왑영역에 있음유효비트 0 : 페이지가 물리 메모리에 있음읽기/쓰기/실행 비트(권한 비트)해당 메모리에 접근권한이 있는지 검사하는 비트Page Fault프로세스가 가상 메모리에 접근요청을 했을 때 MMU(메모리 관리자)는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아낸다.물리 메모리에 프레임이 없다면 MMU는 Page Fault라는 인터럽트를 발생시킨다.Page Fault가 발생하면 스왑영역에 접근하고 해당 프로세스는 대기 상태가 된다.→ 스왑 영역의 데이터가 메모리로 올라가는 작업을 수행한다.→ 데이터가 물리 메모리로 올라가는 경우 해당 프로세스가 실행 상태로 변경된다.공간의 지역성현재 위치와 가까운 데이터에 접근할 확률이 높다.시간의 지역성최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높다.페이지 교체 정책메모리가 꽉찼을 때 어떤 페이지를 스왑영역으로 보낼지 결정하는 정책무작위로 교체하는 방법지역성을 고려하지 않는다.자주 사용되는 페이지가 선택될 수 있어 성능이 좋지 않다.→ 거의 사용되지 않는다.FIFO(First-In First-Out)메모리에 들어온지 가장 오래된 페이지를 교체한다.→ 자주 사용하는 페이지가 교체될 수 있다.구현이 간단하고 성능이 나쁘지 않아 변형해서 사용된다.H/W 적으로 접근비트를 지원하지 않는다면 FIFO를 사용해야 한다.Belady's AnomalyPage Fault를 줄이려고 메모리를 더 늘려서 프레임의 수를 늘렸는데 오히려 Page Fault가 더 많이 발생하는 현상FIFO에서만 발생한다.2차 기회 페이지 교체 알고리즘FIFO 방식에서 자주 사용하는 페이지에게는 또 한번의 기회를 준다.FIFO와 동일하게 동작하지만 Page Fault 없이 페이지 접근에 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시켜 준다.Optimum앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다.→ 이후에 어떤 요청이 들어올지 알고 있어야 한다.→ 사실상 구현이 불가능한 이론적인 방법다른 알고리즘과 성능 비교를 할 때 참고용으로 사용된다.LRU(Least Recently Used)시간의 지역성에 따르면 최근 사용한 데이터가 앞으로도 사용될 확률이 높기 때문에 최근에 가장 사용을 적게한 페이지가 앞으로도 사용될 확률이 적다.Optimum 알고리즘에 근접한 성능을 갖는다.프로그램이 지역성을 띄지 않을 때는 성능이 떨어진다.PTE에 시간을 기록하려면 비트가 많이 필요하다.→ 비트를 많이 사용하는 것은 어렵기 때문에 접근비트를 이용하여 LRU에 근접하게 구현한다.Clock Algorithm접근 비트 하나만을 사용하여 구현하는 알고리즘일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화한다.페이지가 참조되는 경우 1로 설정된다.⇒ 일정 시간 간격마다 페이지가 참조되었는지 참조되지 않았는지 알 수 있다.페이지를 원형으로 연결한다.Page Fault가 발생해서 스왑영역으로 보내야 하는 경우클락 핸드는 현재 참조하고 있는 접근 비트를 본다.해당 비트가 1인 경우 해당 비트를 0으로 변경하고 다음 비트를 바라본다.접근 비트가 0인 페이지를 발견하면 해당 페이지를 스왑 영역으로 보낸다.Clock Hand스왑영역으로 옮길 페이지를 가르키는 포인터시계 방향으로 돈다.Enhanced Clock Algorithm접근 비트만 이용하는 것이 아니라 변경 비트도 함께 사용하는 알고리즘스왑 영역으로 보내지는 가장 우선순위접근 비트 : 0, 변경 비트 : 0접근 비트 : 0, 변경 비트 : 1접근 비트 : 1, 변경 비트 : 0접근 비트 : 1, 변경 비트 : 1스레싱 프로세스들이 실제 실행되는 시간보다 페이지를 교체하는 데에 더 많은 시간을 사용하고 있는 현상⇒ 페이지 부재(page fault)가 과도하게 발생하여 CPU 이용률이 급격히 떨어지는 현상다중 프로그래밍의 정도가 높아져 각 프로세스에 할당된 메모리가 부족해지면서 발생CPU 이용률 저하 → 운영체제의 다중 프로그래밍 증가 → 페이지 부재 증가의 악순환이 반복근본적인 원인 : 물리 메모리의 크기가 부족한 것→ 메모리의 크기를 늘려서 해결(H/W 수준)할 수 있다.S/W 수준의 해결 방법프로세스가 실행되면 일정량의 페이지를 할당한다.→ Page Fault가 빈번하게 발생하는 경우 : 더 많은 용량의 페이지를 할당한다.→ Page Fault가 거의 없는 경우 : 적은 용량의 페이지를 할당한다.워킹셋프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합프로그램의 지역성(Locality) 특성을 이용한 개념자주 참조되는 워킹셋을 주기억장치에 유지함으로써 페이지 부재와 교체를 줄인다.시간에 따라 자주 참조하는 페이지들의 집합이 변화하므로 워킹셋도 동적으로 변한다.컨텍스트 스위칭에서 사용된다.
