programmer life guidance 101

Quiz From execise 4.2: Using Amdahl's Law, calculate the speedup gain of an application that has a 60 percent parallel component for (a) two processing cores and (b) four processing cores. 위 연습문제의 정답으로 가장 옳은 것은? (a) 1.43 (b) 1.8 (a) 1.81 (b) 1.43 (a) 2.56 (b) 2.13 (a) 2.13 (b) 2.56 user-thread와 kernel-thread에 대한 설명으로 가장 틀린 것은? user thread는 사용자 모드에서 동작하고, kernel thread는 커널 모드에서 동작한다. Many-to-..

Quiz Two fundamental models of inter-process communication are: shared-memory and message-passing pipes and sockets sockets and remote procedure call ordinary pipes and named pipes 생산자-소비자 문제를 shared memory로 해결하는 방법에 대한 설명으로 가장 옳은 것은? 운영체제가 알아서 shared memory의 생성과 소멸을 처리해 주므로, 구현하기가 편하다. POSIX 표준에서는 shared memory를 지원하지 않는다. shared memory는 memory-mapped file로만 만들 수 있다. 생산자는 공유 버퍼에 메시지를 write()하고, ..

Quiz In the memory layout of a process, the ______ section is an area of memory that is dynamically allocated during program run time. **heap** stack data code 운영체제에서 프로세스의 상태에 대한 설명으로 가장 틀린 것은? fork() 시스템 콜로 새로운 프로세스를 생성하면 항상 NEW 상태가 된다. **READY 상태에 있는 프로세스에 interrupt를 걸면 WAITING 상태로 천이해서 응답이 올 때까지 대기한다. ** RUNNING 상태의 프로세스가 I/O 처리를 하면 event가 응답할 때까지 WAITING 상태로 천이한 다. RUNNING 상태의 프로세스가 time ou..

Quiz 내 친구가 4지선다형 시험 문제의 답 하나를 알려주었다. 이 친구가 나에게 준 정보량은 얼마인가? 1 2 3 4 범용 컴퓨터(general-purpose computer)는 소프트웨어를 통해 여러 목적으로 사용할 수 있는 컴퓨 터를 의미한다. 범용 컴퓨터를 구현하려고 논리 회로를 만들려고 할 때 필요한 최소한의 논리 게이트 집합을 모두 고르시오. NOT, AND, OR NOT, AND, OR, NAND NOT, AND, OR, XOR NOT, AND, OR, XOR, NAND, NOR NAND Turing Machine에 대해서 틀린 설명은? Alan Turing이 제안한 현대적 컴퓨터의 원형이다. Universal Turing Machine은 현대적 컴퓨터에서 운영체제가 되었다. Turing ..

파일 시스템 컴퓨터에서 파일이나 자료를 쉽게 발견할 수 있도록, 유지 및 관리하는 방법 저장매체에는 수많은 파일이 있기 때문에, 이런 파일들을 관리하는 방법이다. file + directory file 이름을 가지는 디스크에 저장되는 bytes의 집합이다. 비휘발성의 보조기억장치에 저장된다. O/S는 다양한 저장 장치를 file이라는 동일한 논리적 단위로 볼 수 있게 한다. Operation create, read, write, reposition, delete, open, close file attribute (metadata) 파일 이름, 유형, 저장위치, 파일사이즈, 접근권한, 시간, 소유자와 같은 파일 자체의 내용이 아니라 파일을 관리하기 위한 각종 정보들 directory 파일의 메타데이터 중 ..

I/O Two Main Jobs of Compter I/O (대부분이므로 굉장히 중요하다) ex. web browsing, file editing, youtube, games, ... computing I/O Type polling(busy-waiting) reading the status register repeatedliy until the busy bit becomes clear. interrupt CPU has a wire called the interrupt-request line if CPU detects an interrupt, ISR로 점프해서 인터럽트를 처리한다. ISR의 주소는 interrupt vector table에 정의되어 있다. DMA (Direct Memory Access) u..

디스크 저장장치 비휘발성 메모리의 대용량장치인 HDD나 SDD같은 Secondary Storage에도 스케쥴링이 필요하다. 디스크 접근시간 Seek Time + retotatinal delay(track이 도는시간) + transfer time Seek Time이 가장 크다 (header를 움직이는 시간) 다중 프로그래밍 환경의 disk queue에는 많은 요청이 쌓여 있고 이 요청들을 효율적으로 스케쥴링하여 탐색시간을 줄이기 위해 디스크 스케쥴링이 필요하다 디스크 스케쥴링 알고리즘 seek time(access timie)을 최소화 하고 data transfer의 bandwidth를 최대화 하는 것이 최종 목표이다. FCFS 가장 먼저 온 것을 먼저 실행 Shortest-Seek-Time-First s..

https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 9466 3309 2348 33.080% 문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 1, 2, 3, 4, 5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 192 MB 12676 5952 4282 50.041% 문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 ..

캐시 메모리 주 기억장치에 저장된 내용의 일부를 임시로 저장해두는 기억장치 CPU와 주기억장치의 속도 차이에 의한 성능 저하(병목현상)를 방지하기 위한 방법 CPU가 이미 봤던 걸 다시 재 접근할 때, 메모리 참조 및 인출과정에 대한 비용을 줄이기 위해 캐시에 저장해둔 데이터를 활용한다. 캐시는 플리플롭 소자로 구성되어 SRAM으로 되어있어서 DRAM보바 빠른 장점을 지닌다. CPU와 기억장치의 상호작용 CPU에서 주소를 전달 → 캐시 기억장치에 명령이 존재하는지 확인 존재 → Hit 해당 명령어를 CPU로 전송 → 완료 비존재 →Miss 명령어를 갖고 주기억장치로 접근 해당 명령어를 가진 데이터 인출 해당 명령어 데이터를 캐시에 저장 해당 명령어를 CPU로 전송 → 완료 이처럼 캐시를 잘 활용한다면 비..

페이지 교체 알고리즘 페이지 부재 발생 → 새로운 페이지 할당 해야함 → 현재 할당된 페이지 중 어떤 것을 교체할 지 결정하는 방법 위 그림은 페이지 교체가 필요한 상황을 보여준다. 현재 1번 프로세스가 가리키고 있는(PC)가 B 페이지는 Page-Out되어 있는 상태고 Storage에서 B라는 페이지를 가져오려고(스와핑 시도) 하는데, 현재 physical memory에 자리가 없다(no free frame). 이 때 어떤 프로세스를 교체해야 가장 효율적으로 교체할 수 있을까? → 페이지 교체 알고리즘 필요 victim(페이지 out의 대상)을 하나 정하고, victim이 있으면 page out - page in 시킨다. 그러면 어떤 Victim을 선택해야 효율적인가? → Secondary Storag..

가상 메모리 Paging 다중 프로그래밍을 실현하기 위해서는 많은 프로세스들을 동시에 메모리에 올려두어야 한다. 가상메모리는 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법 이며, 프로그램이 물리 메모리보다 커도 된다는 주요 장점이 있다. 실행되는 코드의 전부를 물리 메모리에 존재시켜야 했고, 메모리 용량보다 큰 프로그램은 실행시킬 수 없었다. 또한, 여러 프로그램을 동시에 메모리에 올리기에는 용량의 한계와, 페이지 교체등의 성능 이슈가 발생하게 된다. 또한, 가끔만 사용되는 코드가 차지하는 메모리들을 확인할 수 있다는 점에서, 불필요하게 전체의 프로그램이 메모리에 올라와 있어야 하는게 아니라는 것을 알 수 있다. 프로그램의 일부분만 메모리에 올릴 수 있다면... 물리 메모리 ..

단순 Paging 프로세스를 연속 메모리 할당(Contiguous Memory Allocation) 을 하게 되면, 외부 단편화(External Framentation)이 발생하게 되고, 값 비싼 메모리 자원의 1/3 까지 손실될 수 있는 현상을 타파하고자 나온것이 Paging(페이징)이다. 하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 한다는 제약을 없앤다. 외부단편화와 압축(Compaction) 작업을 해소하기 위해 생긴 방법론으로, 물리 메모리(Physical Memory)는 Frame이라는 고정 크기로 분리되어 있고, 논리 메모리(프로세스가 점유하는)(Logical Memory)는 Page라 불리는 고정 크기의 블록으로 분리된다. 페이징 기법을 사용함으로써 논리 메모리는 물리 메모리에 저장..

연속 메모리 할당 Contiiguous Memory Allocation 메모리는 크게 운영체제를 위한 저장공간과, 사용자 프로세스들을 위한 공간 두 파티션으로 이루어져 있다. 운영체제는 인터럽트와 큰 상관관계가 있다. 사실 운영체제 데이터를 0번지 등의 메모리 하단에 위치시켜도 되고, 윗단에 위치시켜도 되는데, 보통은 밑단에 있다. 그 이유는 인터럽트 벡터가 주로 낮은 메모리에 위치되어 있다. 그래서 앞으로 운영체제는 메모리 주소 하단에 저장되어 있다 가정할 것이다. MMU : CPU 코어 안에 탑재 되어서 가상 주소를 실제 메모리 주소로 변환 해주는 장치 기준점의 위치가 다르더라도 offset은 같기 때문에, 더하기를 통해서 물리적 주소도 논리적 주소처럼 연속적으로 배치되게 된다. => 이게 바로 연속..

Static Linking vs Dynamic Linking 먼저 Linking(링킹)에 대해 이해를 해보자 링킹은, 프로그램을 빌드하는 과정 (즉 컴파일 과정에서 거치는 단계) 이뤄지는 과정이다. 이 전체를 크게 컴파일 과정이라고 한다. 작은 의미의 컴파일은 Compile 과정이고, 큰 의미의 컴파일은 Compiling + Linking 전 구간을 의미한다. 프로그래머들이 이해하기 쉬운 C/C++로 코드를 짜면 Source.cpp처러 소스파일이 생성된다. 그리고 이를 Build(빌드) 하게 되면 Compiling + Linking 과정을 거친 후 .exe파일을 내보내게 된다. 작은 의미의 컴파일인 Compiling만을 거치게 되면 Object File(목적 파일)인 Source.obj가 생성되게 되고 ..