개요 MLFQ 는 짧은 작업을 먼저 실행시켜 반환 시간을 최적화 하고 대화형 사용자에게 응답이 빠른 시스템이라는 느낌을 주기 위해 고안된 알고리즘임 SJF, STCF 와 같은 알고리즘은 작업시간의 실행 시간 정보를 필요로 하지만, 운영체제는 이 시간을 알 수가 없음 RR 과 같은 알고리즘은 응답 시간을 단축시키지만 반환 시간은 최악임 핵심: 정보 없이 스케줄 하는 방법은 무엇인가. 작업의 실행 시간에 대한 선행 정보 없이 대화형 작업의 응답 시간을 최소화 할 수 있는 방법은? 기본 규칙 여러개의 큐로 구성되며 각각 다른 우선순위(priority level) 가 배정된다 실행 준비가 된 프로세스는 이중 하나의 큐에 존재한다. 높은 우선순위 큐에 존재하는 작업이 선택된다. 큐에는 둘 이상의 작업이 존재할 수..
분류 전체보기
워크로드에 대한 가정 프로세스가 동작하는 일련의 행위를 워크로드라고 함. 적절한 워크로드의 선정은 스케줄링 정책 개발에 매우 중요한 부분 스케줄링의 평가 항목 스케줄링 정책의 평가를 위해 스케줄링 평가 항목(scheduling metric) 을 결정해야 함 반환 시간(turnaround time) 작접이 완료된 시간 - 작업이 도착한 시간 선입선출 (FIFO) 장점 단순함, 구현하기 쉬움 단점 CPU를 많이 필요로 하지 않는 프로세스들이, CPU를 오랫동안 사용하는 프로세스가 끝나기를 기다리는 현상이 발생함 (convey effect) 최단 작업 우선 (SJF) 장점 convey effect 문제를 해결함 모든 작업이 동시에 도착한다면 SJF 가 최적(optimal) 의 스케줄링 알고리즘임 단점 모든 작..
개요 운영체제는 여러 작업들이 동시에 실행되는 것 처럼 보이도록 물리적인 CPU를 공유함 (시분할방식) 이러한 가상화 기법을 구현하기 위해서 성능저하, 제어 문제를 해결해야 함 제어를 유지하며 CPU 를 가상화 하는 방법 운영체제는 효율적인 방식으로 CPU를 가상화하지만 시스템에 대한 제어를 잃지는 않음 제한적 직접 실행 프로그램을 빠르게 실행하기 위해 제한적 직접 실행 기법 개발 프로세스 목록에 추가 → 프로그램 메모리 할당, 탑재 → 스택 셋 → main() 실행 운영체제가 원치않은 일을 하지 않는다는 것을 보장할 수 없음 프로그램 실행에 제한을 두지 않으면 운영체제는 어떠한 것도 제어 할 수 없음, 단순 라이브러리일 뿐임. 문제점 1: 제한된 연산 직접 실행의 장점은 빠르게 실행됨, 그러나 특수한 ..
프로세스 생성 API UNIX는 프로세스를 생성하기 위하여 fork() 와 exec() 시스템 콜을 사용함 wait() 은 프로세스가 자신이 생성한 프로세스가 종료되기를 기다리기 원할 때 사용함 프로세스를 생성하고 제어하려면 운영체제가 어떤 인터페이스를 제공해야하는가? 유용성, 편리성, 성능을 위해서는 어떻게 인터페이스를 설계해야 하는가? fork() 시스템 콜 시스템 콜 중에서 가장 이해하기 힘든 시스템 콜 fork() 시스템 콜의 반환 값은 자식, 부모가 서로 다름 자식 == 0 부모 > 0 실패 < 0 부모와 자식 프로세스간의 실행 순서는 보장하지 못함 CPU 스케줄러는 실행할 프로세스를 선택함, 스케줄러의 동작은 일반적으로 상당히 복잡하고 상황에 따라 다른 선택이 이루어지기 때문에 어느 프로세스가..
프로세스 실행 중인 프로그램 프로그램은 디스크 상에 존재하며 실행을 위한 명령어와 정적 데이터의 묶음 CPU 가 여러 개 존재한다는 환상을 어떻게 제공하는가 운영체제는 CPU 를 가상화하여 프로그램이 동시에 실행 되는 것 처럼 보이게 함 시분할 (time sharing) 이라 불리는 기법을 사용해 원하는 수 만큼의 프로세스를 동시에 실행할 수 있게 함 CPU를 공유하기 때문에 각 프로세스의 성능은 낮아짐 Context switching CPU 에서 프로그램 실행을 잠시 중단하고 다른 프로그램을 실행하는 것 프로세스의 개념 실행중인 프로그램을 프로세스라 함 프로세스의 구성요소를 이해하기 위해 하드웨어 상태를 알아야 함 하드웨어 상태 중 가장 중요한 요소는 메모리 명령어, 실행 프로그램이 읽고 쓰는 데이터는..
개요 운영체제는 자원 관리자로서 CPU, 메모리, 및 디스크 같은 시스템의 자원을 효율적으로 관리하는 역할을 지니고 있음 보통 응용 프로그램이 사용가능한 수백 개의 시스템 콜을 제공함 운영체제는 어떻게 자원을 가상화하는가? 가상화 효과를 얻기 위해 운영체제가 구현하는 기법과 정책은 무엇인가. 운영체제는 이들을 어떻게 효과적으로 구현하는가. CPU 가상화 여러개의 CPU가 존재하는 것 처럼 변환하여 동시에 많은 수의 프로그램을 실행시키는 것 프로그램에서 사용하는 명령을 운영체제에 알려주기 위해서는 API 가 필요함 메모리 가상화 (Virtualizing memory) 각 프로그램이 물리 메모리를 다른 프로그램과 공유하는 것이 아니라 각자 메모리를 가지고 있는 것 처럼 보이게 하는 것 각 프로세스는 자신만의..
https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 풀이시간 설계: 160분 구현: 20분 문제 종류 스택, 자료구조 풀이 방법 이 문제의 요구사항은 다음과 같이 정의된다. 1. 두개의 인덱스를 결정한다. (A,B) 2. 두개의 인덱스 사이에 있는 값들은 arr[A] > val and arr[B] > val 을 동시에 만족해야한다. 예를들어 배열이 4,2,3,5 와 같은 형태의 경우 가능한 쌍은 아래와 같다 (4,2),(4,..
https://www.codetree.ai/training-field/frequent-problems/problems/tree-tycoon/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제종류 dx dy, simulation 풀이시간 설계: 3분 구현:26분 풀이방법 까다로운 요구사항은 없는 문제, 단지 영양제를 투입할때 나무의 성장은 동시에 일어난다는 조건에 주의해야함 코드 # 20:28 # → ↗ ↑ ↖ ← ↙ ↓ ↘ dx, dy = [0, -1, -1, -1, 0, 1, 1, 1], [1..
