독학두비니

Coding_Algorithm/백준 풀이

[Python] 13783번: Hashing 풀이

백준 풀이 13783번: Hashing 풀이 문제 Link : https://www.acmicpc.net/problem/13783 13783번: Hashing For each test case, print a single integer: the number of valid strings that have the same hash as the input string (including the input string itself), modulo 1,000,000,007 (10^9 + 7). www.acmicpc.net 문제 A string hashing function is an algorithm that turns arbitrary strings into numbers. If S is a string of..

Coding_Algorithm/Operating System

Semaphore - 코드로 이해하기

앞선 글들에서 공유메모리를 사용하기 위한 방법을 서술하였습니다. 그러나 이런 기법을 구현할 때, synchronization관련 이슈를 해결하는 것은 필수적입니다. 이런 부분들을 고려하지 않는다면 race condition등의 이슈가 발생합니다. 1. (IPC) Semaphore? 따라서 사용하는 대표적인 수단 중 하나가 semaphore입니다. 특히 이번 글에서 다룰 것은 IPC Semaphore인데, 이는 공유하는 자료 구조에 대한 통제된 접근을 위해서 사용됩니다. 주요 특징을 정리하자면, 기본적으로 semaphore은 양의 정수값을 가집니다. 자원에 프로세스가 접근할 때 마다 semaphore값은 감소합니다. semaphore값이 0이되면 semaphore값이 다시 양수가 될 때까지 프로세스의 접근..

Coding_Algorithm/Operating System

Shared Memory - 코드로 이해하기

저번 글에서는 shared memory에 대한 이론적인 부분을 보았습니다. 이번 글에서는 공유메모리에 관련한 함수들을 알아보고, 코드를 통해 직접 이해를 해보는 걸로 합시다. 1. 관련 함수 파악 우선 크게 4가지 함수가 있습니다. 하나하나 알아보도록 하겠습니다. #include #include 공유메모리 관련 1) shmget int shmget(key_t key, size_t size, int shmflg); shmget함수는 처음 공유메모리를 생성하고, shmid를 얻을 때 사용하는 함수입니다. 앞선 글에서 공유메모리는 생성만 하면 다른 과정은 할 필요가 없다고 언급했었습니다. 그 과정을 담당하는 함수입니다. 다음은 매개변수에 대한 설명입니다. key : 공유메모리를 설정할 때 사용하는 고유 key..

Coding_Algorithm/Operating System

IPC와 Shared Memory

1. IPC란? IPC는 Inter-Process Communication의 줄임말로, 프로세스 간에 데이터 및 정보를 주고받기 위한 메커니즘입니다. 특히나 OS는 프로그램을 실행시키면서 하나의 프로세스가 독박으로 모든 걸 해결할 수 없기 때문에, 통신을 위한 메커니즘은 필수적이죠. 따라서 이런 통신을 할 때 사용하는 것을 IPC라고 합니다. 다른 것들에 알아보기에 앞서, 이런 IPC는 어떠한 상황에서 필요할까요? 크게 4가지로 나누어 볼 수 있습니다. 정보 공유: 여러 사용자가 동일한 정보에 흥미를 가질 수 있음에 따라, 병행적으로 접근할 수 있는 환경 제공 계산 가속화: task를 sub task로 나누고, 병렬 처리를 통한 계산 가속화 모듈성: 시스템 기능을 변도의 프로세스 또는 스레드로 나누어 모..

Coding_Algorithm/Python

[Python 2] input() 취약점에 대하여

0. 조사하게 된 계기 CTF문제를 풀다가 엄청난걸 알아냈습니다 python2에 한해서 input함수는 eval(raw_input(prompt))로 실행된다는 사실이요. 일단 eval함수 자체가 보안측면에서 봤을 때는 위험한 함수죠. (명령어를 실행시킬 수 있는 함수인지라) 그래서 조금 더 찾아봤는데 생각보다 뭐가 많더라구요! 그래서 정리할 겸 찾아봤습니다. 1. input함수 자체에 대하여 일단 input함수 자체에 대해서 조금 탐구를 해봅시다. python2에서 이 함수의 가장 큰 특징은 "알아서 형변환"을 해준다는 점입니다. 직접 확인해봅시다 s1 = input("input()>> ") print(type(s1)) s2 = input("input()>> ") print(type(s2)) s3 = i..

Coding_Algorithm/C_C++

[C] pthread_mutex 이해하기

thread에서 가장 중요한 이슈는 race condition입니다. 동일한 메모리에 접근할 때, 그 메모리에 대해서 일관성이 유지될수 있는가?에대한 문제죠. 이런걸 해결하기 위해서 대표적으로 사용할 수 있는 함수가 pthread_mutex입니다. 오늘은 그 함수를 어떻게 사용해야하는지에 대해서 보도록 하겠습니다. 01. 문제상황 이해 우선 문제가 있는 상황을 통해서 이해를 해봅시다. 다음은 간단한 thread를 통한 코드입니다 #include #include #include int mails = 0; void* routine(){ for (int i=0;i

Coding_Algorithm/Operating System

Thread에 대하여 - C언어 기준으로

Thread에 대하여 1. Introduction 우선 Thread를 이야기 할 때 항상 거론되는 Process에 대해서 간단히 이야기해봅시다. Process에 대해서는 앞서 글을 써놨으니 참고합시다. C언어에서 가장 대표적으로 프로세스를 생성할 때 쓰는 함수는 fork()입니다. 그러나 이 과정은 매우 비쌉니다.(자원의 측면에서) 우선 프로세스라는 것 자체가 자원을 공유하지 않고 각각의 code, data 등을 가지기 때문에 기존의 process의 것들을 다 복사를 해 주어야 합니다. 이걸 해결하기 위해 COW(Copy on Write)방법같은것도 고안되었지만, 만족스러운 수준까지 성능이 향상되지는 않았습니다. 그래봤자 page table이라던가 file descriptor table같은건 복사해주어야..

Coding_Algorithm/Operating System

[OS] Scheduling Techniques Depending on Environment

Scheduling Techniques Multiple-Processor Scheduling 앞서서는 Scheduling 알고리즘 자체에 대해서 알아보았습니다. 근데 그 알고리즘들은 모두 single-processor라는 전제 하에 배웠는데, 오늘은 그 이외의 상황들에 있어서는 어떤 방식으로 스케줄링이 되어야 하는지에 대해서 알아보도록 하겠습니다. 1. Multiple-Processor Scheduling 우선 이 멀티프로세서 스케줄링의 경우에는 여러개의 비슷한(homogeneous) 프로세서들로 이루어져있습니다. 이러한 멀티프로세싱은 크게 두 가지로 나뉩니다. - Asymmetric Multiprocessing '비대칭'이라는 단어처럼 하나의 대장 프로세서가 있고, 그 친구가 스케줄링 및 자원분배를 담..

Coding_Algorithm/Operating System

[OS] Scheduling Algorithm - 2 (RR, Priority Scheduling, Multilevel Queue)

Scheduling Algorithm - 2 RR, Priority Scheduling, Multilevel Queue 1편에 이어서 Scheduling Algorithm에 대해서 계속 알아봅시다. 1. RR (Round Robin) 기본적으로 FCFS(First-Come First-Served)에서 preemptive가 추가되었다고 보면 됩니다. Round Robin 알고리즘에서 가장 중요한 점은 모든 프로세스에 기본적으로 같은 시간을 준다는 것입니다. 실제로는 보통 0~100ms 정도의 시간을 준다고 하네요. 아무튼 미리 정해놓은 시간이 다 되면, CPU를 뺐기고, queue의 뒤로 가는 식으로 진행됩니다. 대신에, 이 time unit이 너무 크면 FCFS랑 같은 격이 되고, 너무 잦은 경우에는 너..

Coding_Algorithm/Operating System

[OS] Scheduling Algorithm - 1 (FCFS, SJF)

Scheduling Algorithm - 1 FCFS, SJF 1. FCFS(First-Come, First-Served) Scheduling 가장 먼저 생각할 수 있는 알고리즘입니다. 따로 생각할 필요 없이, ready queue에 쌓이는 순서대로 바로 CPU에게 연결시켜주는 알고리즘입니다. 그냥 FIFO방식인 queue와 완벽하게 똑같습니다. 예시와 함께 봅시다. 다음과 같이 ready queue가 쌓여있다고 가정합시다. 순서는 P1, P2, P3의 순서로 쌓여있다고 가정합시다. 또한, I/O는 발생하지 않는다고 가정합니다. 그럼 이 ready queue에 대해서 실행시키는 과정을 그림으로 그려봅시다. 다음과 같이 볼 수 있겠죠? 앞서 배웠던 평가 척도를 적용시킵시다. Waiting time P1 =..

Coding_Algorithm/Operating System

[OS] Scheduling 알고리즘 평가 척도

Scheduling Criteria 스케줄링 알고리즘 평가 척도 수많은 스케줄링 알고리즘이 있지만, 그게 어떤 척도로 평가하느냐에 따라서도 많이 바뀌겠죠. 실제로 스케줄링 알고리즘은 다양한 척도로 평가를 하고 있으며, 오늘 알아 볼 계획입니다. 1. CPU의 입장에서 1) CPU Utilization 먼저 CPU 활용입니다. CPU가 존재하는 이유는 연산을 하기 위해서입니다. 그리고 CPU는 기계이기 때문에 인간적으로 쉴 시간을 챙겨줄 필요가 없이 더 많이 굴리는게 무조건 효율적입니다. 따라서 이 CPU를 얼마나 idle상태가 아닌, busy상태로 두었는지를 보는게 하나의 평가척도입니다. 물론 I/O bound program이라던가, I/O busy program같은 경우들에는 어쩔 수 없이 CPU가 놀..

Coding_Algorithm/Operating System

[OS] Nonpreemptive Scheduling vs. Preemptive Scheduling

Nonpreemptive Scheduling vs. Preemptive Scheduling 선점 / 비선점 스케줄링 1. CPU Scheduling이 필요한 경우들 우선 CPU Scheduling이 필요한 경우는 최대한 CPU의 뽕을 뽑아먹기 위해서입니다. 즉, 프로세스들에게 적절하게 CPU를 배분해서 효율적으로 작업을 처리하기 위함이죠. 그래서 그 경우에는 크게 4가지로 나뉩니다. 1. running -> waiting : I/O 발생 2. running -> ready : timeout, interrupt 3. waiting -> ready : I/O or event 끝 4. Terminates : exit +) ready -> running : Scheduler dispatch 뒤에서 더 자세히 보..