분류 전체보기

[컴퓨터 구조] Instruction Set

컴퓨터의 Instruction set에 대해서 알아보자 Ex ) 3 + 6 = 9 Operands : '3', '6' Operator : '+' 명령어 사이클의 기본 상태 Diagram을 알아보자 Instruction fetch : 메모리에 있는 명령어를 가져오는 작업(Op code) bring 대신 fetch를 사용한 이유 : CPU가 원하는 명령어의 주소를 메모리에 주고, 해당 주소에 있는 명령어를 받아오는 작업이기 때문에. Instruction operation decoding : 가져온 명령어를 해석한다. Operand의 주소를 계산해서 Operand를 메모리로부터 가져온다. Data Operation : 가져온 Operand와 Op code를 통해서 Data를 계산한다. Data의 계산 결과를 ..

[백준 17387] 선분 교차 2 C++

17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 선분 교차 알고리즘 계산 기하학 알고리즘 중 선분 교차 알고리즘을 공부했다. 1. 문제 해결 아이디어 먼저 두 선분이 교차하는 경우를 알아보자 l1선분의 p1, p2벡터에서 l2선분의 p1으로의 방향과 p1, p2벡터에서 l2선분의 p2로의 방향이 서로 다르다면(한 점이 선분에 포함된 경우 포함) 반드시 두 선분은 교차한다. 두 선분의 직선의 방정식을 구해서 교차하는 한 점을 구하면 선분이 교차하는지 알 수 있지 않을까요? 알 수 없다 아래 두 선분을 보자 l2선분을 직선으로 만들면 l1과 교차하게된다. 하지만 l1과 l2..

[운영체제] Locks #3

[운영체제] Locks #2 [운영체제] Locks #1 Lock에 대해서 알아보자 Lock이 필요한 이유 2개 이상의 tread가 동시에 공유 자원에 접근할 경우 race condition(병행성 문제)이 발생해서 결과를 예측할 수 없다. 따라서 공유 자원에 hyeo-noo.tistory.com 지금까지의 방법들은 매우 비효율적이다. 왜냐하면 lock을 얻기위해서 spin-wait를 하게되는데, 이러한 방식은 CPU를 불필요하게 계속 소모해서 다른 활동을 하지 못하기 때문이다. 따라서 위 문제를 해결할 수 있는 방법들을 알아보자 Just Yield 가장 간단한 구현 방법이다. 만약 lock이 사용중이라면 깔끔하게 CPU를 반납하고 다음 time-slice에 자신의 차례가 올 때까지 기다리는 방법이다. ..

[운영체제] Locks #2

[운영체제] Locks #1 Lock에 대해서 알아보자 Lock이 필요한 이유 2개 이상의 tread가 동시에 공유 자원에 접근할 경우 race condition(병행성 문제)이 발생해서 결과를 예측할 수 없다. 따라서 공유 자원에 대한 동기화 메커 hyeo-noo.tistory.com 하드웨어적으로 lock 변수를 관리하는 instruction에 대해서 알아보자 CPU에서 제공하는 Atomic Instruction을 알아보자 Test and Set test-and-set을 사용한 Spin lock 사용 예 기존의 TestAndSet을 알기 전에는 flag 값이 0인지 확인하기 + flag 값을 1로 바꾸기와 같은 총 2가지 동작으로 나뉘어서 수행을 했다. 그래서 2가지 동작 사이에 context swi..

[운영체제] Locks #1

Lock에 대해서 알아보자 Lock이 필요한 이유 2개 이상의 thread가 동시에 공유 자원에 접근할 경우 race condition(병행성 문제)이 발생해서 결과를 예측할 수 없다. 따라서 공유 자원에 대한 동기화 메커니즘이 필요한데 그중 가장 일반적인 메커니즘이 Lock이다. Critical Section 공유자원에 접근하는 코드의 조각이다. Mutual Exclusion(병행성 해결) Critical Section은 하나의 부분인 것처럼 실행되어야 한다.(Atomically) Critical Section은 한 번에 하나의 쓰레드만 실행 가능하다. 다른 모든 쓰레드들은 Critical Section에 진입하기 위해서 현재 사용 중인 쓰레드가 종료될 때까지 entry에서 기다려야 한다. Lock의 ..

[백준 2150] Strongly Connected Component C++

2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 강한 연결 요소 ㅈㅎㄱ 교수님의 알고리즘 수업에서 강한 연결 요소 문제를 해결하기 위한 코사라주 알고리즘을 배우고 이를 적용하는 문제를 풀어보았다. 1. 문제 해결 아이디어 위와 같은 그래프를 Graph라고 하자 Graph에서 임의의 시작 노드를 잡아서 DFS(시작)를 한다. Graph가 서로 분리된 경우도 생각해야한다.(모든 정점에 대해서 DFS하기) DFS를 하면서 각 정점의 finis..

SystemSoftware - Exceptional Control Flow #3

SystemSoftware - Creating Processes #2 SystemSoftware - Creating Processes #1 OS에서 process를 만드는 방식에 대해서 알아보자 process는 fork()라는 syscall을 통해서 child process를 생성한다. fork를 호출한 process가 parent process가 되고,.. hyeo-noo.tistory.com 지난번에 이어서 Exceptional Control Flow에서의 Shells, Signals, Nonlocal jumps에 대해서 알아보자 Shell : processor를 생성해 주는 역할 shell의 종류 sh shell csh/tcsh bash shell : default Linux shell shell의..

[운영체제] Page Replacement Policy (페이지 교체 알고리즘)

[운영체제] Swapping #1 메모리 swapping에 대해서 알아보자 Swap : 필요한 주소공간 전체를 메모리에 올려 두는것이 아니라 그때 그때 필요한 것들만 메모리에 올리고, 필요없어지면 하드디스크로 내보내는 동작 Swap을 구 hyeo-noo.tistory.com Swap과 관련된 메커니즘에 이어서 page replacement policy에 대해서 알아보자 replacement의 목적은 Cache miss를 최소화하기 위함이다. Cache가 여기서 왜 나왔을까? > 메모리는 하드디스크의 cache역할을 하기 때문이다. Average Memory access time(AMAT) - 평균 메모리 접근 시간 AMAT = (Phit * Tm) + (Pmiss * Td) Tm : 메모리에 접근하는 시..

[운영체제] Swapping (가상 메모리)

메모리 Swapping에 대해서 알아보자 Swap : 필요한 주소 공간 전체를 메모리에 올려 두는 것이 아니라 그때그때 필요한 것들만 메모리에 올리고, 필요 없어지면 하드디스크로 내보내는 동작 Swap을 구현하는 방법들 Overlays : 코드의 일부분, 데이터의 일부분을 가져오고 내보내는 동작을 프로그래머가 수동으로 구현하는 방법 Process-level swapping : Process의 주소공간 전체가 메모리에 올라왔다가, 다른 process가 동작할 때 다시 제자리로 돌아가는 방법. Page-level swapping : Page단위로 디스크에서 가져왔다가 내려보내는 방법 Swap을 하기위한 공간 : swap space 디스크의 일부분을 swap space로 미리 설정을 해줌 swap space의..

[백준 1600] 말이 되고픈 원숭이 C++

1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net BFS 1. 문제 해결 아이디어 이동할 수 있는 방향이 동서남북 외에도 체스의 말(house)이 움직일 수 있는 8방향이 추가된 문제이다. 처음엔 그냥 8방향만 추가해 주고, 말이 움직이는 방향을 먼저 탐색해 주면 풀리겠지 해서 빠르게 틀렸다. [백준 14442] 벽 부수고 이동하기2 C++ 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 ..