🖥 Computer Science

97점짜리 코드입니다.. 100점 도전은 해보았는데, 정상적으로는 안되더라구요.. 혹시 누군가 정상적으로 100점을 받았다면.. 슬쩍 알려주시면 감사하겠습니다.. 화이팅하세요 :)

🧐 프로세스 우선 프로세스에 대해 알아보기 전에, 프로세스와 같이 알아두어야 할 용어가 있습니다. 바로 프로그램과 Task입니다. 📕 프로그램 일반적으로 하드 디스크에 저장되어 있는 실행코드를 뜻하는데, 예를 들어 카카오톡, 워드, 한글 등이 각각 하나의 프로그램입니다. 카카오톡을 예시로 계속 설명하자면, 카카오톡을 컴퓨터에 설치하기만 해서는 사용할 수 없습니다. 카카오톡 프로그램을 실행하여야 사용할 수 있는데, 실행하는 경우 카카오톡 프로그램에 대한 인스턴스가 생성됩니다. 이것이 바로 프로세스입니다. 프로세스는 OS가 만들어 주는 실행 프로그램의 인스턴스입니다. 컴퓨터는 User, Kernel, HW 영역으로 나뉘어집니다. 카카오톡, 워드 등의 프로그램은 User 영역에서 실행되며, Kernel 영역에..

🧐 가상 메모리 메인 메모리를 2차 저장장치(디스크)의 캐시로 사용하는 기술을 의미합니다. 이전까지는 캐시가 어떻게 최근에 사용한 코드와 데이터 부분에 대한 빠른 접근을 제공하는지 알아보았습니다. 같은 방법으로, 메인 메모리가 보통 자기 디스크로 구현되는 2차 저장장치를 위한 캐시로 동작할 수 있습니다. 이러한 기술을 가상 메모리(Virtual Memory)라고 부릅니다. 가상 메모리를 사용하게 된 주요 동기는 두가지입니다. 1. 여러 프로그램들이 효과적이고 안전하게 메인 메모리를 공유할 수 있게 하기 위하여 2. 작고 제한된 크기의 메인 메모리에서 프로그래밍해야 하는 제약을 제거하기 위해서 이 기법이 탄생한 지 수십년이 지난 지금은 첫 번째 이유로 널리 사용되고 있습니다. 다수의 프로그램이 같은 메모리..

이전 글에서 살펴본 associative cache는 miss rate를 줄이는 방식으로 성능을 개선하였습니다. 이번에 살펴볼 Multilevel cache는 miss penalty를 감소시켜 성능을 높이는 방법입니다. 🧐 Multilevel Cache 현대의 모든 컴퓨터는 캐시를 사용합니다. 프로세서의 빠른 속도와 상대적으로 점점 느려지는 DRAM의 접근시간의 차이를 더욱 줄이기 위해서, 대부분의 마이크로프로세서는 캐시를 한 계층 더 지원합니다. L1 cache(1차 캐시, primary cache) : 프로세서와 가장 가까운 캐시. 속도를 위해 I cache와 D cache로 나뉩니다. - Instruction Cache (I cache) : 메모리의 TEXT 영역 데이터를 다루는 캐시입니다. - D..

🧐 Associative Cache Associatvie Cache는 유연한 블록 배치(placement)를 통해 캐시 실패율(Miss rate)을 줄이는 방법입니다. 이전 글 까지에서는 메모리 블록을 캐시에 넣을 때 각 블록이 캐시의 딱 한 장소에만 들어갈 수 있도록 하는 단순한 배치 방법인 directed mapped를 사용하였습니다. directed mapped는 블록을 배치하는 다양한 방식들 중, 극단적으로 블록을 한 곳에만 넣을 수 있도록 하는 방법입니다. 반대쪽 극단에는 블록이 캐시의 어느 곳에나 들어갈 수 있도록 하는 방식이 있습니다. 👉 fully associative 블록이 캐시의 어느 곳에나 들어갈 수 있도록 하는 캐시 구조를 의미합니다. 메모리 블록을 캐시 내의 어떤 엔트리와도 연관(..

🧐 캐시 성능 측정 해당 글에서 CPU 시간(time)에 대해 잠깐 살펴보았듯이, CPU 시간은 클럭 사이클의 수와 클럭 사이클 시간의 곱으로 표현할 수 있었습니다. 이때 클럭 사이클의 수는 다시 CPU가 프로그램을 수행하는 데 쓴 클럭 사이클과, 메모리 시스템을 기다리는 데 사용한 클럭 사이클로 나누어볼 수 있습니다. 일반적으로 적중 시간(hit time)은 CPU 클럭 사이클의 일부로 간주합니다. CPU Time = (CPU 클럭 사이클(hit time 포함) + 메모리 지연 클럭 사이클) X 클럭 사이클 시간(Clock Cycle Time) 메모리 지연 클럭 사이클은 주로 캐시 실패 때문에 발생하며, 읽기와 쓰기 시에 발생되는 지연 사이클의 합으로 정의할 수 있습니다. 메모리 지연 클럭 사이클 = ..

🧐 NP-Hard(NP 난해) Problem X가 다음 조건을 만족하면 이를 NP-Hard라 부릅니다. 어떠한 Y $\in$ NP 에 대해서도, Y $\leq_p$ X 가 성립니다. 즉 NP에 속한 어떠한 문제에 대해서도 X로의 Polynomial Time Reduction이 존재해야 합니다. Halting Problem(정지 문제)은 NP-Hard에 속하는 대표적인 문제입니다. 🧐 NP-Complete(NP 완전) Problem X가 다음 조건을 만족하면 이를 NP-Complete라고 부릅니다. 1) 어떠한 Y $\in$ NP 에 대해서도, Y $\leq_p$ X 가 성립니다. 2) X $\in$ NP 여야 합니다. 즉 NP-Complete는 NP-Hard이면서 NP인 문제들을 의미합니다. Haltin..

🧐 Problem 이전 글에서 살펴보았던 problem에 관련한 개념들을 다시 살펴보도록 하겠습니다. Problem Instance : 어떤 문제(problem)를 정의하는 input이며, 이때 해당 input을 일종의 binary string으로 생각할 수 있습니다. Problem : 어떤 조건을 만족시키는(YES라 답하는) problem instance들의 집합을 의미합니다. 이때 Problem에 속하는 instance들을 YES instance라 합니다. Algorithm : 어떤 problem X에 대하여, 어떤 mapping 함수 A가 임의의 s $\in $ X에 대하여 A(s) = YES이고, 역( A(s) = YES일 경우 s $\in$ X )도 성립하는 경우 A를 problem X를 해결하..