컴퓨터 과학
-
컨텍스트 스위칭컴퓨터 과학/운영체제 2022. 1. 9. 20:57
멀티 스레드 컨텍스트 스위칭 스레드는 프로세스의 메모리를 공유하고 스택만 독립적으로 가지므로 TCB만 교체됨 TCB에는 스레드 ID, 레지스터(stack pointer, pc 등), 스레드 상태(ready, running, waiting etc), PCB 포인터 등을 저장 다른 가상 메모리로의 전환이 필요없고 TLB와 캐시 메모리가 플러싱되지 않음 멀티 프로세스 컨텍스트 스위칭 컨텍스트 스위칭뿐만 아니라 메모리 전환도 일어남 프로세스 마다 가상 메모리가 할당되기 때문 메모리 주소, 페이지 테이블, 캐시 등도 바뀜 접근하는 가상 메모리 주소가 달라졌기 때문에 TLB의 기존 데이터는 플러싱되고 새 프로세스의 정보로 채워짐 프로세스를 메모리에 올렸다가 내리는 과정의 오버헤드가 크다 프로세스가 스위칭되면 PCB..
-
그래프 간선의 분류 간단 정리컴퓨터 과학/자료구조와 알고리즘 2021. 9. 14. 22:41
참고 https://rebro.kr/71 https://hy38.github.io/about-edges-in-graph https://bowbowbow.tistory.com/1 https://www.tutorialspoint.com/data_structures_algorithms/spanning_tree.htm 설명 아래와 같은 그래프가 있습니다. 1번 정점부터 깊이 우선으로 탐색을 시작하면 다음과 같은 스패닝 트리가 나옵니다. 스패닝 트리를 연결하고 있는 간선을 스패닝 트리 간선이라고 합니다. 스패닝 트리에는 순환이 없습니다. 스패닝 트리는 이미 방문한 노드는 방문하지 않기 때문에 (5, 1), (6, 4), (6, 3), (1, 7) 간선은 스패닝 트리에 포함되지 않습니다. 여기에서 순방향 간선, 역..
-
스케줄링 알고리즘컴퓨터 과학/운영체제 2021. 8. 18. 03:07
FCFS(First-Come-First-Served) 이름 그대로 CPU를 먼저 요청한 프로세스가 CPU를 먼저 할당받습니다. 요청한 순서대로 처리됩니다. 만약 버스트 시간이 긴 프로세스가 요청을 앞서 했다면 평균 대기 시간이 길어집니다. 프로세스들이 처리 시간이 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과(convoy effect)라고 합니다. 비선점형입니다. SJF(Shortest-Job-First) 최단 작업 우선 알고리즘입니다. CPU는 가장 작은 버스트를 가진 다음 프로세스에 할당됩니다. 프로세스 전체의 길이가 아니라 CPU의 버스트의 길이에 의해 스케줄링이 되기 때문에 Shortest-next-CPU-burst 알고리즘이라는 용어가 더 적합합니다. SJF 스케줄링 알고리즘은 프로..
-
동시성(concurrentcy) vs 병렬성(parallelism)컴퓨터 과학/운영체제 2021. 8. 11. 15:41
동시성 동시성은 동시에 작동하는 것처럼 보이는 것에 가깝습니다. 하나의 코어에서 멀티스레드로 여러 프로그램이 돌아갈 때 CPU는 인간이 인지할 때 동시에 작동하는 것처럼 느껴질 만큼 빠르게 여러 프로그램들을 다녀가면서 태스크를 수행합니다. 가벼운 프로그램이라면 크게 상관 없을지도 모르지만 프로그램이 크고 무겁다면 이야기가 다릅니다. 메모리가 무한대가 아니며 메모리 하나당 하나의 프로그램만 돌릴 수 있다고 했을 때 CPU가 할당된 프로그램(혹은 프로세스)이 바뀔 때마다 메모리와 레지스터에 올라와 있는 데이터를 지금 실행 중인 프로그램의 것으로 변경해야 하고 그 전에 있던 내용은 보조 메모리 등으로 옮겨야 하기 때문입니다. 이를 컨텍스트 스위칭이라고 합니다. 멀티프로세서의 컨텍스트 스위칭보다는 멀티스레드의 ..
-
NoSQL컴퓨터 과학/데이터베이스 2021. 8. 10. 19:56
개념 NoSQL은 원래 non sql 혹은 non-relational이라는 의미였지만 sql 계열의 query 언어를 사용할 수 있는 측면을 강조하는 의미에서 Not only SQL로 불리기도 한다. 전통적인 데이터베이스 모델인 관계형 데이터베이스(RDMBS)보다 덜 제한적이면서 비정형의 데이터를 저장 및 검색하는 데 용이하다. 빅데이터를 이용해 서비스를 운용하고 있는 회사는 NoSQL을 활용하는 경우가 많다. 페이스북, 트위터, 넷플릭스, 애플의 아이클라우드 등이다. RDBMS는 데이터 트랜잭션을 안전하게 수행되는 것을 보장하기 위해 ACID(원자성, 일관성, 독립성, 지속성) 성질을 갖고 있지만 NoSQL은 그러한 특성을 제공하지 않는다. 대신 확장성과 성능이 좋고 수평 확장에 유리하다. 서비스 혹은..
-
페이징 정리 - 2컴퓨터 과학/운영체제 2021. 8. 8. 19:52
하드웨어 지원 대부분의 운영체제는 프로세스마다 하나의 페이지 테이블을 할당한다. 페이지 테이블의 하드웨어 구현은 여러 가지 방법이 있는데 간단한 방법은 레지스터를 이용하는 것이다. 하지만 이는 페이지 테이블이 작을 경우에만 가능하다. 32비트 환경의 시스템은 페이지 테이블의 항목이 1백만에 이른다. 페이지의 크기가 4kb일 때, 4gb 메모리를 가진 시스템에서 페이지의 수가 1백만이기 때문이다. 2^32 / 2^12 = 2^20 -> 1,048,576. 이러한 페이지 테이블을 레지스터를 이용해 구현하는 것은 적절하지 않다. 대부분의 컴퓨터는 페이지 테이블을 주 메모리에 저장하고 페이지 테이블 기준 레지스터(PTBR, Page Table Base Register)가 페이지 테이블을 가리키게 한다. 다른 페..
-
페이징 정리 - 1컴퓨터 과학/운영체제 2021. 8. 8. 17:42
기본 개념 외부 단편화를 해결할 수 있다. 메모리가 프로세스에 할당되고 해지되는 과정에서 생기는, 분산된 메모리 조각을 마치 연속된 공간인 것처럼 사용할 수 있다. CPU는 실제 메모리가 파편되어 있는지 알 수 없고 관심을 가질 필요도 없다. 페이지는 물리 메모리에 할당되는데, 물리 메모리의 할당 단위가 프레임이다. 페이지와 프레임은 같은 크기이다. 32bit cpu는 기본 연산 단위가 32bit이다. 포인터가 32bit(4byte)이므로 표현할 수 있는 주소의 수가 2^32개다. 이는 4,294,967,296개이다(약 42억). 32bit가 말 그대로 비트가 32개 있다는 것이고 1비트당 0, 1의 두 가지를 표현할 수 있기 때문이다. 데이터를 표현하는 기본 단위는 비트이지만 주소의 기본 단위는 바이트..
-
hash map컴퓨터 과학/자료구조와 알고리즘 2021. 8. 7. 21:51
언어 차원에서 제공하는 알고리즘은 성능, 안정성 등에서 검증이 된 것입니다. 그렇지 않으면 해당 언어의 신뢰도에 치명적인 손상을 입힐 수 있기 때문입니다. 때문에 검증된 이론, 수학적으로 증명된 공식 등을 통해서 구현됩니다. 자료구조는 직접 개발하기 위해 공부한다기 보다는 간단한 기능을 직접 구현해보면서 개념과 기본적인 흐름을 파악하는 데 의의가 있는 것 같습니다. 해시맵은 데이터를 배열에 넣습니다. 그러므로 O(1)의 시간복잡도를 가지지만 데이터가 많아질수록 중복된 해시 코드를 얻게 될 확률이 올라갑니다. 그래서 C++ 표준 라이브러리인 std::unordered_map은 일정 수준 이상에서 std::map보다 성능이 안 나올 수 있습니다. 해시맵은 최악의 경우에는 O(n)까지 성능이 저하될 수 있습니..