[학습일기] 디자인 패턴 관련 학습 정리 - 실습 관련

개요스프링 입문 강의의 예제 코드 강의를 보고 따라해보면서 모듈화를 하는 전략에 대해서 고민하고 어느 정도 정해진 루틴을 생각해보았습니다.기본적으로 이 정해진 루틴으로 초안을 작성하고 나서 상황에 맞는 리팩토링하는 방법으로 빠르게 설계 및 구현을 시도해볼 계획입니다. 루틴먼저 구현하고자 하는 기능을 책임으로 나눕니다.책임을 더 작은 책임들로 분할합니다.이 때 책임의 분할에 도움이 되는 전략으로는 다음을 사용하였습니다.책임을 수행하기 위해 필요한 정보에 따라서 분할하였습니다.예를 들면 어떤 정보는 객체를 생성할 때만 필요하고 사용할 때는 필요하지 않을 수 있습니다.이 이유로 저번 블로그 글에서 디자인 패턴을 관심사의 분리 측면에서 관찰하게 되었습니다.같은 맥락에서 사용되고 변하는 정보의 경우 맥락을 객체로 캡슐화하였습니다.다른 맥락에서 사용되는 정보의 경우, 다른 객체에서 정보를 제공할 수 있도록 책임을 분할하거나, 분할이 어려운 경우 고차함수를 이용해서 책임을 따로따로 주입할 수 있도록 하였습니다.지금 생각났는데 일단 구현하고 나서 리팩토링하는 것도 시도해볼 만한 전략인 것 같습니다.예시많이 많이 부끄럽습니다만 해당 커밋에 코멘트 형식으로 사고 과정을 달아놓았습니다.원래 공개할 계획이 없던 리포지토리다 보니 깔끔하지 못한 부분이 있습니다. 죄송합니다ㅠㅠ앞으로는 비공개 리포도 깔끔하게 정리해야겠습니다.

[학습일기] 디자인 패턴 관련 학습 정리 - 이론 관련

설계 시간 문제설계와 구현의 밸런스 중에서 설계에 치중해 있었던 것 같습니다.문제: 저는 설계할 때 생각과 고민이 너무 너무 많습니다.시도한 해결 방안오히려 설계를 열심히 파서 고민을 해결하고 제 나름대로의 설계 방법론이 생기면 빠르게 설계를 끝내고 구현으로 넘어갈 수 있지 않을까 생각했습니다."오브젝트" 책 보기"오브젝트"를 도서관에서 빌렸지만 훑어만 보고 깊게 읽어보지 못한 상태로 반납했습니다. 훑어보기밖에 하지 못했지만 고민을 해결해준 부분, 모르는 것을 알려준 부분, 생각만 하던 것을 확인해준 부분들을 많이 확인할 수 있었습니다. 책임을 어떻게 배분해야 할지에 대해서 고민거리를 던져주었습니다. 취업 시 구매 목록 1순위에 있습니다. 소장하고 있다가 필요할 때마다 발췌독을 해야겠다고 생각했습니다.디자인 패턴들 확인refactoring.guru 사이트에 나온 디자인 패턴 중 몇 개를 관심사의 분리 측면에서 개인적으로 재해석해보았습니다.생성과 관련된 디자인 패턴: 객체의 생성 // 객체의 사용 분리, 객체의 생성을 심도있게 다루기객체의 생성과 객체의 사용은 대부분 필요로 하는 정보가 다릅니다. 따라서 객체의 생성과 사용을 분리해서 생각하는 것, 생성과 관련해서 구체적인 디자인 패턴이 나오는 것이 이상한 일이 아닙니다.객체의 생성: 객체의 구체적인 구현체의 클래스 및 생성자 파라미터 등등객체의 사용: 객체 자체의 인터페이스구체적인 패턴들은 필요할 때마다 간간이 보기행동과 관련된 디자인 패턴: 책임을 "누구"에게 할당해야 하는지와 관련이 큼 중재자: M*N 형태의 관계를 M*1 형태 + 1*N 형태로 분리중재자 패턴에 들어맞지는 않더라도 이런 식의 분리 전략이 유용한 경우를 생각할 수 있었습니다.커맨드, 옵서버: 책임의 "언제"와 "무엇"을 분리커맨드 패턴: 언제 무엇을 할지가 정적으로 미리 고정되어 있는 경우옵서버 패턴: 언제 무엇을 할지가 동적으로 추가되거나 제거될 수 있는 경우전략: 책임의 "무엇"과 "어떻게"를 분리반복자: 순회 + 전략 + 역 IoC전략: 순회할 때 각 원소를 가지고 어떻게 할 것인지에 대한 전략구현하면 Array.prototype.forEach와 같은 메소드가 됨역 IoC: 많은 언어에서 제어를 뺏어가는 forEach 메소드보다 제어를 클라이언트 코드에게 넘기는 Iterator가 범용성 측면에서 유리예: 두 Iterator를 번갈아가며 순회하는 Iterator 구현 비지터, 상태: M * N 형태의 관계에서 한쪽을 고정시키고 다른 쪽을 유연하게 설정하는 기법Expression Problem과 비슷하게 때로는 한 요소는 M가지 중 하나, 다른 요소는 N가지 중 하나에 의존해서 실제로 양쪽 요소가 모두 변할 때 구현체들의 종류는 MN가지이고 두 요소 모두에 대해서 깔끔하게 확장이 안 되는 경우가 존재합니다. 한쪽 축을 고정시켜 희생시키고 다른 쪽을 유연하게 만드는 기법입니다.비지터는 Sum Type으로 나타낼 수 있는 정보를 전달하는 맥락으로 사용됩니다. Sum Type의 각 항들이 고정되고, Sum Type을 사용하는 쪽이 변경에 용이합니다. DDD 책 보기아직 DDD에 대해서 깊게 공부할 시기는 아니라고 생각하지만, 왜 Controller, Service, Repository의 설계가 아닌 다른 설계는 없는지 고민하느라 시간을 많이 허비하고 있었고, 이를 해소하기 위해 DDD 책이 필요하다고 판단하였습니다. 당연하게도 책의 모든 부분을 깊게 이해하지 못했지만 다행히도 의문을 해소할 수 있었고 더이상의 시간 소모를 막을 수 있었습니다. 구체적으로 아래와 같은 의문들을 가졌습니다.(Entity의 생명주기가 request마다 새로 생성되는 개념적 모델을 가진 상태였습니다.) 'Entity에게 save 메소드를 부여하면 Repository의 도움 없이 Entity 객체가 자율적으로 저장될 수 있지 않을까?'보통 해결하고자 하는 도메인에서 Entity는 데이터베이스에 영속적으로 저장된 채로 request/response 한 주기보다 긴 생명주기를 가진다고 이해했습니다.'Domain Layer에서는 Entity를 인터페이스로 설계하고 Data Access Layer에서는 이 인터페이스의 구현체를 만들면 Domain에서 메시지만 주고받을테니 더 객체지향적인 설계가 가능하지 않을까?'이 의문을 해결해준 링크이자 DDD 책을 보게 된 원인입니다.다음의 4단 의문'HTTP 요청 데이터도 데이터이고, 관계형 데이터베이스에서 저장되는 것도 관계형 데이터이고, 반환하는 것도 HTTP 응답 데이터인데, 왜 중간에 객체를 꼭 거쳐야 할까?''관계형 데이터를 불러오는 수단으로 객체를 거치는 것이 아니라 객체를 저장하기 위해서 관계형 데이터베이스를 사용하나 보다.''왜 도메인을 나타내는데 객체를 사용했을까?''Entity를 나타내는데 객체가 효과적이어서 그렇지 않을까?'비고제가 스프링 강의를 듣기 직전에 데이터베이스 강의를 들어서 이 의문이 정말 오랫동안 남았습니다.책의 저자께서는 제가 기억하기로는 다음과 같은 취지의 말씀을 하셨습니다. "도메인에 따라 절차지향적 프로그래밍, 함수형 프로그래밍, 논리 프로그래밍이 더 잘 맞는 도메인도 있다. 하지만 객체지향은 도메인 모델링 시에 놀랍도록 유연해서 넓은 범위의 도메인에서 효과적이며 생태계도 발전해 있으니 객체지향 패러다임을 택하는 것은 기술적으로 추천할 만한 선택이다."효과열심히 생각해보고 구현하면서 루틴이 생기는 것 같기는 한데, 루틴과 그 결과가 괜찮은지 잘 모르겠습니다. 다음 블로그 글은 실습 관련으로 올리겠습니다. 괜찮았으면...!

ostep / 가상화 / CPU / MLFQ (한글판 11장, 영문판 8장)

들어가며이번 장에서는 멀티 레벨 피드백 큐(MLFQ, Multi-Level Feedback Queue)에 대해서 다룹니다.이전 장에서 다룬 내용 중 이번 장에서 가장 중요한 내용 2가지를 꼽자면 다음과 같습니다.반환 시간을 최적화하기 위해서는 짧은 작업을 먼저 실행시켜야 한다. 평균적으로 대기하는 작업 수를 최소화해야 해서 그렇습니다.연관 개념: SJF, STCF 알고리즘응답 시간이 짧아지면 짧아질수록 반환 시간이 길어진다. 평균적으로 대기하는 작업 수가 늘어나서 그렇습니다.연관 개념: 라운드 로빈 알고리즘, 타임 슬라이스MLFQ 알고리즘은 이전 장에서 다루었던 가정 중 마지막 가정인 "작업의 시간이 사전에 알려져 있다"마저 없앤 현실적인 가정 하에 동작합니다. 현대 운영체제에서 적용하는 알고리즘의 뼈대가 됩니다.Ostep에서 이 장을 진행하는 구성은 다음과 같습니다.먼저 특정 시각에 MLFQ가 어떻게 동작하는지를 먼저 기술합니다. (Multi, Level, Queue)그리고 시간에 따라 피드백을 받으며 조정하는 부분을 기술합니다. (Feedback)개요MLFQ 알고리즘이 달성하고자 하는 목표는 다음과 같습니다.사용자가 실시간으로 기다리는 대화형 작업의 경우 응답 시간을 최소화이외의 작업의 경우 반환 시간을 최소화이를 어렵게 하는 난관은 다음과 같습니다. 사용자 작업의 소요 시간 및 특성을 사전에 알 수 없습니다.응답 시간을 최적화할 경우 반환 시간이 안 좋아지는 트레이드오프가 있습니다.이를 해결하기 위한 전략은 다음과 같습니다.작업이 지금까지 보여준 과거를 통해서 미래를 예측한다.기본적인 모델먼저 MLFQ가 특정 시각에 어떻게 동작하는지 살펴보겠습니다.먼저 MLFQ의 M, L, Q에 해당되는 부분입니다.Queue: 작업은 큐에서 대기합니다.Multi: 그런데 큐를 여러 개를 둡니다.Level: 그런데 그 여러 개의 큐들의 우선순위에 차등을 둡니다.우선 순위에 따른 동작은 다음과 같습니다. 규칙 1: 우선 순위가 높은 작업이 먼저 실행된다.규칙 2: 우선 순위가 같은 작업은 라운드 로빈 알고리즘으로 실행된다.이를 구현하기 위해서는 다음과 같습니다.우선 순위가 가장 높은 큐에 작업이 있으면, 라운드 로빈 알고리즘에 따라 다음 실행할 작업을 결정한다.우선 순위가 가장 높은 큐에 작업이 없으면, 다음 우선순위 큐로 넘어간다.우선 순위가 가장 낮은 큐까지 반복한다.시간에 따른 변화를 고려한 모델 (mk1)특정 시각으로 시간을 고정할 경우 작업마다 (과거에 실행된 것을 바탕으로) 우선 순위가 고정되어 있습니다. 하지만 특정 시각의 동작만 가지고는 초기에 정보가 없을 때 우선 순위를 어떻게 설정해야 하는지, 또 어떻게 변하는지에 대하는지 이해할 수 없습니다. 따라서 이 섹션에서는 시간에 따른 변화를 고려해보겠습니다. 일단 규칙부터 보여드리겠습니다.규칙 3: 모든 작업은 초기에는 가장 높은 우선순위로 실행된다.다시 말해 처음 생성된 작업은 우선순위가 가장 높은 큐에 대기시킵니다.규칙 4a: 주어진 타임 슬라이스를 모두 사용하면 우선순위를 한 단계 강등시킨다.즉, 우선 순위가 한 단계 낮은 큐에서 대기시킵니다.규칙 4b: 주어진 타임슬라이스를 모두 사용하지 않으면 우선순위를 유지시킨다.즉, 같은 큐에서 대기시킵니다.ostep에서 Q2 > Q1 > Q0인 3개의 큐를 둔 예시를 설명하고 있습니다. 책을 보시는 게 좋을 것 같아 여기서는 결론만 정리하겠습니다.실행 시간에 따른 분석긴 실행 시간을 가진 작업: Q2 -> Q1 -> Q0로 떨어져서 낮은 우선 순위로 실행짧은 실행시간을 가진 작업: Q2, Q1 등 높은 우선 순위에서 실행 후 완료짧은 실행 시간을 가진 작업을 더 높은 우선순위로 실행시켜 반환 시간을 최적화하는 것을 알 수 있습니다.입출력 작업: 주어진 타임 슬라이스가 끝나기 전에 입출력을 수행한다면 우선 순위 유지한다고 가정대화형 작업의 경우 타임 슬라이스가 종료되기 전에 입출력을 수행해 높은 우선 순위로 실행되어 응답 시간을 최적화할 수 있습니다.mk1의 문제점기아 상태(starvation)대화형 작업 여러 개가 존재한다면, 높은 우선순위의 큐만 실행하느라 낮은 우선순위 큐에 있는 CPU 위주 작업은 계속 실행되지 못하는 가능성이 있습니다.높은 우선순위를 유지하는 꼼수 존재CPU를 오래 사용하는 작업이더라도 타임 슬라이스가 끝나기 직전에 입출력을 수행한다면 높은 우선 순위를 유지할 수 있습니다.따라서 이 문제를 해결하기 위해서 타임 슬라이스 사용 여부의 boolean이 아닌, 타임 슬라이스의 얼마가 남아있는지를 저장해야 합니다.시간에 따른 작업의 특성 변화 고려 못함CPU 작업이 대화형 작업으로 변화할 수 있지만, mk1에서는 우선 순위가 내려간 작업은 다시 올라오지 않기 때문에 대화형 작업의 응답 시간이 길어질 가능성이 있습니다.시간에 따른 변화를 고려한 모델 (mk2)꼼수 문제를 해결하기 위해서 4번 규칙을 보완하겠습니다.규칙 4: 주어진 타임 슬라이스를 모두 사용하면 우선순위를 한 단계 강등시킨다. 단, CPU를 몇 번 양도하였는지와 상관없이 시간 할당량을 소진하는 것으로 강등 여부를 판단한다.즉, 남은 시간을 확인해서 0이라면 우선 순위가 한 단계 낮은 큐에서 대기시킵니다. 반면 0이 아니라면 같은 큐에서 대기시키되, 남은 시간을 저장하여 다음 실행 시에는 타임 슬라이스 시간이 아닌 남은 시간동안만 실행되도록 합니다.기아 상태 문제와 작업 특성 변화 문제를 해결하기 위해서 규칙을 하나 더 만들겠습니다.규칙 5: 일정 시간 S가 지나면 모든 작업을 최상위 큐로 이동시킨다. MLFQ의 조정과 다른 쟁점들MLFQ에는 정확하게 결정하기 위해서는 흑마법이 필요해 보이는 "부두 상수"들이 몇 가지 있습니다.큐의 개수큐 별 타임 슬라이스 길이우선 순위가 높으면 대개 타임 슬라이스가 짧습니다. 대화형 작업이 많기 때문입니다. (우선 순위가 낮으면 응답 시간보다는 반환 시간을 최적화하기 위해서 타임 슬라이스가 깁니다.ostep에서 다룬 것과 같이 정확한 규칙이 아닌, 수학 공식을 사용하여 우선순위를 조정하기도 합니다.또한 스케줄러는 다른 기능을 제공하기도 합니다. 사용자 작업에 대해서 우선순위를 정하게 해주는 nice와 같은 기능이 그 예입니다. 정리Ostep에서 다룬 MLFQ 알고리즘의 경우 다음 5가지 규칙으로 정리할 수 있습니다.규칙 1: 우선 순위가 높은 작업이 먼저 실행된다.규칙 2: 우선 순위가 같은 작업은 라운드 로빈 알고리즘으로 실행된다.규칙 3: 모든 작업은 초기에는 가장 높은 우선순위로 실행된다.규칙 4: 주어진 타임 슬라이스를 모두 사용하면 우선순위를 한 단계 강등시킨다. 단, CPU를 몇 번 양도하였는지와 상관없이 시간 할당량을 소진하는 것으로 강등 여부를 판단한다.규칙 5: 일정 시간 S가 지나면 모든 작업을 최상위 큐로 이동시킨다.그 결과로 MLFQ는 반환 시간과 응답 시간을 모두 최적화합니다. 짧게 실행되는 작업은 SJF/STCF처럼 처리해 전반적인 성능을 개선시키고, 오래 실행되는 CPU 작업의 경우 공정하게 실행되도록 기아 상태를 방지하고 조금이라도 진행되게 합니다. 이런 이유로 많은 운영체제에서 MLFQ를 기본 스케줄러로 사용하고 있습니다.출처강의: https://pages.cs.wisc.edu/~remzi/Classes/537/Fall2021/Discussion/videos.html책: https://pages.cs.wisc.edu/~remzi/OSTEP/Korean/

알고리즘 / self-balancing binary tree

red-black tree와 유사하지만 경우의 수가 더 적은 2-3 트리와 일대일 대응이 되는 self-balancing binary tree를 구현해보았다.red-black tree는 아주 아주 오래 걸릴 것 같아서 더 쉬운 버전을 구현한다고 했는데 하루 종일 걸렸다.red-black tree보다는 간단해서 순한 맛인데,트리 회전에 대해서 생각하지 않고 순수 함수를 이용한 순한 맛인데타입스크립트의 표현력 깊은 타입 시스템까지 활용해서 분명히 순한 맛인데어려웠다.고려할 경우의 수가 많았다.테스트도 제대로 못 해보았지만 구현한 것에 의미를 두고 잘 동작하길 기원만 하고 넘어가기로 했다. 부끄럽다. // Copyright 2024-2024 Dongook Lee // SPDX-License-Identifier: MIT // AA-like tree implementation with one tag bit per node // https://en.wikipedia.org/wiki/AA_tree type Tree = null | Node2 | Node3 // A tag value of true corresponds to black nodes in a red-black tree type Node2 = [tag: true, l: Tree, x: number, r: Tree] type Node3 = [tag: true, l: Tree, x: number, [tag: false, m: Tree, y: number, r: Tree]] function isNode2(tree: Tree): tree is Node2 { return tree !== null && (tree[3] === null || tree[3][0]) } const node2 = (l: Tree, x: number, r: Tree): Node2 => [true, l, x, r] const replaceLeft2 = ([, _l, x, r]: Node2, l2: Tree): Node2 => node2(l2, x, r) const replaceValue2 = ([, l, _x, r]: Node2, x2: number): Node2 => node2(l, x2, r) const replaceRight2 = ([, l, x, _r]: Node2, r2: Tree): Node2 => node2(l, x, r2) const node3 = (l: Tree, x: number, m: Tree, y: number, r: Tree): Node3 => [true, l, x, [false, m, y, r]] const replaceLeft3 = ([, _l, x, [, m, y, r]]: Node3, l2: Tree): Node3 => node3(l2, x, m, y, r) const replaceLeftValue3 = ([, l, _x, [, m, y, r]]: Node3, x2: number): Node3 => node3(l, x2, m, y, r) const replaceMiddle3 = ([, l, x, [, _m, y, r]]: Node3, m2: Tree): Node3 => node3(l, x, m2, y, r) const replaceRightValue3 = ([, l, x, [, m, _y, r]]: Node3, y2: number): Node3 => node3(l, x, m, y2, r) const replaceRight3 = ([, l, x, [, m, y, _r]]: Node3, r2: Tree): Node3 => node3(l, x, m, y, r2) // Insert const upgradeLeft2 = ([, _l, x, r]: Node2, [, ll, y, lr]: Node2): Node3 => node3(ll, y, lr, x, r) const upgradeRight2 = ([, l, x, _r]: Node2, [, rl, y, rr]: Node2): Node3 => node3(l, x, rl, y, rr) function upgradeLeft3([, _l, x, [, m, y, r]]: Node3, [, ll, z, lr]: Node2): Node2 { return node2(node2(ll, z, lr), x, node2(m, y, r)) } function upgradeMiddle3([, l, x, [, _m, y, r]]: Node3, [, ml, z, mr]: Node2): Node2 { return node2(node2(l, x, ml), z, node2(mr, y, r)) } function upgradeRight3([, l, x, [, m, y, _r]]: Node3, [, rl, z, rr]: Node2): Node2 { return node2(node2(l, x, m), y, node2(rl, z, rr)) } type InsertionResult = | [upgraded: false, newNode: Tree] | [upgraded: true, newNode: Node2] function insert(tree: Tree, v: number): InsertionResult { if (tree === null) { return [true, node2(null, v, null)] } if (isNode2(tree)) { const [, l, x, r] = tree if (v >= x) { const [up, r2] = insert(r, v) return up ? [false, upgradeRight2(tree, r2)] : [false, replaceRight2(tree, r2)] } const [up, l2] = insert(l, v) return up ? [false, upgradeLeft2(tree, l2)] : [false, replaceLeft2(tree, l2)] } // Node3 const [, l, x, [, m, y, r]] = tree if (v >= y) { const [up, r2] = insert(r, v) return up ? [true, upgradeRight3(tree, r2)] : [false, replaceRight3(tree, r2)] } if (v >= x) { const [up, m2] = insert(m, v) return up ? [true, upgradeMiddle3(tree, m2)] : [false, replaceMiddle3(tree, m2)] } const [up, l2] = insert(l, v) return up ? [true, upgradeLeft3(tree, l2)] : [false, replaceLeft3(tree, l2)] } type DeletionResult = | [downgraded: false, newNode: Tree] | [downgraded: true, newNode: Node3 | null] function downgradeLeft2([, _l, x, r]: Node2, l2: Node3 | null): DeletionResult { if (r === null) { throw new TypeError("expected non-null sibling, got null") } if (isNode2(r)) { const [, rl, y, rr] = r return [true, node3(l2, x, rl, y, rr)] } const [, rl, y, [, rm, z, rr]] = r return [false, node2(node2(l2, x, rl), y, node2(rm, z, rr))] } function downgradeRight2([, l, x, _r]: Node2, r2: Node3 | null): DeletionResult { if (l === null) { throw new TypeError("expected non-null sibling, got null") } if (isNode2(l)) { const [, ll, y, lr] = l return [true, node3(ll, y, lr, x, r2)] } const [, ll, y, [, lm, z, lr]] = l return [false, node2(node2(ll, y, lm), z, node2(lr, x, r2))] } function downgradeLeft3([, _l, x, [, m, y, r]]: Node3, l2: Node3 | null): DeletionResult { if (m === null) { throw new TypeError("expected non-null sibling, got null") } if (isNode2(m)) { const [, ml, z, mr] = m return [false, node2(node3(l2, x, ml, z, mr), y, r)] } const [, ml, z, [, mm, w, mr]] = m return [false, node3(node2(l2, x, ml), z, node2(mm, w, mr), y, r)] } function downgradeMiddle3([, l, x, [, _m, y, r]]: Node3, m2: Node3 | null): DeletionResult { if (r === null) { throw new TypeError("expected non-null sibling, got null") } if (isNode2(r)) { const [, rl, z, rr] = r return [false, node2(l, x, node3(m2, y, rl, z, rr))] } const [, rl, z, [, rm, w, rr]] = r return [false, node2(l, x, node2(node2(m2, y, rl), z, node2(rm, w, rr)))] } function downgradeRight3([, l, x, [, m, y, _r]]: Node3, r2: Node3 | null): DeletionResult { if (m === null) { throw new TypeError("expected non-null sibling, got null") } if (isNode2(m)) { const [, ml, z, mr] = m return [false, node2(l, x, node3(ml, z, mr, y, r2))] } const [, ml, z, [, mm, w, mr]] = m return [false, node2(l, x, node2(node2(ml, z, mm), w, node2(mr, y, r2)))] } function isLeafNode(node: Node2 | Node3): boolean { return node[1] === null } function popMinValue(tree: Tree): [number, DeletionResult] { if (tree === null) { throw new Error("expected non-empty tree, got null") } if (isLeafNode(tree)) { if (isNode2(tree)) { const [, _l, x, _r] = tree return [x, [true, null]] } const [, _l, x, [, _m, y, _r]] = tree return [x, [false, node2(null, y, null)]] } if (isNode2(tree)) { const [, l] = tree const [x2, [down, l2]] = popMinValue(l) return down ? [x2, downgradeLeft2(tree, l2)] : [x2, [false, replaceLeft2(tree, l2)]] } const [, l] = tree const [x2, [down, l2]] = popMinValue(l) return down ? [x2, downgradeLeft3(tree, l2)] : [x2, [false, replaceLeft3(tree, l2)]] } function remove(tree: Tree, v: number): DeletionResult { if (tree === null) { throw new Error("value not found") } if (isLeafNode(tree)) { if (isNode2(tree)) { const [, _l, x, _r] = tree if (v === x) { return [true, null] } throw new Error("value not found") } const [, _l, x, [, _m, y, _r]] = tree if (v === x) { return [false, node2(null, y, null)] } if (v === y) { return [false, node2(null, x, null)] } throw new Error("value not found") } if (isNode2(tree)) { const [, l, x, r] = tree if (v > x) { const [down, r2] = remove(r, v) return down ? downgradeRight2(tree, r2) : [false, replaceRight2(tree, r2)] } if (v === x) { const [x2, [down, r2]] = popMinValue(r) return down ? downgradeRight2(replaceValue2(tree, x2), r2) : [false, node2(l, x2, r2)] } const [down, l2] = remove(l, v) return down ? downgradeLeft2(tree, l2) : [false, replaceLeft2(tree, l2)] } const [, l, x, [, m, y, r]] = tree if (v > y) { const [down, r2] = remove(r, v) return down ? downgradeRight3(tree, r2) : [false, replaceRight3(tree, r2)] } if (v === y) { const [y2, [down, r2]] = popMinValue(r) return down ? downgradeRight3(replaceRightValue3(tree, y2), r2) : [false, node3(l, x, m, y2, r2)] } if (v > x) { const [down, m2] = remove(m, v) return down ? downgradeMiddle3(tree, m2) : [false, replaceMiddle3(tree, m2)] } if (v === x) { const [x2, [down, m2]] = popMinValue(m) return down ? downgradeMiddle3(replaceLeftValue3(tree, x2), m2) : [false, node3(l, x2, m2, y, r)] } const [down, l2] = remove(l, v) return down ? downgradeLeft3(tree, l2) : [false, replaceLeft3(tree, l2)] } export function toInserted(t: Tree, v: number): Tree { return insert(t, v)[1] } export function toRemoved(t: Tree, v: number): Tree { return remove(t, v)[1] }

ostep / 가상화 / CPU / 스케줄링 정책 (한글판 10장, 영문판 7장)

들어가며ostep에서는 스케줄링 정책에 대해서 설명할 때 비현실적인 가정 하에 만든 단순화한 모델에서 시작해 가정을 하나씩 없애가면서 점점 복잡한 모델을 만들면서 최종적으로 현실에서 사용하는 모델에 다다릅니다.이 장에서는 작업의 실행 시간을 사전에 알 수 있는 경우까지만 다룹니다.책에서와 섹션 구성에 아주 살짝의 차이를 두었습니다.책에서는 알고리즘별로 섹션을 구성하여, 알고리즘을 설명하고, 가정을 완화한 다음에 생기는 문제를 같이 제시했습니다.저는 사용한 가정에 따라 섹션을 구성하여, 각 섹션별로 이전 섹션에서 가정을 완화한 모델을 제시하고, 이전 섹션에서 최적의 알고리즘을 적용했을 때 발생하는 문제를 제시하고 이를 새로운 모델로 해결하는 방향으로 풀어갔습니다.워크로드에 대한 가정모든 작업은 같은 시간동안 실행됩니다.모든 작업은 동시에 도착합니다.각 작업은 시작되면 완료될 때까지 실행됩니다.모든 작업은 CPU만 사용합니다.각 작업의 실행 시간은 사전에 알려져 있습니다.스케줄링 알고리즘 한 눈에 살펴보기비선점형 스케줄링가장 단순한 모델모든 가정을 고려한 가장 단순한 모델에서 출발해보겠습니다.모델모든 작업이 같은 시간동안 실행되고,동시에 도착하고,시작하면 완료될 때까지 실행되고,CPU만 사용하고,실행 시간은 사전에 알려져 있습니다.평가 기준: 반환 시간이 때 스케줄링 알고리즘은 무엇을 최적화해야 할까요? 각 작업을 완료하는데 소요된 시간을 최적화할 수 있겠습니다. 이를 반환 시간으로 정의합니다. 계산할 때에는 주어진 정보를 활용하여 $(완료\ 시간) - (도착\ 시간)$으로 계산할 수 있겠습니다.알고리즘: FIFO모든 작업들이 시간적인 측면에서는 동일하기 때문에 어떤 순서로 실행해도 평균 반환 시간은 동일합니다.가장 심플하게 구현하자면 작업들이 나열된 순서대로 실행하는 알고리즘을 생각할 수 있겠습니다. 이 알고리즘을 FIFO (선입선출)라고 부릅니다.가정 완화: 작업들의 실행 시간이 항상 같지는 않다면?이전 모델에서 "모든 작업이 같은 시간동안 실행된다"라는 가정을 제거해보겠습니다.모델모든 작업이 동시에 도착하고,시작하면 완료될 때까지 실행되고,CPU만 사용하고,실행 시간은 사전에 알려져 있습니다.평가 기준: 반환 시간FIFO의 문제: Convoy Effect선입선출 알고리즘에서 길이가 각각 10, 10, 100인 작업이 다른 순서로 들어온 경우를 비교해보겠습니다.순서대로 시간이 10, 10, 100인 작업이 들어온 경우 반환시간이 각각 10, 20, 120이며, 평균 반환시간은 $\frac{10+20+120}{3} = 50$입니다.순서대로 시간이 100, 10, 10인 작업이 들어온 경우 반환시간이 각각 100, 110, 120이며, 평균 반환시간은 $\frac{100+110+120}{3} = 110$입니다.각각의 작업의 소요 시간은 같은데 평균 반환시간이 이렇게 차이가 나는 이유는 앞에 시간이 오래 걸리는 작업이 있어서 뒤의 짧게 끝나는 작업들이 모두 긴 시간을 기다리기 때문입니다.이 효과를 Convoy Effect라고 합니다.해결 방법: SJFConvoy Effect를 최소화하려면 작업 시간이 최소인 작업부터 순서대로 실행해야 합니다.이렇게 대기 중인 작업 중 소요 시간이 최소인 작업부터 실행하는 알고리즘을 최단 작업 우선(Shortest Job First, SJF)라고 합니다.SJF 알고리즘은 현재 가정 하에서 평균 반환 시간을 최소화함이 수학적으로 증명되어 있습니다.여담: 수학적인 증명 스케치가정에 의해 모든 작업이 동시에 도착하기 때문에 모든 작업 목록이 도착 시점에 정해짐을 알 수 있습니다.작업 목록의 개수가 정해져 있을 때 평균 반환 시간을 최적화하는 것과 총 반환 시간을 최적화하는 것은 같습니다. $(평균\ 반환\ 시간) = \frac{(총\ 반환\ 시간)} {(작업\ 개수)}$이기 때문입니다.총 반환 시간총 반환시간은 각 작업의 반환시간, 즉 각 작업이 완료되기까지 기다려야 하는 시간을 모두 합하여 구할 수 있습니다. 다른 방법으로는 각 작업이 실행되는 동안 작업들이 실행 및 대기중인 시간을 모두 합할 수도 있습니다. 그림으로 나타내면 다음과 같습니다.먼저 실행하면 실행할수록 많은 작업들이 대기 중이므로, 많은 작업들이 짧은 시간동안만 대기하도록 짧은 작업의 순서대로 실행시키는 알고리즘이 총 반환시간을 최소화합니다.엄밀하게는 재배열 부등식을 통해 증명할 수 있습니다. 가정 완화: 작업들이 모두 같은 시간에 도착하지는 않는다면?책에서는 별도로 다루지 않았으므로 짧게 넘어가겠습니다. 이 경우에도 각 작업이 끝날 때마다 대기 중인 작업 중 가장 짧은 작업을 실행시키는 SJF 알고리즘이 최적의 알고리즘입니다.아까전의 예시에서 시간이 각각 10, 10, 100인 작업들이 간발의 차로 100, 10, 10의 순서대로 도착한다고 가정해보겠습니다. 그렇다면 SJF 알고리즘을 적용하여도 최적의 평균 대기 시간은 $\frac{100 + 110 + 120}{3} = 110$이 되겠습니다.선점형 스케줄링들어가며지금까지는 "작업이 시작하면 완료될 때까지 계속 실행된다"는 가정 하의 스케줄링 알고리즘에 대해서 살펴보았습니다. 이는 예전에 많이 사용했던 일괄 처리 시스템에서 유효하게 사용되었던 가정입니다. 이런 가정 하의 스케줄러를 비선점(non-preemptive) 스케줄러라고 합니다.반면 현대 운영체제에서는 OS가 한 프로세스의 실행을 중단시키고 다른 프로세스에게 실행권을 넘길 수 있습니다. 구체적으로 말하면 스케줄러는 앞 장에서 다루었던 문맥 교환을 수행할 수 있습니다. 이렇게 한 작업을 중단시키고 다른 작업을 처리하는 스케줄러를 선점 스케줄러라고 하며, 현대 OS에서 사용하는 거의 모든 스케줄러는 선점 스케줄러입니다.가정 완화: 작업이 완료되기까지 기다리지 않아도 된다면?모델모든 작업은 CPU만 사용하고,실행 시간은 사전에 알려져 있습니다.평가 기준: 반환 시간 SJF의 문제: Convoy Effect아까전에 보았던 간발의 차로 100, 10, 10의 순서대로 작업이 도착하는 상황을 생각해보겠습니다.앞의 상황에서는 작업이 끝날 때까지 기다려야 한다는 가정이 있었습니다.따라서 SJF 알고리즘을 적용하여도, 나중에 도착한 짧은 작업이 이미 시작한 긴 작업을 중단할 수 없었기 때문에 기다려야 했습니다. 다시 말해, 앞에 살펴보았던 Convoy Effect가 다시 발생했음을 확인할 수 있습니다.해결: STCF작업이 도착하는 족족 현재 실행 중인 작업을 포함해서 SJF 알고리즘을 적용한다고 생각하면, 현재 시점에서 가장 잔여 시간이 적은 작업을 먼저 실행해야 한다는 사실을 알 수 있습니다. 이를 STCF (Shortest Time-to-Completion First)라고 부릅니다. 새로운 평가 기준: 응답 시간일괄 처리 시스템에서는 작업의 반환 시간을 최적화하는 것과 작업이 처음 실행되는 시간을 최적화하는 것이 좋은 평가 기준이었습니다.하지만 시분할 컴퓨터가 등장하면서 사용자가 상호작용을 하면서 응답 시간이라는 새로운 평가 기준이 중요해지기 시작했습니다.ostep에서는 응답 시간을 작업이 도착하기부터 처음 스케줄될 때까지의 시간으로 정의합니다.수식으로는 다음과 같이 정의합니다: $(응답\ 시간) = (첫\ 실행\ 시간) - (도착\ 시간)$응답 시간을 최적화하는 알고리즘모델모든 작업은 CPU만 사용하고,실행 시간은 사전에 알려져 있습니다.평가 기준: 응답 시간문제반환 시간을 최적화하는 알고리즘의 경우 응답 시간이 길어지는 경우가 있습니다. 예를 들어 10초짜리 작업이 10개가 대기하고 있다면 대기 중인 11초짜리 작업은 응답시간이 최소 100초가 되겠습니다.알고리즘: Round RobinRound Robin 알고리즘은 정해진 타임 슬라이스(time slice) 혹은 스케줄링 퀀텀(scheduling quantum)동안 현재 작업을 실행 한 후 대기 중인 다음 작업으로 넘어갑니다.타임 슬라이스의 길이응답 시간 측면에서는 짧은 것이 좋습니다.문맥 교환 비용의 상쇄(amortization) 측면에서는 긴 것이 좋습니다.이 둘을 고려해서 적절한 길이로 설정해야 합니다.트레이드오프: 공정한 정책의 경우 반환 시간이 안 좋습니다.동일한 작업을 가지고 공정한 정책과 불공정한 정책을 비교해 보겠습니다.두 정책 모두 총 CPU 사용 시간은 동일합니다. (문맥 교환 비용은 상쇄되었다고 가정하겠습니다.)공정한 정책의 경우 CPU의 시간을 골고루 나누어주기 위해서 실행 중인 작업을 중단시키고 대기시키는 과정이 있습니다. 이로 인해 CPU 사용 중에 더 많은 작업들이 대기 중이게 됩니다.총 실행 시간이 같을 때, 대기 중인 작업이 더 많을 때 총 반환 시간이 커짐을 알 수 있습니다.표로 만들어서 각 시간대별로 비교해보시면 비교가 쉽습니다. (아래 표에서는 세로줄끼리 비교)시간이 10, 10, 100인 작업이 도착했을 때 첫 번째 표는 STCF, 두 번째 표는 time slice를 5로 놓은 RR입니다.입출력 연산의 고려모델모든 작업은 CPU와 입출력을 모두 사용하고,실행 시간은 사전에 알려져 있습니다.알고리즘한 개의 작업이 CPU를 사용하다가 입출력 작업으로 넘어갈 경우, 입출력을 대기하고 있는 CPU 자원을 다른 작업에게 할당한다면 시스템을 더 잘 활용할 수 있습니다.이를 구현하기 위해서 각 입출력 작업 사이의 CPU 작업들(CPU 버스트)을 별개의 작업으로 간주하면 기존의 정책을 그대로 적용하면서 입출력 대기중일 때 다른 작업을 수행할 수 있게 됩니다.나가며이렇게 실행 시간이 사전에 알려져 있는 경우에 여러 가지 알고리즘을 학습하고 비교하였습니다. 하지만 현실에서는 작업의 실행 시간이 얼마인지 사전에 알고 있다는 가정은 비현실적입니다. 따라서 다음 장에서는 사전 지식 없이 반환 시간과 응답 시간을 모두 고려하는 알고리즘에 대해서 다루게 됩니다.출처강의: https://pages.cs.wisc.edu/~remzi/Classes/537/Fall2021/Discussion/videos.html책: https://pages.cs.wisc.edu/~remzi/OSTEP/Korean/

스프링 핵심 원리 - 기본편 / 싱글톤 컨테이너

"스프링 핵심 원리 - 기본편" 강의를 수강중입니다. 학습한 내용을 정리하고 있습니다.싱글톤 개요어떤 클래스의 인스턴스가 정확히 한 개여야 할 때 사용합니다.그 클래스의 인스턴스를 사용하는 코드는 모두 같은 인스턴스에 접근하게 됩니다.싱글톤으로 해결하고자 하는 문제웹 서버의 경우 사용자의 요청이 올 때마다 서버의 코드가 실행됩니다.이 때 사용자의 요청이 올 때마다 클래스의 인스턴스를 생성하고 가비지컬렉션으로 제거하는 것보다, 재사용할 수 있는 인스턴스는 재사용하는 것이 경제적입니다.문제 해결 1 - 싱글톤 패턴미리 인스턴스를 만들어놓을 것인지, 실행 시 동적으로 필요 시 인스턴스를 만들 것인지에 따라서 싱글톤 패턴에도 여러 종류가 존재합니다.다음은 전자에 대한 예시 코드입니다.public class Singleton { private Singleton() {} private static final Singleton instance = new Singleton(); public static Singleton getInstance() { return instance; } }싱글톤 패턴의 문제 싱글톤으로 관리하고자 하는 모든 클래스 코드에 싱글톤 패턴의 코드를 추가해야 합니다. 클라이언트가 구체 클래스에 의존하게 되어 OCP, DIP를 위반할 가능성이 높습니다, 테스트하기 어렵습니다.스프링을 안 쓸 때 이 문제를 해결하려면, 앞의 DI에서 한 것과 마찬가지로 클라이언트는 추상적인 인터페이스에 의존하도록 하고, DI를 활용하여 싱글톤 인스턴스를 주입하는 코드만 구체 클래스에 의존하도록 구성하면 해결할 수 있습니다. 내부 속성의 초기화가 어렵습니다.필요한 내부 속성의 종류가 컴파일 시점에 정해져 있으면 내부 속성 종류별로 하나씩 싱글톤을 만들어야 할 것 같습니다.필요한 내부 속성의 종류가 컴파일 시점에 정해져 있지 않으면 싱글톤 패턴을 사용하면 안 될 것 같습니다.내부 속성의 변경이 어렵습니다.자식 클래스를 만들기 어렵습니다.문제 해결 2 - 스프링 컨테이너스프링 컨테이너의 경우 앞의 싱글톤 패턴의 문제점들을 해결해줄 수 있습니다.특히 보일러플레이트의 문제를 해결해줄 수 있습니다.동작 방식스프링 컨테이너의 경우 기본적으로 스프링 빈을 싱글톤 객체로 관리해줍니다.이 때 각 클래스에 싱글톤 패턴을 적용하지 않아도 스프링 빈에서의 인스턴스는 동일하게 관리됩니다.동작 원리의문: 각 클래스에 싱글톤 패턴을 적용하지 않았고, 클래스의 인스턴스를 생성하는 함수를 여러 번 호출하였는데도 어떻게 싱글톤 인스턴스가 생성되는 것일까요? -> @Configuration 어노테이션스프링에서 @Configuration 어노테이션이 붙은 클래스를 상속받는 하위 클래스를 만들고 이를 사용한다.하위 클래스 예상도: @Bean 어노테이션이 달린 부모 클래스의 메소드들을 오버라이딩해서, 이미 빈이 등록되어 있으면 그 인스턴스를 반환하고, 없으면 부모 클래스의 메소드를 호출해서 빈으로 등록하는 코드가 적용되어 있을 것이다.싱글톤 컨테이너 사용시 주의사항각 컨테이너를 무상태(stateless)로 만들어주어야 합니다!!!