전체 글 (291) 썸네일형 리스트형 2.3 알고리즘의 설계 2.3 알고리즘의 설계 분할정복 분할 : 현재 문제를 같은 문제를 다루는 다수의 부분 문제로 분할한다. 정복 : 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 충분히 작으면 직접적인 방법으로 푼다. 결합 : 부분 문제의 해를 결합하여 원래 문제의 해가 되도록 만든다. 병합정렬 분할정복 시간복잡도 연습문제 2.3-1 2.3-2 def merge_without_sentinels(A, p, q, r): nL = q - p + 1 # Length of A[p...q] nR = r - q # Length of A[q+1...r] L = [0] * nL # Initialize arrays L and R R = [0] * nR for i in range(nL): # Copy A[p...q] into L.. 스케줄링: 멀티 레벨 피드백 큐 스케줄링: 멀티 레벨 피드백 큐 MLFQ, Multi-level Feedback Queue 여러 개의 큐로 구성되며, 각각 다른 우선순위(priority level)가 배정된다. 높은 우선순위를 가진 작업(큐)가 선택된다. 📌 배운 것 MLFQ가 해결하려는 문제 짧은 작업을 먼저 실행시켜 반환시간을 최적화 대화형 사용자(화면 앞에 앉아 바로면서 프로세스 종료를 기다리는 사용자)에게 응답이 빠른 시스템이라는 느낌을 주고 싶음. 즉, 응답시간을 최적화 MLFQ 규칙 규칙 1 : Priority(A) > Priority(B)이면, A가 실행된다.(B는 실행되지 않는다.) 규칙 2 : Priority(A) = Priority(B)이면, A와 B는 RR 방식으로 실행된다. 규칙 3 : 작업이 시스템에 진입하면, .. 스케줄링: 개요 스케줄링: 개요 컴퓨터 시스템 개발 이전에 생산 관리 분야에서 개발되었으며 컴퓨터에 적용된 스케줄링 원칙! 📌 배운 것 워크로드(workload) 프로세스들이 실행되는 상황 워크로드를 잘 알수록 그에 맞게 정책을 만들 수 있을 있다. 핵심 가정 모든 작업은 같은 시간 동안 실행된다. 모든 작업은 동시에 도착한다. 각 작업은 시작되면 완료될 때까지 실행된다. 모든 작업은 CPU만 사용한다.(즉, 입출력을 수행하지 않는다.) 각 작업의 실행 시간은 사전에 알려져 있다. 스케줄링 평가 항목(평가 기준) 반환시간(Trunaround time) = 완료시간 - 도착 시간 반환시간 ⇔ 성능 지표 하지만, 성능을 높이고자 몇몇 작업의 실행을 중지하면 공정성(fairness)이 떨어진다. 📌 기본접근법 비선점(non-.. 이전 1 ··· 5 6 7 8 9 10 11 ··· 97 다음
