알고리즘 고수가 되기까지

설명 순서는 다음과 같습니다.

1. Cache가 등장한 배경
2. Cache란
3. Cache에 담는 데이터 선택하기

1. Cache가 등장한 배경

   - 기술의 발전으로 CPU 속도는 빠르게 증가하는 반면, 메모리는 그렇지 않음

   - CPU가 아무리 빨라도 메모리 처리 속도가 느리다면, 전체 속도는 느려지게 되어있음

   - 이를 개선하기 위한 장치가 Cache임

2. Cache란

   - Cache란 빠른 CPU와 느린 메인 메모리 사이 병목현상을 줄이기 위한 빠르고 작은 메모리

   - 메인 메모리를 빠른 캐시처럼 만들면되지 않을까? 용량이 크고 빠른 메모리를 사용하기에는 비용이 너무 많이 듬(가성비 X)

   - 결국 메모리의 '특정 데이터'만을 캐시에 올려서 빠르게 사용하도록 해야함. 어떤 부분을 캐시에 올려야할까

   - 우리는 메인 메모리에 접근하는 시간을 줄여야함. 최대한 CPU가 캐시에서만 사용할 수 있도록 해야함

   - 따라서, 자주 사용하는 데이터를 캐시에 올려야함

3. Cache에 어떤 데이터를 담을까

   - 어떤 데이터가 자주 사용될까 -> 자주 사용되는 데이터는 시간적 또는 공간적으로 몰려있을 가능성이 높다는 법칙을 이용함

      ① 시간적 지역성 : 최근 사용한 데이터를 다시 사용할 확률이 높다(ex. for문의 i)

      ② 공간적 지역성 : 최근 사용한 데이터의 주변 데이터를 사용할 확률이 높다(ex. 배열)

   - 따라서, 최근 사용한 데이터와 그 주변 데이터를 캐시에 올려놓을 필요가 있음

   - 또한, 캐시에 없는 데이터를 메모리에서 찾아서 올릴 때 '가장 최근에 사용된 적이 없는 것'과 교체함

   - 이 알고리즘 또한 시간적 지역성을 이용한 사례라고 생각합니다

캐시 메모리에 대해 알아볼 수 있었습니다

순서는 다음과 같습니다

1. CPU 스케줄링이 필요한 이유
2. CPU 스케줄링의 성능 평가 기준
3. CPU 스케줄링의 종류

1. CPU 스케줄링이 필요한 이유

   - 프로세스는 동작하려면 CPU가 필요함

   - 많은 프로세스들이 CPU를 요구할 때, CPU는 그 중 어떤 프로세스를 실행해야할지 선택해야함

   - CPU에 어떤 프로세스를 할당할 지 결정하는 것을 CPU 스케줄링이라고 

2. CPU 스케줄링의 성능 평가 기준

   - 여러 CPU 스케줄링 알고리즘이 등장할 수 있음(ex. 먼저 요청한 프로세스를 먼저, 적게 걸리는 것 먼저 등등)

   - 그 중 어떤 스케줄링이 가장 적합한지 고르려면 기준이 있어야 함. 이것이 CPU 스케줄링 성능 평가 기준임

   - 성능평가 기준

      ① CPU 이용률 : 시간당 CPU를 사용한 시간의 비율. CPU가 쉬지않고 계속 일을 해야(프로세스를 돌려야) 좋은 알고리즘임. 그러므로, 입출력 작업보다 프로세서 중심의 작업을 해야함.

      ② 처리율 : 시간당 처리한 작업의 비율. 많은 일을 끝내야 좋은 알고리즘임. 그러므로, 작업소요시간이 짧은 것을 먼저 처리하도록 해야함.

      ③ 소요시간 : 한 프로세스가 처리된 총 시간. 이 시간이 짧을수록 좋은 알고리즘임

      ④ 대기시간 : CPU를 할당받기까지 기다린 시간. 이 시간이 짧을수록 좋은 알고리즘임

      ⑤ 응답시간 : 처음 CPU를 할당받기까지 기다린 시간. 이 시간이 짧을수록 좋은 알고리즘임

3. CPU 스케줄링의 종류

   - 크게 두가지로 나눌 수 있음(선점형, 비선점형)

      ① 선점형

         : 프로세스가 CPU를 사용하고 있더라도, 운영체제가 강제로 CPU를 빼앗아 다른 프로세스에게 할당할 수 있는 방식.

      ② 비선점형

         : 프로세스가 종료되거나 스스로 대기상태에 접어들기 전까지 다른 프로세스가 CPU를 사용할 수 없는 방식.

   - 선점형 특징 : 더 급하게 처리해야할 일이 들어왔을 경우 먼저 처리할 수 있음. 그렇지만, Context-Switching이 발생하므로 오버헤드가 발생할 수 있음

   - 비선점형 특징 : Context-Switching 오버헤드는 적지만, 더 급한일을 처리할 수 없음

   - 대표적인 스케줄링 알고리즘

      ① FCFS(First Come First Served)

         * 먼저 온 프로세스가 먼저 CPU를 할당받아서 하나씩 처리하는 방식, 비선점형

         * 긴 시간이 필요한 프로세스가 끝날때까지 다른 프로세스는 모두 기다려야하므로 비효율

      ② SJF(Shortest Job First)

         * 짧은 시간이 필요한 프로세스를 먼저 처리하는 방법

         * 프로세스가 얼마나 시간을 필요로할지 애초에 알지 못함. 긴 시간이 필요한 프로세스는 기아현상 발생

      ③ Priority Scheduling

         * 높은 우선순위를 가진 프로세스를 먼저 처리하는 방법

         * 선점형 방식에서는 도착한 프로세스의 우선순위가 현재 실행되는 것보다 높으면 CPU를 할당받음

         * 비선점형 방식에서는 준비큐에 우선순위에 따라 삽입

         * 우선순위가 낮은 프로세스일 경우 기아현상 발생함

         * 이러한 기아현상은 결국 우선순위가 높은 프로세스가 계속 실행되므로 발생하는 것임. 그러므로, 우선순위가 높은 것을 낮춰야하고, 낮은것을 높이는 방식으로 해결해야 함.

         * 대표적인 방법으로는 aging이 있는데, 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방법임. 이렇게 하면 기아현상을 줄일 수 있음

      ④ Round Robin

         * 동일한 시간동안 계속 돌아가면서 CPU를 할당받는 방식, 선점형

         * 만약 이 시간이 커지면 결국 FCFS와 같아지므로 비효율적이고, 너무 짧을 경우 Context-Switching이 자주 발생해 오버헤드가 증가함

      ⑤ 다단계 피드백 큐 스케줄링

         * 가장 일반적인 CPU 스케줄링 알고리즘

         * 우선순위에 단계별로 큐가 여러개 있고, Round Robin으로 돌아감

         * 이후 실행된 프로세스의 우선순위를 하나씩 낮춤(aging)

         * 우선순위에 따라 긴급한 처리가 가능, 기아 현상 줄임, Round Robin으로 응답시간을 줄임

CPU 스케줄링에 대해 알아볼 수 있었습니다