분류 전체보기

SystemSoftware - Creating Processes #1

OS에서 process를 만드는 방식에 대해서 알아보자 process는 fork()라는 syscall을 통해서 child process를 생성한다. fork를 호출한 process가 parent process가 되고, 새로 생긴 process가 child가 process이다. int fork(void) return을 2번 한다. parent에서 fork를 호출하면 child에서 return 하고 parent에서도 return 한다. 이때 return 값에 따라서 parent인지 child인지를 구분할 수 있다. 0을 return 하면 child이고, child의 PID를 return 하면 parent이다. child는 parent의 모든 부분이 복제되어 생성된다. (가상 주소, parent에서 open ..

[백준 14442] 벽 부수고 이동하기2 C++

14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net BFS 1. 문제해결 아이디어 매번 칸을 이동할 때마다 지금까지 몇 개의 벽을 부쉈는지 정보를 가지고 있어야한다. struct P를 만들고 해당 객체를 queue에서 가지고 다니게 하였다. 가장 중요한 visited배열이다. visited[r][c][k] = 1 : r, c를 방문할 때 총 k번 벽을 부수고 방문했음을 의미한다. 만약 다음 좌표가 3, 5이고 지금까지 부순 벽이 2개라면 visited[3][5][3]이 0인지 확..

SystemSoftware - Exceptional Control Flow #2

SystemSoftware - Exceptional Control Flow #1 예외상황(예외처리)에 관해서 알아보자 예외 상황 : Segmentation Fault, Hardware Interrupt 등을 예외 상황이라고 한다 CPU는 명령어 주소에 있는 레지스터에 적혀있는 메모리에 가서 명령을 수행하고, 다 hyeo-noo.tistory.com 이전 포스팅에 이어서 Process와 context switch에 대해서 알아보자 Process : 실행중인 Program에서의 instace (Program : class, Process : object 라고 하기도 한다) Process의 추상화를위한 2개의 중요한 key 가 있다. 1. Logical control flow : 각각의 program이 cpu..

SystemSoftware - Exceptional Control Flow #1

예외상황(예외처리)에 관해서 알아보자 예외 상황 : Segmentation Fault, Hardware Interrupt 등을 예외 상황이라고 한다 CPU는 명령어 주소에 있는 레지스터에 적혀있는 메모리에 가서 명령을 수행하고, 다음 명령어를 받고 메모리에 가서 명령을 수행하는 반복적인 작업을 컴퓨터가 꺼질 때까지 반복한다. 이러한 시퀀스를 Control Flow라고 한다. 일반적으로 코드는 연속적으로 실행된다. 하지만 jump와 branch 같은 제어문(if, for loop)을 통해서 control flow를 바꿀 수 있다. 그리고 함수 호출을 통해서도 control flow를 제어할 수 있다. 하지만 위와 같이 일반적으로 제어할 수 없는 부분(system 상태의 변화)이 존재한다. 하드디스크, 네트..

[백준 1007] 벡터 매칭 C++

1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 브루트 포스 1. 문제해결 아이디어 처음에 단순히 최대 20개의 점 중에서 2개씩 묶어 나가는 방법으로 풀려고 했다. 위 방법대로 하면 O(20 * 18 * ... * 4 * 2) 같은 끔찍한 시간복잡도가 나와 불가능함을 알 수 있었다. v1, v2 이라는 벡터가 있다고 가정해보자 v1 + v2 = = 이 된다. 여기서 알 수 있는점은 N개의 점 중에서, N/2개의 점은 시작점이 될 것이고, 나머지 N/2개의 점은 도착점이 되는 것을 알 수 있다. 따라..

[XV-6 운영체제] Copy-on-Write #2 구현

[XV-6 운영체제] Copy-on-Write #1 Copy-on-Write가 어떤 기능을 하는지 알아보자 Copy on Write는 기본적으로 forks 기능과 관련이 있다. forks는 parent process를 이용해서 child process를 만들어 내는 것으로 볼 수 있다. (기본적으로 복제를.. hyeo-noo.tistory.com 이전 포스팅인 Copy-on-Write에 대한 설명에 이어서 Copy-on-Write를 구현해 보겠다. 1. vm.c 수정 page table entry(PTE)에 writeable flag(PTE_W)를 disable (read-only 상태로 만들어준다) 새로운 page 할당없이 parent process의 page를 child process의 mapping..

[XV-6 운영체제] Copy-on-Write #1

Copy-on-Write가 어떤 기능을 하는지 알아보자 Copy on Write는 기본적으로 forks 기능과 관련이 있다. forks는 parent process를 이용해서 child process를 만들어 내는 것으로 볼 수 있다. (기본적으로 부모 프로세스를 복제함) 대부분의 자식 프로세스들은 이후에 exec을 이용해서 새로운 process로 Overwite한다. 그러면 부모로부터 복사해온 페이지들은 다 쓸모없는 것들이 되고 만다. 복사를 하고 바로 exec을 통해서 새로운 process를 만들어 낼 텐데 굳이 복사를 할 필요가 있는가? 라는 의문에 의해서 탄생한 것이 Copy on Write 라는 방법이다. Copy on Write : parent process의 이미지를 child에 복사하지 않..

[컴퓨터 구조] ILP & Superscalar

ILP : Instrction Level Parallelism ILP의 2가지 방법 Superscalar : 1 Cycle 동안에 서로 다른 독립적인 2개의 연산을 동시에 수행하는 기술이다. Superpipeline : 한 클럭을 2개로 나누고, 나누어진 클럭에서 각각 서로 다른 연산을 수행하는 기술이다. ILP실행의 한계점 1. True Data Dependency ADD의 r1과 MOVE의 r1은 서로 의존적이다. pipeline에서의 타이밍을 맞추지 못하면 MOVE에서 잘못된 r1값(add가 되기 전의 r1)을 받아서 틀린 연산 결과를 낼 수 있다. 2. Procedural Dependancy if(~) ... else(~) ... 위와 같은 branch가 있을 때 branch이전과 branch 이..

SystemSoftware - Linking #2

SystemSoftware - Linking #1 컴파일된 object 파일들을 linking해서 exe파일로 만드는 과정에서 어떤 일들이 일어나는지 알아보자 // main.c int sum(int *a, int n) int array[2] = {1, 2} int main(){ int val = sum(array, 2); return val;.. hyeo-noo.tistory.com 지난 글에 이어서 Linking을 하는 2가지 방법에 대해서 알아보자 다 쓰고 파일 날아가서 다시 씀 일반적으로 사용하는 함수의 Packaging 모든 함수를 하나의 source file에 넣는경우 : 공간과 시간측면에서 비효율적임 각각의 함수마다 나누어진 source file에 넣는 경우 : 효율적 Static librar..

[컴퓨터 구조] RISC (feat. CISC)

CICS구조를 비교 모델로 삼아 RISC구조에 대해서 알아보자. RISC(Reduced Instruction Set Computer) - 명령어가 축약된 컴퓨터 명령어 set이 매우 짧고 심플하다 CISC에 비해서 레지스터의 수가 매우 많다 (CISC : 8~16, RISC : 32~520) 소프트웨어적인 기술의 중요성이 크다 (컴파일러의 역할 증가(레지스터 최적화)) 명령어의 개수 : 60~100 (CISC : 200~300) 명령어의 크기 : 4 (CISC : 1 ~ 60) addressing mode : 1 (레지스터를 사용) (CISC : 4 ~ 22) CISC(Complex Instruction Set Computer)가 나오게 된 이유, 장점 과거에는 소프트웨어보다 하드웨어 기술이 상대적으로 ..