왈왈이의 기술블로그

페이지 교체 알고리즘 페이지 폴트 발생 시 스와핑이 일어날 때, 페이지 교체 알고리즘(page replacement algorithm)에 의해 페이지가 교체된다. 이론상의 알고리즘인 오프라인 알고리즘과, 실제 사용되는 4가지 알고리즘에 대해 알아보자. 오프라인 알고리즘 오프라인 알고리즘은 가장 좋은 알고리즘이라고 일컫는 알고리즘으로, 가장 먼 미래에 참조될 페이지와 현재의 페이지를 바꾸는 알고리즘이다. LFD(Longest Forward Distance)라고도 한다. 예를 들어, 메모리에 세 자리가 있고, 0, 1, 2, 3, 4, 2 페이지가 순서대로 들어온다면 가장 먼 미래에 참조되는 2와 스와핑 하는 방식이다. 그러나 미래에 사용될 프로세스를 미리 알 수 없기에, 현실에서는 사용할 수 없는 알고리즘..

가상 메모리(virtual memory) 가상 메모리는 OS에서 사용되는 메모리 관리 기법 중 하나로, 컴퓨터가 실제로 이용 가능한 메모리 자원(실제 주소, physical address)를 추상화하여 사용자들에게 매우 큰 메모리로 보이게 만드는 것을 말한다. 가상 주소는 MMU와 페이지 테이블(page table)에 의해 실제 주소로 변환된다. *페이지: 가상 메모리를 사용하는 최소 크기 단위 *프레임: 실제 디스크나 메모리를 사용하는 최소 크기 단위 페이지 테이블 가상 메모리는 가상 주소와 실제 주소가 매핑 되어있는 페이지 테이블로 관리되며, 이 때 속도 향상을 위해 캐싱 계층인 TLB를 사용한다. 가상 주소에서 바로 페이지테이블로 가지 않고, TLB에 실제 주소가 있는지 확인하고, 만약 없다면 페이..

메모리 계층 메모리 계층(memory hierarchy)은 레지스터, 캐시, 주기억장치(RAM), 보조기억장치(HDD, SSD)로 구성된다. 특징 휘발성 속도 기억 용량 레지스터 CPU 내의 작은 메모리 휘발성 속도 가장 빠름 기억 용량 가장 적음 캐시 CPU 내 L1, L2 캐시 휘발성 속도 빠름 기억 용량 적음 주기억장치 RAM 휘발성 속도 보통 기억 용량 보통 보조기억장치 HDD, SSD 비휘발성 속도 낮음 기억 용량 많음 계층이 존재하는 이유 더 빠른 접근과 처리 속도 증가 보통 많이 쓰는 것을 다시 많이 쓴다. 이러한 특성 때문에 특정 데이터에 많이 접근하게 되는데, 좀 더 작은 캐시 메모리에 해당 데이터가 있다면 더 빠르게 접근이 가능하고, 이로 인해 처리 속도도 더 빨라진다. 비용 효율성 캐..

문제에서 10진수를 n진법 수로 변환하라고 하는 경우가 있다. 아래는 10진수 n = 100을 2진수로 변환하는 코드이다. n에는 변환하고자 하는 10진수 수를, b자리에는 몇 진법으로 변환할 지 숫자를 넣으면 된다. n의 값이 1만큼 작아질 때까지 n을 b로 나눈 나머지 값을 배열에 저장하고, n을 b로 나눈 몫으로 갱신한다. 마지막 몫이 1이라면 그 값을 배열에 넣는다. 배열을 뒤집고, 각 값을 연속으로 출력하면 n진법 변환이 완성된다. 다만, 16진법은 알파벳을 사용하기에 그 부분을 적용하기 위해서는 10이상의 값은 알파벳으로 변환하는 과정이 필요하다. #include using namespace std; vector v; int main(){ int n = 100; int b = 2; while(..

순열과 조합은 알고리즘 문제들의 단골 요소다. 경우의 수를 순열과 조합으로 확인하여 풀어야하는 경우들이 많다. 배열의 순열과 조합을 확인하는 방법을 알아보자. 순열 순열은 next_permutation이라는 메서드를 활용하는 것이 가장 간단한 방법이다. next_permutation을 사용하기 전에 반드시 배열을 오름차순 정렬해야 함을 주의하자. #include using namespace std; int main() { int a[3] = { 1, 3, 2 }; sort(a, a+3); do{ for(int i : a) cout

C++의 장점 중 하나는 알고리즘 문제 풀이에 최적화된 다양한 자료구조를 사용할 수 있다는 점인 것 같다. 매우 다양한 자료구조들이 있는데, 그 중 초보자 수준에서 반드시 알아야 하는 자료구조들만 먼저 정리해본다. vector, array, map, stack, queue 5개만 알아보자. vector vector는 배열의 길이를 알 수 없을 때 사용하는 동적 배열로 코테에서 가장 많이 사용되는 자료구조다. 일반 정적 배열과 유사하지만, 정적 배열과 달리 사용할 수 있는 메서드가 많고, 초기화 방법 등이 조금 다르다. 백준과 같이 모든 코드를 직접 작성하는 경우에는 정적 배열을 최대 크기로 선언하여 사용하기도 하지만 프로그래머스 같은 경우에는 문제에서 vector로 변수를 지정하는 경우가 대부분이다. 타..

코딩 테스트 준비를 위해 C++에 입문한 지 얼마되지 않아, 아직은 기본적인 사용법도 헷갈리는 상태다. 여태까지 문제를 풀며 초보적인 수준에서 가장 자주 사용했던 자료 구조와 메서드 등을 정리 해본다. 입력과 출력 프로그래머스 같은 경우 보통 직접 값을 입력받고 출력하지 않아도 되지만, 백준 같은 경우, 직접 값을 입력 받고 출력 하는 코드도 작성해야 한다. 프로그래머스를 사용한 시험에서도 값을 입력받아야 했던 적도 있다. (그 때 매우 당황했다.) 일반적인 경우, 입력과 출력은 cin/cout을 사용하여 간단히 처리할 수 있다. int n, m; cin >> n >> m; cout

시스템콜 시스템콜이란 운영체제가 커널에 접근하기 위한 인터페이스로 유저 프로그램이 운영체제의 서비스를 받기 위해 커널 함수를 호출할 때 이를 거쳐 호출하도록 설계되어 있다. 프로세스 관리(생성/삭제 등), 파일 관리, 디바이스 관리, 시간 및 날짜 관련 시스템, 프로세스 간 통신 때 시스템콜을 통해 커널 함수를 호출한다. 예를 들어, 프로세스를 종료하는 kill() 함수가 있는데, 이 함수를 발동시키면 시스템콜을 거쳐 커널 함수가 호출되게 된다. 과정 만약 유저프로그램이 I/O 요청을 위한 트랩을 발동했다고 하면, 다음과 같은 과정이 발생된다. 유저 프로그램이 I/O 요청 트랩을 발동한다. 올바른 I/O 요청인지 확인한다. 유저 모드가 시스템콜을 통해 커널모드로 변환한다. 이후 커널 함수를 실행한다. 커..

CPU CPU란 산술 논리 연산 장치, 제어 장치, 레지스터로 구성되어 있는 장치이다. 인터럽트에 의해 메모리에 존재하는 명령어를 해석하여 실행하는 일꾼이다. 산술 논리 연산 장치 산술 논리 연산 장치는 ALU(Artihmetic and Logical Unit)라고도 하며, 덧셈, 뺄셈, 나눗셈 등 산술연산과 논리연산을 수행하는 장치다. 제어 장치 제어 장치(control unit, CU)는 프로세스의 조작을 지시하며, 명령어들을 읽고 해석하여 데이터 처리 순서를 결정한다. 레지스터 CPU 안에 있는 작고 매우 빠른 임시 기억 장치 CPU의 처리 과정은 아래와 같이 정리할 수 있다. 제어장치가 메모리에 있던 일을 레지스터에 올림 제어장치가 ALU에게 레지스터에 있는 값을 읽고 계산하라고 명령 제어장치가 ..

컴퓨터의 구조와 원리에 대해 알아보자. 운영체제(Operating System, OS) 운영체제의 종류 운영체제는 인터페이스의 종류에 따라 GUI(Graphic User Interface)와 CUI(Character User Interface)로 나눠진다. GUI(Graphic User Interface) GUI는 그래픽을 사용하여 컴퓨터와 상호작용하는 인터페이스이다. 현대의 windowOS, macOS 등이 GUI이다. CUI(Character User Interface) CUI는 사용자가 키보드만으로 사용하여 문자를 기반으로 컴퓨터와 상호작용하는 인터페이스이다. 과거에 사용되던 MS-DOS가 대표적인 CUI 운영체제이나, 1994년 단종되었다. chatGPT도 CUI 형태라고 볼 수 있다. 운영체제의..