CS

시스템 구조와 프로그램 실행 1

시스템 구조 CPU : 매 클럭 사이클 마다 메모리에서 인스트럭션을 읽어 실행 registers : 메모리보다 더 빠르면서 저장할 수 있는 공간 mode bit : CPU에서 실행되는 것이 운영체제인지 사용자의 프로그램인지 구분해주는 bit Interrupt line : I/O device의 신호를 전달해주는 통로. 인스트럭션이 끝날 때마다 CPU가 체크한다. 들어온 신호가 있다면 운영체제에게 CPU가 넘어감. 메모리 : CPU의 작업공간 I/O device : 별개의 입출력 장치. 프로그램은 접근을 못하고 운영체제를 통해서만 접근할 수 있다. device controller : I/O device를 전담하는 컨트롤러. 디스크의 내부를 통제 local buffer : device contoller의 작업..

PCB(Process Control Block)란?

PCB는 운영체제가 프로세스를 제어하기 위해 정보를 저장해 놓는 곳으로, 프로세스의 상태 정보를 저장하는 자료구조다. 운영체제에서 프로세스는 PCB로 표현된다. 프로세스가 생성될 때마다 고유의 PCB가 생성되고, 주기억장치에 유지되며, 프로세스가 완료되면 PCB도 함께 제거된다. 프로세스 상태 관리와 문맥 교환(Context switch)을 위해서 필요하다. 운영체제에 따라 PCB에 포함되는 항목이 다를 수 있지만, 일반적으로 다음과 같은 정보가 포함되어 있다. PCB에 포함되는 정보 포인터 : 부모프로세스에 대한 포인터, 자식 프로세스에 대한 포인터, 프로세스가 위치한 메모리 주소에 대한 포인터, 할당된 자원에 대한 포인터 정보 등. 프로세스 상태(Process State) : 생성(create), 준..

문맥 교환 Context Switching

하나의 프로세스가 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해, 이전의 프로세스의 상태(문맥)를 보관하고 새로운 프로세스의 상태를 적재하는 작업 프로세스의 문맥(context)은 PCB에 저장된다. 인터럽트(interrupt)가 발생하면 시스템은 현재 수행 중인 프로세스의 문맥을 저장하고, 이후 해당 프로세스가 재개될 때 복원한다. CPU 코어를 다른 프로세스로 교환 현재 프로세스의 상태를 저장 다른 프로세스의 상태를 복원하는 작업(task)를 말한다. 교환 시점 멀티태스킹 인터럽트 핸들링 사용자 모드와 커널 모드 간의 전환 준비 → 실행, 실행 → 준비, 실행 → 대기 전환 시 문맥 교환 발생 교환 필요한 상황 교환 과정 문맥 교환과 오버헤드 문맥을 교환하는 동안에는 유용..

캐시가 동작하는 아주 구체적인 원리

Principle of Locality 지역성에는 시간적 지역성과 공간적 지역성, 순차적 지역성이 있다. 시간적 지역성 : 최근에 액세스 된 프로그램이나 데이터가 가까운 미래에 다시 액세스 될 가능성이 높음을 의미한다. 반복루프, 서브루틴 호출, 공통 변수가 대표적인 예시다. 공간적 지역성 : 기억장치 내에 인접하여 저장된 데이터들이 연속적으로 액세스될 가능성이 높음을 의미한다. 표, 배열의 데이터가 그 대표적 예시다. 순차적 지역성 : 분기가 발생하지 않는 이상 명령어들이 기억장치에 저장된 순서대로 인출되어 실행됨을 의미한다. 이는 공간적 지역성에 편입되어 설명되기도 한다. 한 프로세스 안에도 자주 사용하는 부분과 그렇지 않은 부분이 있기 때문에 운영체제는 프로세스를 페이지(Page)라는 단위로 나눠 ..

캐시 히트율/메모리 적중률 (Hit Rate)

캐시 메모리는 CPU의 처리 속도와 주기억장치의 접근 속도 차이를 줄이기 위해 사용하는 고속 Buffer Memory이다. ※ 캐시 메모리 이용 효과 프로그램의 실행과정을 분석해 보면, 주어진 시간 동안에 참조하는 메모리 영역은 국한된다는 사실을 알 수 있다.(메모리 참조의 국부성) 따라서 자주 참조되는 프로그램의 일부를 속도가 빠른 기억장치에 저장해 놓고 실행시키면 프로그램의 총 실행시간을 단축시킬 수 있다. 이때 이용하는 기억장치를 캐시 메모리라고 한다. 캐시 메모리의 특징 캐시는 주기억장치와 CPU사이에 위치하며, 자주 사용하는 프로그램과 데이터를 기억한다. 캐시 메모리는 메모리 계층 구조에서 가장 빠른 소자이며, 처리 속도가 거의 CPU의 속도와 비슷할 정도이다. 캐시를 사용하면 주기억장치를 접근..

Union-Find (합집합 찾기) 알고리즘

Disjoint Set의 개념 서로 중복되지 않는 부분 집합들 로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 즉, 공통 원소가 없는, 즉 “상호 배타적” 인 부분 집합들로 나눠진 원소들에 대한 자료구조이다. Disjoint Set = 서로소 집합 자료구조 Union-Find의 개념 Disjoint Set을 표현할 때 사용하는 알고리즘 집합을 구현하는 데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그 중 가장 효율적인 트리 구조 (아래 참고*)를 이용하여 구현한다. 아래의 세 가지 연산을 이용하여 Disjoint Set을 표현한다. Union-Find의 연산 make-set(x) 초기화 x를 유일한 원소로 하는 새로운 집합을 만든다. union(x, y) 합하기 x가 속한 집합과 y..

페이징(Paging)이란? 페이지 테이블이란?

페이징(Paging)이란? 논리주소의 메모리를 고정된 크기의 페이지(Page)로 나누어 관리하는 기법이다. 페이징은 아래와 같은 특징들을 갖고 있다. 물리주소 공간(Physical address)은 연속적이지 않을 수 있다(noncontiguous) 페이지는 모두 같은 크기를 가진다. 물리주소 공간을 페이지와 같은 사이즈로 나눈 것들을 프레임(Frame)이라고 한다. 페이지 사이즈(=프레임 사이즈)는 하드웨어에 의해 정해진다. 페이지의 크기는 일반적으로 2의 제곱수를 사용한다. 일반적으로 4KB(2^12) ~ 1GB(2^20) 페이지 테이블(page table)을 이용해 논리주소에서 프레임을 가리키는 물리주소로 매핑한다. 외부 단편화는 발생하지 않으나, 내부 단편화는 발생한다. 페이지 테이블(Page T..

라빈-카프 알고리즘 (Rabin-Karp) 해시값을 통한 문자열 비교

정의 / 시간 복잡도 O(n) 문자열에 해싱 기법을 사용하여 해시 값으로 비교하는 알고리즘이다. 간단하게 해시 값을 만들려면 문자열의 각 문자(ASCII TABLE 값)에 특정 수의 제곱 수를 차례대로 곱하여 모두 더하면 된다. 이러한 방식을 사용하면 두 문자열이 서로 다를 때 두 문자열의 해시 값이 다르게 나오게 된다. 예를 들어 ABCD와 ABED라는 문자열이 있을 때 ABCD의 해시 값은 65 * 3^3 + 66 * 3^2 + 67 * 3^1 + 68 * 3^0 = 2618 ABED의 해시 값은 65 * 3^3 + 66 * 3^2 + 69 * 3^1 + 68 * 3^0 = 2624 이므로 ABCD와 ABED 두 문자열은 서로 일치하지 않는다는 결과가 된다. 간혹 해시 값이 서로 충돌하는 해시 충돌 ..

보드 게임 관련 AI 알고리즘 [구현 예정]

테트리스 - 유전 알고리즘 (Gnome Algorithm) 오목 - 최소극대화 알고리즘 (Min Max Algorithm) 체스 - 최소 극대화, 알파-베타 가지치기 (Alpha–beta pruning) , Move Ordering, 전치 테이블 (Transposition table), Quiescence search 미로 찾기 - 다익스트라 > A* > JPS 각 알고리즘 별로 퍼포먼스 차이 결과 도출할 예정 지뢰 찾기 - Straightforward Algorithm, The Tank Solver Algorithm, Two Endgame Tactics 오델로 - 최소 극대화, 휴리스틱

스레드 풀 (Thread Pool)

쓰레드 풀에 대한 이해 쓰레드의 생성과 소멸은 시스템에 많은 부담을 준다. 따라서 빈번한 쓰레드의 생성과 소멸을 피하기 위해선 쓰레드 풀을 유지하는 것은 성능 향상에 도움이 된다. 쓰레드 풀의 기본 원리는 쓰레드의 재활용이다. 할당된 일을 마친 쓰레드를 소멸시키지 않고, 쓰레드 풀에 저장해 뒀다가 필요할 때 다시 꺼내 쓰는 개념이다. 즉, 쓰레드의 생성과 소멸에 필요한 비용을 지불하지 않겠다는 것이다. 쓰레드 풀 동작 원리 쓰레드 풀은 처리해야 할 일(work)이 등록되기 전에 생성되는데, 풀이 생성됨과 동시에 쓰레드들도 생성되어 풀에서 대기하게 된다. 쓰레드 풀에 존재하는 쓰레드 하나를 임의로 할당해서 일의 처리를 도모한다. 만약 풀에 존재하는 쓰레드 수보다 처리해야 할 일의 수가 많다면, 일이 순서대..