Computer Science

가상기억장치(Virtual Memory) 관리 기법

관련 게시글 https://2sjin.tistory.com/66 [컴퓨터공학개론] 가상기억장치(Virtual Memory)의 관리 ■ 가상기억장치(Virtual Memory)의 관리 1. 개요 RAM과 같은 주기억장치의 용량이 부족하다면, 주기억장치를 확장하는 방법도 있지만, HDD와 SSD 등의 보조기억장치 일부 영역을 주기억장치와 논리 2sjin.tistory.com 1. 개요 가상기억장치는 대용량 프로그램이 수행하는 데 필요한 주기억장치의 공간만큼이 있는 것처럼 동작이 되도록 한다. 프로그램의 동작이 지역성(locality)을 가지기 때문에 아무리 큰 프로그램도 특정 시점에 특정 프로그램 코드만 주 기억장치에 상주하면 프로그램이 실행하는 데 아무 문제가 없다는 것에 착안한 개념이다. ① 장점 적은 ..

교착상태(Deadlock) 발생 조건 및 예방법

1. 교착상태(Deadlock)란? 두 개 이상의 프로세스가 자신이 가진 자원은 계속 가지고 있으면서 서로 상대방이 가진 자원을 요구하게 되는 상태. 2. 교착상태 발생 조건 아래 4가지 조건이 모두 발생하면(AND 조건 만족) 데드락이 발생할 가능성이 있다. ① 상호 배제(Mutual exclusion) 조건 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구 ② 대기(Waiting) 조건 할당된 자원을 가진 상태에서 다른 자원을 기다리는 경우 ③ 비선점(Non-preemption) 조건 프로세스에게 할당된 자원은 사용이 끝날 때까지 프로세스로부터 제거할 수 없음 ④ 환형 대기(Circular wait) 조건 자원 할당 그래프 내에 환형 대기가 존재함 3. 교착상태 예방법 ① 상호 배제(Mut..

프로세스 실행 다이어그램

1. 프로세스 실행 다이어그램 ① 대기(Ready) → 실행(Run) CPU를 차지하기 위해 대기 중인 Process가 CPU를 가짐 Process는 Ready Queue에서 선입선출(FIFO)로 CPU를 가지게 됨 Dispatcher에 의해 Dispatch가 이루어진다고도 표현할 수 있음 ② 실행(Run) → 대기(Ready) CPU를 가지고 있는 Process에 타임 슬라이스(Time Slice)만큼 CPU 시간 할당 주어진 CPU 시간이 끝나고, 작업을 완료하지 못하면 Ready Queue로 이동하여 대기 CPU 사용의 공정성을 보장함 ③ 실행(Run) → 슬립(Sleep) Process 실행 도중 입출력(I/O) 연산이 일어나면 Sleep Queue로 이동 CPU보다 매우 느린 I/O 장치와 CP..

운영체제의 기능과 역할, 실시간 운영체제

1. 운영체제의 기능과 역할 ① 시스템 자원(System Resource)을 효율적이고 공정하게 관리하는 역할을 함 ② 데이터 추상화(Data abstraction) 사용자에게 OS 동작을 숨김 사용자가 OS의 존재를 인식하지 못하도록 하고, 편리성을 제공함 ③ 운영체제의 수행 모드 사용자 영역(User Area, User Address Space) 커널 영역(Kernel Area, Kernel Address Space) ④ 운영체제의 의미 넓은 의미(비전문적 의미): 커널 + 라이브러리 + 모듈 좁은 의미(전문적 의미): 커널 ⑤ 운영체제(커널)의 4가지 기능 모듈 프로세스 관리(Process Management): CPU 관리 메모리 관리(Memory Management): 주기억장치(Main Mem..

[알고리즘 과제] 해싱(Hashing)

1. 해싱(Hashing)이란? 데이터를 해시 함수(Hash Function)를 이용하여 해시 테이블(Hash Table) 내에서 주소값 계산 후, 빠르게 저장하고 원하는 데이터를 빠르게 검색할 수 있도록 하는 알고리즘. [해싱 알고리즘] ① 데이터를 매개 변수로 입력 ② 데이터로부터 테이블 내의 주소를 해시 ③ 주소를 이용하여 요소에 접근 2. 해싱(Hashing) 알고리즘 성능 일반적으로 O(1) Overflow 또는 Collision 발생 시에는 O(1)보다 성능이 떨어진다. 성능 향상을 위해 Hash Table의 크기를 적절히 크게 할 필요가 있다. 3. 해싱(Hashing) 의 활용 소량의 데이터를 처리할 때(데이터 개수가 많지 않을 때) 적합한 알고리즘 운영체제, DB, 네트워크 등 여러 분야..

[알고리즘 과제] 퀵 정렬(Quick Sort) 알고리즘

1. 의사 코드(Pseudo Code) ① 데이터 집합 내에서 기준 요소를 선택하고, 기준 요소보다 작은 요소들은 순서에 관계없이 무조건 기준 요소의 왼편에, 큰 값은 오른편에 위치시킨다. ② 기준 요소 왼편에는 기준 요소보다 작은 요소들이 모여 있고, 오른편에는 큰 요소들이 모여있게 된다. 이렇게 나눈 데이터 집합들을 다시 ①과 같이 임의의 기준 요소를 선택하고, 같은 방법으로 데이터 집합을 분할한다. ③ 과정 ①~②를 더 이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합을 얻게 된다. 2. 퀵 정렬 수행 과정

[알고리즘 과제] 연결 리스트 삽입 및 삭제

해당 게시글의 소스 코드는 특정 언어가 아닌, 의사 코드(Pseudo Code)로 작성되었습니다. 1. 노드 삽입(마지막 부분) Input: head, node_new(삽입할 노드) if head == NULL: ① head -> node_new else: ① node_c의 next -> node_new ② node_new의 prev -> node_c ③ tail -> node_new 2. 노드 삽입(중간 부분) Input: node_a의 위치(삽입할 위치), node_new(삽입할 노드) ① node_new의 next -> node_a의 next ② node_new의 prev -> node_a ③ if node_a의 next != NULL: node_a의 next의 prev -> node_new ④ n..

[알고리즘 과제] 알고리즘 분석 방법

1. 알고리즘의 우수함을 가리는 기준 1) 정확성 - 정확하게 동작하는가? - 입력값에 대한 정확한 출력을 몇 번 제공하는지를 나타냄 2) 작업량 - 얼마나 적은 연산을 수행하는가? - 프로그램의 코드 길이가 가능할 짧을 것 - 예: 버블 정렬의 비교 연산 횟수, 이진 탐색의 거치는 노드의 개수 3) 메모리 사용량 - 얼마나 적은 주기억장치(RAM)를 사용하는가? - 요즘에는 주기억장치(RAM) 용량이 매우 크지만, 여전히 중요한 기준임 4) 단순성 - 알고리즘이 얼마나 단순한가? - 단순성을 만족하는 알고리즘의 예로는 이진 탐색, 퀵 정렬 등이 있음 5) 최적성 - 개선의 여지가 없을 만큼 최적화되어 있는가? - 최적의 성능을 위하여 개선 가능한 모든 요소(작업량, 메모리, 사용량) 최적화 - 알고리즘..

[정보보호] 공개 키 암호, 하이브리드 암호

1. 공개키 암호 알고리즘 공개 키 암호(Public Key Cryptosystem) 알고리즘은 암호화와 복호화에 서로 다른 키를 사용하는 비대칭 키 알고리즘이다. 공개 키 암호에서는 암ㆍ복호화를 위해 반드시 한 쌍의 키가 필요하다. 한 쌍의 키는 공개 키와 개인 키로 구성되어 있다. 공개 키(Public Key)는 공개된 저장소에 보관하는 키로, 제3자가 알고 있어도 상관이 없다. 반면 개인 키(Private Key)는 소유자 자신만 알고 있어야 한다. 공개 키는 송ㆍ수신자가 서로 다른 키를 사용하므로 제삼자에게 비밀이 누설될 가능성이 없다. 공개 키 암호는 대칭 키 암호보다 구조가 복잡하여 속도가 느리다. 따라서 공개 키 암호는 적은 양의 메시지 비밀통신에 적합하다. 공개 키 암호는 정보의 기밀성, ..

[정보보호] 블록 암호, 블록 암호 모드

1. 블록 암호란? 블록 암호(Block Cipher)는 데이터를 고정 길이의 블록(64bit, 128bit 등)으로 나누어 암ㆍ복호화를 수행하는 암호 알고리즘을 말한다. 평문 데이터의 길이가 블록 크기보다 클 때는 블록 단위로 나누어서 암호화를 해야 한다. 이렇게 여러 개의 블록을 암호화하기 위한 운영 방식을 ‘블록 암호 모드’라고 한다. 블록 암호 모드의 종류로는 ECB 모드, CBC 모드, CFB 모드, OFB 모드, CTR 모드가 있다. 2. ECB 모드 ECB 모드는 Electric CodeBook mode(전자 부호표 모드)의 약자이다. ECB 모드에서는 평문 블록을 암호화한 것이 그대로 암호문 블록이 된다. 따라서 ECB는 5가지 모드 중 가장 단순하며 기밀성이 가장 낮은 모드이다. 암호문 ..