본문 바로가기
반응형

분류 전체보기313

페이지 교체 알고리즘 주기억장치 메모리 공간의 한계를 프로세스 전체가 메모리 내에 올라오지 않더라고 실행이 가능하도록 하는 가상기억장치 기법을 통해 해결한다고 하였다. ​가상기억장치는 주로 페이지 단위로 관리한다. 가상기억장치는 프로그램 전체를 메모리에 적재하지 않는 대신, 초기에 필요한 것들만 미리 메모리에 할당하는 요구 페이징(Demand Paging)이라는 전략을 주로 사용한다.​ 요구 페이징 전략을 통해 몇 개의 페이지가 메모리에 할당되고 프로그램을 실행한다고 가정하자. 프로그램 실행 시 필요한 페이지가 요구 페이징 전략을 통해 할당되지 않았을 수도 있다. 즉, 필요로 하는 페이지가 주기억장치에 없는 페이지 부재(Page Fault)가 발생할 수 있다. ​페이지 부재가 발생하게 되면, 원하는 페이지를 보조기억장치에서 .. 2021. 7. 7.
백준 5213 : 과외맨 https://www.acmicpc.net/problem/5213 5213번: 과외맨 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500) 다음 줄부터 N*N-N/2줄(/는 정수 나눗셈이다)에는 두 양의 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ 6, 1 ≤ i ≤ N * N - N / 2) 타일 i의 왼쪽에 쓰여 있는 숫자는 Ai, 오른 www.acmicpc.net [ 문제풀이 ] 지문이 굉장히 길어서 이해하는데 조금 시간이 걸렸지만 결국 1번 타일부터 시작하여 각 타일들을 통해 이동할 수 있는 타일 중 번호가 가장 큰 타일의 최소 경로를 찾아주면 되는 문제이다. 이동할 수 있는 타일 간의 거리는 1이기 때문에 BFS를 수행해주면 된다. 다만, 각 타일마다 이동할 수 있는 경로를 어떻게 설정해줄 .. 2021. 7. 7.
백준 2662 : 기업투자 https://www.acmicpc.net/problem/2662 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net [ 문제풀이 ] 배낭 문제와 거의 비슷한 유형으로 dp를 사용하여 해결해주면 된다. 먼저 다음과 같이 dp 테이블을 정의하자. dp[i][j] : 1~j번째 기업까지 i원을 사용했을 경우 최대 이익구하고자 하는 값 그렇다면 점화식은 어떻게 될까? 잘 생각해보면 현재 기업에 i원을 투자하기 위해서는 이전 i-1기업까지 투자한 금액이 N-i원을 초과해서는 안된다. 그래야 현재 기업에 i원만큼 투자할 수 있기 .. 2021. 7. 6.
가상기억장치 할당 기법 이전 글에서 주기억장치에 프로그램을 할당하는 방법을 공부하였다. 하지만 주기억장치의 메모리 공간은 제한적이기 때문에 결국 메모리의 크기보다 많은 프로그램들이 올라갈 수 없다. 이를 해결하기 위해 나온 것이 바로 가상기억장치이다. 가상기억장치란 주기억장치 안의 프로그램 양이 많아질 때, 보조기억장치(하드디스크)의 일부를 주기억장치처럼 사용하는 것으로, 용량이 작은 주기억장치를 마치 큰 용량을 가진 것처럼 사용하는 기법이다. ​즉, 프로그램을 여러 개의 작은 블록 단위로 나누어서 가상기억장치에 보관해 놓고, 프로그램 실행 시 요구되는 블록만 주기억장치에 불연속적으로 할당하여 처리하는 방식이다. ​ 가상기억장치에 저장된 프로그램을 실행하기 위해선 가상기억장치의 주소를 주기억장치의 주소로 변환하는 작업이 필요하.. 2021. 7. 6.
주기억장치 할당 기법 이전 글을 통해 한정된 주기억장치의 메모리 공간을 효율적으로 사용하기 위해 반입, 배치, 교체 전략을 활용한다고 공부하였다. 전략 기법을 통해 최종적인 과정은 프로그램을 주기억장치 메모리 공간에 할당하는 것이다. 이 또한 마찬가지로 무턱대고 아무렇게나 메모리에 프로그램을 할당한다면 굉장히 비효율적일 것이다. ​즉, 주기억장치 할당 기법은 프로그램이나 데이터를 실행시키기 위해 주기억장치에 어떻게(How) 할당할 것인지에 대한 방법이며, 연속 할당 기법과 분산 할당 기법으로 분류할 수 있다. 이번 글에서는 주기억장치에 프로그램을 할당하는 방법 중 연속 할당 기법에 대해서 알아보자. 먼저 단일 분할 할당 기법이다. 단일 분할 할당 기법은 주기억장치를 운영체제 영역과 사용자 영역으로 나누어 한순간에는 오직 한 .. 2021. 7. 6.
메모리 관리 전략 멀티 프로세스 환경에서 성능을 향상시키기 위해서는 주 메모리에 여러 개의 프로세스가 올라와서 서로 공유하도록 해야 한다. 이때 운영체제가 어떤 프로세스를 메모리에 올릴 것인지를 판단한다. ​우선 메모리 계층 구조를 간단하게 살펴보고 넘어가자. 메모리 계층 구조는 다음과 같이 레지스터, 캐시 기억장치, 주기억장치, 보조기억장치로 이루어져 있다. 여기서 주의 깊게 봐야 할 메모리는 보조기억장치와 주기억장치이다. 각각 하드디스크, RAM을 생각하면 쉽다. ​과거의 프로그램들은 메모리 크기가 작았기 때문에 주기억장치에 모두 올릴 수 있었지만 현대의 프로그램들은 메모리가 굉장히 크기 때문에 모든 프로그램을 주기억장치에 올릴 수 없다. 주기억장치의 공간은 제한적이기 때문이다. 따라서 제한된 공간에 적절한 프로그램을.. 2021. 7. 6.
교착상태(Deadlock) 다중 프로그래밍 환경에서는 여러 프로세스들이 한정된 자원을 사용하려고 서로 경쟁할 수 있다. 한 프로세스가 자원을 요청했을 때, 자원을 사용할 수 없는 상황이 발생할 수 있고, 그 경우 프로세스는 대기 상태로 들어간다. 이처럼 대기 중인 프로세스들이 대기 상태를 변경할 수 없는 상황을 교착상태라고 한다. ​즉, 교착상태는 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 의미한다. ​ 교착상태가 발생하기 위해서는 다음 네 가지 조건이 모두 충족되어야 한다. 현재의 대부분의 운영체제들은 교착상태를 막을 수 없다. 따라서 교착상태가 발생했을 때 이를 처리하는 3가지 방법이 존재한다. 그렇다면 교착상태를 처리하는 방법들에 대해서 간단하게 알.. 2021. 7. 6.
Blocking / Non-Blocking & Synchronous / Asynchronous 공부를 하다가 Blocking / Non-Blocking & Synchronous / Asynchronous 내용을 접하게 되었다. 각각 대충 어떤 의미인지 가볍게 알고 있었으며 Blocking-Synchronous, Non-Blokcing-Asynchronous가 비슷한 개념?으로 알고 있었다. 하지만 당연하게도 다른 개념이니 용어를 구분하였을 것이다. 따라서 이번 기회에 한 번 공부 및 정리해보려고 한다. ​ 우선 각 용어들의 개념과 차이에 대해서 이해하고 넘어가자. Blokcing / Non-Blocking과 Synchronous / Asynchronous는 관심사 관점으로 구분할 수 있다. 관심사 관점뿐만 아니라 입장을 통해서도 구분할 수 있다. 그리고 Async와 NonBlocking은 동작 관.. 2021. 7. 6.
프로세스 동기화(Process Synchronization)(2) 이전 글에서 임계구역 문제를 해결하기 위한 동기화 하드웨어 방법은 복잡할 뿐 아니라 응용 프로그래머가 사용할 수 없는 방법이라고 하였다. 이를 위해 운영체제 설계자들은 소프트웨어 도구들을 개발하였는데 그중 가장 간단한 도구가 바로 mutex 락이다. ​mutex 락 역시 lock을 사용하는 방법으로 프로세스는 임계구역에 들어가기 전에 반드시 lock을 획득해야 하고 임계구역을 빠져나올 때 lock을 반환해야 한다. mutex 락은 available이라는 변수로 락의 가용 여부를 표시한다. ​ mutex 락을 사용하는 프로세스의 구조는 다음과 같다. acquire() 메서드를 통해 lock을 획득하고 release() 메서드를 통해 lock을 반환한다. do { acquire() //lock을 획득 --c.. 2021. 7. 5.
반응형

티스토리툴바