Computer Sci.

이번 포스팅에서는 메모리 관리에 대해서 정리해 보고자 한다. 참고로 내용이 많으므로 두 번에 나누어서 정리한다. 컴퓨터가 널리 보급되면서, 범용 컴퓨터 시스템의 목적은 CPU의 활용률을 극대화 하는 것으로 나아갔다. 사용자들에게 빠른 응답을 제공하기 위해서 보다 많은 프로그램을 메모리에 올려서 실행(multi-programming) 시키게 되었고, 여러 프로그램을 동시에 실행시키기 위한 스케줄링 기법이 등장하게 되었다. 이와 같이 여러 프로그램이 동시에 메모리에 적재되어 실행되면서, 메모리를 공유할 필요가 생겼다. 컴퓨터의 메모리는 한정되었는데, 실행하는 프로그램이 많아지면 메모리 요구량이 증가했기 때문이다. 컴퓨터에서 작동하는 응용 프로그램은 프로그래밍 언어로 만들며, 보통은 컴파일러를 사용하여 작성된..

오늘은 백준 1865번 웜홀 문제를 풀어보려고 한다. https://www.acmicpc.net/problem/1865 1865번: 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다. 시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 www.acmicpc.net 이 문제는 개인적으로 정말 많이 틀리고 나서 해결했던 문제이다. 그래서 더욱 꼼꼼하게 문..

지난번 포스팅 동기화 Part1에 이어서 데드락과 동기화의 고전적 문제들에 대해서 정리를 해 보려고 한다. 데드락(교착상태, Deadlock) 데드락은 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만을 기다리며 작업을 더이상 수행하지 않는 상태를 의미한다. 교착상태가 발생하는 조건은 여러가지가 있는데 아래와 같다. 상호 배제(mutual exclusion): 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다. 배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없다. 따라서 배타적인 자원을 사용하면 교착 상태가 발생한다. 비선점(non-preemption): 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선..

오늘 살펴볼 문제는 백준 1655번 문제이다. https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다. www.acmicpc.net 나는 처음에 이 문제를 정말 단순하게 직관적으로 접근했었다. N개의 입력값을 받아서 하나씩 ArrayList에 받고 그 때마다 정렬을 한 뒤 i/2 번째 원소를 찾아서 출력하면 되지 않나? 라고 접근해서 풀었고 시간초과가 나왔다. 이는 당연한게 시간 복잡도가 O(N*N*logN)..

오늘은 동기화를 공부한 내용에 대해서 정리 해 보려고 한다. 프로세스 간 통신 프로세스는 시스템 내에서 독립적으로 실행 되기도 하고, 데이터를 주고받으며 협업하기도 한다. 프로세스가 다른 프로세스와 데이터를 주고받는 프로세스간 통신(IPC)에는 같은 컴퓨터 내에 있는 프로세스 뿐만 아니라 네트워크로 연결된 다른 컴퓨터에 있는 프로세스와의 통신도 포함된다. 프로세스간 통신에는 크게 세 가지가 있다. 프로세스 내부 데이터 통신 하나의 프로세스 내에 2개 이상의 스레드가 존재하는 경우의 통신이다. 프로세스 내부의 스레드는 전역 변수나 파일을 이용하여 데이터를 주고받는다. 전역 변수를 이용한 통신 : 전역 변수를 이용한 통신은 공동으로 관리하는 메모리를 사용하여 데이터를 주고 받는 것이다. 데이터를 보내는 쪽에..

이번에는 쓰레드에 대해서 공부한 내용을 정리해 보려고 한다. 지난 포스팅에서 프로세스에 대해서 정리를 한 적이 있었다. 프로세스는 스케줄링의 단위로서 실행 단위(Execution unit)이다. 또한 소유하고 있는 자원에 대한 보호(Protection domain) 개념을 가지고 있기도 하다. 지금까지는 하나의 실행 흐름을 가지고 실행중인 프로그램에 대해서만 다루었기 때문에 프로세스만 가지고 설명이 가능했다. 하지만 프로세스의 처리 속도가 점점 빨라져야 할 필요성에 맞추어, 하나의 프로세스가 수행해야 할 여러 작업들을 나누어 수행할 수 있는 설계가 필요해졌고, 이에 생겨난 개념이 쓰레드(Thread)이다. 쓰레드는 프로세스 내의 실행 흐름이다. 이 역시 실행 단위(Execution unit)으로 볼 수 ..

오랜만에 운영체제 공부를 다시 시작하게 되었다. 이번에는 CPU 스케줄링에 대해 정리해 보려고 한다. CPU 스케줄링이란? CPU 스케줄링은 프로세스가 작업을 수행할 때, 언제 어떤 프로세스에 CPU를 할당할지를 결정하는 작업이다. 기본적으로 멀티프로그래밍과 시분할에 기반한다. 메모리 내에 실행 준비된 프로세스 중 하나를 선택하여 CPU를 할당한다. 한정된 CPU 및 I/O장치 등의 시스템 자원을 가지고 최고의 성능을 내야 하고, 따라서 자원을 언제 어떻게 할당할지를 결정하는 문제는 정말 중요하다. CPU 스케줄링의 목표는 CPU를 최대로 활용하는 것, 즉 idle을 최소화 하는 것이다. 참고로 이 때 time quantum은 커널이 CPU를 쓰는 시간에 포함하지 않는다. CPU 스케줄링의 결정은 다음 ..

오늘은 프로세스에 대해서 공부해 본다. 프로그램과 프로세스 소스코드 (.c file) : 프로그램이 수행하고자 하는 작업이 프로그래밍 언어로 표현 컴파일러 (compiler) : 사람이 이해할 수 있는 프로그래밍 언어로 작성된 소스코드를 컴퓨터(CPU)가 이해할 수 있는 기계어로 표현된 오브젝트 파일로 변환 오브젝트 (.o file) : 컴퓨터가 이해할 수 있는 기계어로 구성된 파일. 자체로는 수행이 이루어지지 못함. 프로세스로 변환되기 위한 정보가 삽입되어야 함. 상대 주소로 표현 링커 (linker) : 관련된 여러 오브젝트 파일들과 라이브러리들을 연결하여 메모리로 로드될 수 있는 하나의 실행파일만 작성 실행파일 (.exe) : 특정한 환경(OS)에서 수행될 수 있는 파일. 프로세스로의 변환을 위한 ..