본문 바로가기

분류 전체보기103

[운영체제 OS] Synchronization Race Condition 여러 프로세스가 동기화 없이 동시에 공유 자원에 접근하여 결과값에 영향을 줄 수 있는 상태 자료의 일관성 문제가 발생 예시 ) 남자친구, 여자친구가 긱자 데이트 통장에서 동시에 돈을 인출하는 상황 Critical Section Problem (임계 영역 문제) Critical Section은 공유 데이터를 접근하는 코드 부분을 의미 Critical Section Problem은 한 프로세스가 처리되고 있는 도중 다른 프로세스가 접근하여 발생하는 동기화 문제 Critical Section Problem 해결하기 위한 3가지 기본조건 Mutual Exclusion (상호 배제) : 어떤 프로세스가 Critical Section부분을 수행 중이면, 다른 프로세스는 Critical S.. 2021. 8. 23.
[백준] 5430번 : AC (C++) https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 자체는 쉬운것 같았다. 그냥 구현이겠거니 vector를 사용해서 reverse()함수를 통한 뒤집기를 해보니.... 시간초과가 떠버렸다. (이렇게 쉽게 풀릴리가 없지...) 다음으로 시도한 방식은 자료구조 덱(deque)을 사용하는 것이다. R이 나올때마다 매번 reverse를 하면 엄청나게 비효율적일 것이므로, 정방향인지 역방향인지 상태를 나타내는 bool형 dir변수를 두었다. dir가 true면 정방향이므로, D가 나올때 pop_front().. 2021. 8. 23.
[백준] 1041번 : 주사위 (C++) https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 주사위의 6개의 눈과 N을 입력받으면, 해당 주사위로 이루어진 N×N×N크기의 정육면체의 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 문제이다. 처음에는 3면이 보이는 주사위 갯수, 2면이 보이는 주사위 갯수, 1면이 보이는 주사위 갯수를 구하고, 각각 주사위의 3면,2면,1면의 최소합을 구해 곱하면 되는줄 알았다. 운이 좋게도, 테스트 케이스는 다 통과했지만 "틀렸.. 2021. 8. 22.
[운영체제 OS] Process vs Thread 1. Process vs Thread Process 실행중인 프로그램으로 운영체제로 부터 CPU 할당을 받을 수 있는것 프로세스는 각자 독립된 공간(Code, Data, Heap, Stack)을 가진다. 프로세스 간 직접적인 통신이 불가하며, IPC(Inter-Process Communication) 방식을 통해서만 가능하다. Message Passing : 운영체제(커널)의 도움을 받아 프로세스간 통신. 커널이 알아서 동기를 맞춰주지만, 오버헤드 높음. Shared Memory : 공유 메모리 공간을 통해 프로세스간 통신. 동기를 직접 맞춰줘야하지만 오버헤드 낮음. 프로세스는 기본적으로 1개 이상의 스레드(메인스레드)를 가진다. Thread 프로세스 내에서 실행되는 여러 흐름의 단위, 경랑 프로세스 스.. 2021. 8. 21.
[운영체제 OS] CPU Scheduling Scheduling Criteria 스케줄링의 성능평가에는 크게 5가지 지표가 사용된다. 이 지표들은 앞선 Process 글에서 설명했던 CPU-bound Process와 I/O-bound Process관점으로 나누어볼 수 있다. 1. CPU 사용률 : 전체시간 중 CPU가 놀지않고 일한 시간 2. 처리량 : 단위시간당 처리량 3. 소요시간 : 프로세스가 다 수행되고 도착하는데까지 걸리는 시간 4. 대기시간 : Ready Queue에서 기다리는 시간 5. 응답시간 : 중간중간 사용자에게 응답주는 시간 시간보다 처리량이 중요한 CPU-bound Process에서는 1,2번을 maximize하는 방향으로, 사용자와 interactive한 I/O-bound Process에서는 3,4,5번을 minimize하는.. 2021. 8. 21.
[백준] 1793번:타일링 (C++) https://www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. www.acmicpc.net 이 문제 점화식은 간단하다. 2x1칸이 오른쪽에 추가 되었을때, 새롭게 타일을 채우는 방법은 총 3가지 케이스이다. 추가 후 현재 타일이 2xN 이라고 할때, 1. 기존 2x(N-1) 타일 + 1개의 2x1 타일 2. 기존 2x(N-2) 타일 + 2개의 1x2 타일 3. 기존 2x(N-2) 타일 + 1개의 2X2 타일 즉, dp[N]가 2 X N 타일을 채우는 방법의 수라고 할때 점화식은 다음과 같다. dp[i] = dp[i-1] + dp[i-2] + dp[.. 2021. 8. 21.

티스토리툴바