23년 12월 15일(금요일) - 53번째 TIL

 

 

참조 지역성이란 기억장치로부터 참조될 때 시간적, 공간적, 순차적으로 분포가 집중되는 성질을 말한다.  

 

크게 시간 지역성과 공간 지역성으로 나눌 수 있다. (순차 지역성은 보통 공간 지역성에 편입하여 설명된다.)

클릭 시 원본 이동 (https://itwiki.kr/w/%EC%B0%B8%EC%A1%B0_%EC%A7%80%EC%97%AD%EC%84%B1)

 

x축은 시간, y축은 연속된 메모리 주소이다.

 

시간 지역성은 최근에 참조된 주소는 다시 참조될 확률이 높은 성질이다. 

시간 지역성의 예시로, CPU 스케쥴링을 들 수 있다. CPU에서 처리할 프로세스를 설정할 때, 최근에 사용된 프로세스는 다시 사용될 가능성이 높다고 판단하여 우선순위를 높여서 처리되게끔 한다. 

 

CPU 스케쥴링 방식에는 크게 선점과 비선점 방식이 있다. 

비선정 방식은 프로세스가 들어오는 순차적으로 처리하는 방식이다. 구현은 단순하지만, 프로세스의 중요도와 걸리는 시간을 고려하지 않아 긴급한 처리를 바로 처리가 불가능하고 또 너무 오래 걸리는 프로세스를 처리하는 동안에는 이후에 진행될 프로세스는 계속 대기를 해야하는 현상이 있고, 무한 루프가 있다면 더 이상 처리가 되지 않는 문제가 있다. 

 

선점 방식은 프로세스의 중요도를 정하여 우선순위에 따라 프로세스를 처리하는 방식이다. 이러한 방식으로는 긴급한 프로세스는 바로 처리 가능하지만, 우선 순위가 높은 프로세스들이 들어온다면 낮은 중요도의 프로세스의 경우 처리가 되지 않거나 늦어지는 기아 현상이 발생하기도 한다. 

 

현대의 CPU 스케쥴링 방식은 선점 방식이되 하나의 프로세스를 처리하는데 쓰는 시간을 제한을 둠으로써 기아현상을 해결한다. 

 

공간 지역성은 최근에 참조된 주소의 주변 주소도 접근할 확률이 높은 성질이다. 

배열의 원소나 객체의 필드를 순차적으로 접근하는 경우가 이에 해당한다.

순차 지역성은 for (int i = 0; i < 100; i++) 에서 변수 i 에 해당한다고 볼 수 있다.

 

이러한 공간 지역성의 원리를 적용한 사례 중 하나로 Tim 정렬이 있다. 팀 정렬의 경우 병합 정렬에 삽입 정렬을 적용한 정렬이다. 

우선 병합 정렬로 분할하는 과정을 거치다가, 특정 요소 수 이하가 되면 삽입 정렬을 하는 정렬이다. 

 

삽입 정렬은 배열 내에서만 요소의 위치를 바꾸므로 다시 참조될 가능성이 높지만, 병합 정렬의 경우 분할 이후 정복하는 과정에서 새로운 배열을 만드므로 다시 참조될 가능성이 낮다. 이러한 지역성 때문에 특정 요소 수 이하에서는 삽입 정렬의 최악의 시간 복잡도인 O(N^2) 를 극복할 수준이 된다. 

따라서 팀 정렬의 시간 복잡도는 최선은 O(N), 평균은 O(NlogN), 최악은 O(NlogN)이 된다.