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

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

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

설계 시간 문제설계와 구현의 밸런스 중에서 설계에 치중해 있었던 것 같습니다.문제: 저는 설계할 때 생각과 고민이 너무 너무 많습니다.시도한 해결 방안오히려 설계를 열심히 파서 고민을 해결하고 제 나름대로의 설계 방법론이 생기면 빠르게 설계를 끝내고 구현으로 넘어갈 수 있지 않을까 생각했습니다."오브젝트" 책 보기"오브젝트"를 도서관에서 빌렸지만 훑어만 보고 깊게 읽어보지 못한 상태로 반납했습니다. 훑어보기밖에 하지 못했지만 고민을 해결해준 부분, 모르는 것을 알려준 부분, 생각만 하던 것을 확인해준 부분들을 많이 확인할 수 있었습니다. 책임을 어떻게 배분해야 할지에 대해서 고민거리를 던져주었습니다. 취업 시 구매 목록 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)로 만들어주어야 합니다!!!

스프링 핵심 원리 - 기본편 / 객체 지향 설계 / DI와 정적, 동적 의존 관계

스프링 핵심 원리의 기본편을 수강중입니다. 이론에 해당되는 내용 중 일부를 재해석해서 정리해보았습니다.용어 정리의존 관계이 글에서는 일단 "A가 B에 의존한다"를 "B가 변경될 경우 A가 변경되어야 한다"라고 정의하겠습니다.예를 들어 어떤 프로젝트 내에서 데이터 저장소를 ARepository에서 BRepository로 변경할 때 CService의 코드 내에 해당 부분을 변경해야 할 경우, "CService 클래스 구현 코드는 ARepository 클래스에 의존한다"고 표현하겠습니다. 정적 / 동적이 글에서만 관심 있는 영역의 코드가 컴파일되기 전에 이미 고정된 것을 정적인 것으로 정의하고, 코드 상으로는 고정되어 있지 않고, 컴파일 후 실행될 때에야 정해지는 것을 동적인 것으로 정의하겠습니다.다른 글들을 보았을 때 맥락에 따라 "컴파일" 대신 다른 단어가 들어오는 경우도 있는 것 같습니다.OCP (개방-폐쇄 원칙)"코드는 기능 확장에는 열려 있으면서, 수정에는 닫혀 있어야 한다."는 원칙입니다.다시 말해 코드 자체를 수정하지 않고도 기능을 확장할 수 있어야 한다는 원칙입니다. SRP (단일 책임 원칙)모듈은 한 가지 책임만 지녀야 한다는 원칙입니다.여기서 책임이란 모듈의 변화에 대한 이유입니다.이 글의 맥락에서는 지엽적인 내용이지만, 솔직히 말씀드리면 위 정의를 보긴 했지만 적용이 가능할 정도로 명확히 알지 못해 다음 자료들을 참고하였습니다. 제가 일단 이해한 내용을 공유드리겠습니다.일단 이해한 내용소프트웨어를 개발할 때 사용하는 자료 구조나 알고리즘의 종류와 같이 변화가 예상되는 부분들이 있다. 소프트웨어를 모듈로 나타낼 때, 실행되는 순서로 모듈을 구성하기보다는 변화하는 부분들을 다른 모듈들로부터 격리시키는 방식으로 모듈화를 한다면 특정 요소가 변하더라도 그 변화에 대한 한 모듈만 수정할 수 있다.비즈니스 소프트웨어에서는 변화를 요구하는 대상이 특정 비즈니스 로직과 관련된 특정 부서이기 때문에, 모듈을 설계할 때 그 모듈에게 변화를 요청하는 대상이 한 부서가 되도록 구성하는 것이 이상적이다.참고 자료https://blog.cleancoder.com/uncle-bob/2014/05/08/SingleReponsibilityPrinciple.htmlhttps://en.wikipedia.org/wiki/Single-responsibility_principlehttps://dl.acm.org/doi/pdf/10.1145/361598.361623https://www.sicpers.info/2023/10/ive-vastly-misunderstood-the-single-responsibility-principle/DI (의존성 주입)해결하고자 하는 문제어떤 기능을 실행 시에 다양한 구현체들을 사용하는 방식으로 확장하고 싶습니다.예시: 데이터 저장을 위한 Repository를 운영 시에는 DatabaseRepository를 사용해서, 개발 시에는 InMemoryRepository를 사용하여 실행하고 싶습니다.그러나 Repository 구현체를 변경하려고 보니 Repository를 사용하는 모든 곳에서 구현체를 수정해야 하는 문제가 발생했습니다.예시 class Service { private final Repository repository = new InMemoryRepository(); // 코드 수정 필요 // Repository 사용 로직 ... }DI를 사용한 해결 방안Repository를 사용하는 클래스들이 DatabaseRepository와 같은 구체적인 구현체들을 사용하지 않게 지워버린 후 Repository 인스턴스를 외부에서 주입받도록 합니다. 여기서는 생성자를 통해 주입받았습니다.예시 class Service { private final Repository repository; public Service(Repository repository) { this.repository = repository; } // Repository 사용 로직 ... }Config 클래스를 따로 두어 인스턴스를 생성하는 코드들을 모두 이 클래스에 둡니다. 인스턴스가 필요한 경우 이 클래스에서 사용하면 됩니다. 예시class Config { repository() { return new InMemoryRepository(); } service() { return new Service(repository()); } }OCP 관점에서의 해석원래 문제에서는 실행 시점에 다른 구현체를 사용하는 기능 확장을 하고 싶었지만, 이를 위해 구현체를 사용하는 코드를 변경해야 했습니다. 따라서 OCP를 위반하는 설계였습니다. 이 때 OCP의 각 부분을 이 맥락에서 다음과 같이 해석할 수 있습니다.기능 확장의 대상은 실행 시점에 실행되는 코드로, 이는 Repository 클래스의 인스턴스입니다.반면 소스 코드 수정과 관련된 부분은 컴파일 시점에 결정되는 Service 클래스의 코드 자체입니다.따라서 OCP를 만족하기 위해서는 "Service 인스턴스의 실행 시점에는 서로 다른 Repository 구현체 인스턴스를 사용하되, 컴파일 시점에 같은 Service클래스 코드를 사용하고 싶다"는 문제를 해결해야 합니다.다시 말하면 각 Service 인스턴스는 서로 다른 Repository 구현체 인스턴스에 의존하게 하되, Service 클래스는 구체적인 Repository 구현체 클래스에 의존하지 않도록 해야 합니다.그래서 DI를 사용해서 Service와 Repository 간의 동적인 의존관계와 정적인 의존관계를 서로 다르게 만듦으로써 OCP를 만족하는 설계를 구성하였다고 해석할 수 있습니다. SRP 관점에서의 해석기존의 Service 코드에서는 Repository의 인스턴스를 생성하는 책임과 Repository를 사용하는 책임이 같이 있었습니다. 따라서 SRP를 위반하는 설계였습니다.이 때 Repository를 사용하는 로직은 Repository 인터페이스만 알고 구현체 클래스를 몰라도 문제가 없습니다.반면 Repository 인스턴스를 생성하려면 구체적인 Repository 구현체 클래스의 정보를 알아야 합니다.여기서 Repository 구현체를 변경하면, 원래는 구현체를 몰라도 되는 Repository 사용 로직이 인스턴스 생성 로직과 같은 클래스 안에 담겨 있어 수정의 대상이 되었습니다.DI를 사용하여 수정된 설계에서는 객체들의 인스턴스를 생성하는 책임을 Config 클래스에 몰아줌으로써 Repository 구현체를 변경할 때에도 Service 코드는 영향을 받지 않고 Config 클래스만 수정하면 되도록 바뀌었습니다.

알고리즘 / 투포인터

들어가며일단 만나본 투포인터 유형들에 대해서 코드가 간단하게 나오는 경우가 많아서 공유하고자 합니다.참고: 몇 문제 풀어보지 않아서 공유하는 코드를 응용해야 하는 경우도 있을 것 같습니다.유형제가 확인했던 투포인터 유형의 경우 다음 공통점이 특징적이었습니다.어떤 수열이 있고, 그 수열의 연속된 구간 각각에 대해서 어떤 값을 도출해낼 수 있다.한 구간이 다른 구간을 완전하게 포함하고 있으면 도출해낸 값도 더 커진다.도출값이 정확히 X가 되는 경우 or X 이상인 도출값들 중 최소값을 구한다.예시 문제 풀이a = [1, 2, 3]의 연속한 구간의 합들 중 1.5보다 큰 값들 중 최소값을 구하는 문제를 풀어보겠습니다.연속한 구간의 시작과 끝 인덱스를 i와 j로 놓고 (a[i]는 구간에 포함, a[j]는 미포함) 전체 과정을 그림으로 나타내면 다음과 같습니다.첫 번째 표는 모든 i와 j에 대해서 합을 구한 모습입니다.이 문제에서는 i가 j보다 큰 경우는 고려할 필요가 없지만 그 경우에도 이 알고리즘이 잘 작동한다는 것을 보여주기 위해서, i가 j보다 큰 경우 부분합을 음수로 계산한다고 가정하고 넣었습니다.여기서 눈여겨볼점은 값이 i가 증가할수록 작아지고, j가 증가할수록 커진다는 점입니다.직관적으로 오른쪽이나 위로 갈수록 숫자가 커진다고 볼 수도 있습니다.두 번째 표는 합들 중 1.5보다 크거나 같은 영역을 붉은색으로 색칠한 것입니다.이 때 어떤 칸이 색칠되어 있으면, 그 칸보다 오른쪽이나 위에 있는 칸들은 1.5보다 크기 때문에 그 칸의 오른쪽 위의 영역들이 모두 붉은색으로 색칠된 것을 볼 수 있습니다.이 때 문제에서 1.5보다 큰 값들 중 최소값을 구하려면 색칠된 칸들 중 가장 왼쪽 아래에 있는 값들만 고려하면 된다는 것을 확인할 수 있습니다. 진한 붉은 색으로 나타냈습니다.세 번째 표는 알고리즘의 진행을 나타냅니다.합이 1.5보다 작으면 오른쪽으로 진행하고, 합이 1.5 이상이면 아래쪽으로 진행합니다.진행한 칸을 파란색으로, 붉은 영역과 겹치는 칸들은 보라색으로 나타냈습니다.아래 소개드릴 코드는 보라색 칸들에 대해서 원하는 로직을 실행하게 됩니다.붉은 영역을 여러 개 가지고 실험해보시면, 이렇게 진행할 경우 붉은 영역의 아래 경계를 훑고 지나간다는 것을 확인할 수 있습니다. 따라서 보라색 칸들이 위에서 언급한 가장 왼쪽 아래 칸들을 포함한다는 것을 알 수 있습니다. 코드제가 현재 사용하고 있는 코드는 다음과 같습니다.function* solve(f, lowerBound, iMax, jMax) { let [i, j] = [0, 0] while (i = lowerBound) { yield f(i, j) ++i } else { ++j } } } function main() { // ... const candidates = [...solve(f, lowerBound, iMax, jMax)] const result = Math.min(...candidates) }구간의 합 특수 경우: 투포인터 문제의 경우 f 함수로 구간의 합을 구하는 경우가 대표적인데, 아쉽게도 위 코드와 f = (i, j) => nums.slice(i, j).reduce((a, b) => a + b, 0)으로 구현 시 구간합을 구하는 데만 시간복잡도 최대 O(n), 총 O(n^2)로 시간초과가 나는 경우가 있습니다.따라서 구간의 합을 O(1)안에 구해주기 위해서 다음과 같이 sum이라는 변수에 합을 저장하고, 이전의 합을 이용해 인덱스 업데이트 시 합도 같이 업데이트해주는 방식을 사용하면 전체 시간복잡도 O(n) 안에 해결할 수 있습니다.function* solve(xs, lowerBound, iMax, jMax) { let [i, j, sum] = [0, 0, 0] while (i = lowerBound) { yield sum ;[i, sum] = [i + 1, sum - xs[i]] } else { ;[j, sum] = [j + 1, sum + xs[j]] } } }참고: i와 sum과 같이 여러 값들을 한 번에 업데이트할 때 업데이트 순서에 따른 버그를 방지하기 위해서 저는 JS의 구조 분해 할당 문법을 애용하고 있습니다.주의사항iMax와 jMax가 문제에 따라 length가 될 수도 있고 length + 1이 될 수도 있습니다.

알고리즘 / 최대 힙 / JS 구현

정제 완료...!function makeMaxHeap() { const heap = [] function isValidParent(i, j) { return heap[i] >= heap[j] } function swap(i, j) { ;[heap[i], heap[j]] = [heap[j], heap[i]] } function parent(i) { return Math.floor((i - 1) / 2) } function child(i) { const [l, r] = [2 * i + 1, 2 * i + 2] if (heap[l] === undefined) { return undefined } if (heap[r] === undefined) { return l } return isValidParent(l, r) ? l : r } function push(x) { heap.push(x) const i0 = heap.length - 1 for (let [i, p] = [i0, parent(i0)]; p >= 0; [i, p] = [p, parent(p)]) { if (isValidParent(p, i)) { break } swap(i, p) } } function pop() { if (heap.length 주의사항swap 이후에는 child 함수의 결과가 바뀌기 때문에 child 변수를 미리 저장해놓고 사용해야 한다.child 함수 계산 시 heap[i] === undefined 대신 heap 길이로 계산할 경우 off-by-one error 조심

ostep / 가상화 / CPU / 원리: 제한적 직접 실행 (한글판 9장, 영문판 6장)

들어가며이 책에서는 어떤 문제를 해결하는 개념을 다룰 때 다음의 2가지로 나누어 설명하고 있습니다.저수준 기법 (mechanism)어떻게 문제를 해결할 것인지예: 어떻게 CPU 가상화를 할 것인지 -> 제한적 직접 실행고수준 정책 (policy)문제를 해결해서 무엇을 할 것인지예: 가상화한 CPU자원을 어떤 프로세스에게 할당할 것인지 -> CPU 스케줄링CPU 가상화들어가며CPU라는 자원은 시분할로 가상화하는 것이 자연스럽다.CPU 가상화 기법의 필요조건들빨라야 한다.기법: 제한적 "직접 실행"사용자 프로세스는 가상의 명령어를 해석하는 것이 아니라, 하드웨어에서 지원하는 명령어를 직접 실행한다.예를 들어서 x86 CPU에서 돌아가는 OS의 경우 x86 기계어를 직접 실행한다.일부 명령어는 사용자 프로세스가 사용할 수 없어야 한다.예: 입출력장치에 직접 접근하는 명령어는 사용자 프로세스가 아닌 커널에서만 사용할 수 있다.기법: "제한적" 직접 실행하드웨어 지원 기능: mode bit, trap 및 return-from-trap 명령어 OS의 특정 기법을 구현하기 위해서는 하드웨어가 지원하는 기능과 운영체제 소프트웨어가 협력하는 경우가 많다.mode bitmode bit은 CPU에 존재하며 mode bit의 세팅 여부에 따라 커널 모드(kernel mode)와 사용자 모드(user mode)로 나뉜다.CPU는 사용자 모드인 경우 일부 명령어들의 실행만 지원한다.지원하지 않는 명령어를 실행할 경우 interrupt가 발생하여 OS가 문제의 프로세스를 kill할 수 있다.trap, return-from-trap 명령어위와 같이 사용자 프로세스는 일부 명령어를 직접 실행하지 못하고 OS를 통해 간접적으로 실행해야 한다. 이 과정에서 사용할 수 있는 명령어들이 trap 및 return-from-trap 명령어들이다.trap 명령어kernel mode로 전환하고, 해당 trap과 관련된 커널의 코드가 실행된다.이 때 trap 0xdeadbeef와 같이 trap 명령어에 임의의 주소값을 전달할 수 있다면 사용자 프로세스가 임의의 커널 코드를 실행시킬 수 있는 큰 문제가 일어난다.따라서 trap 명령어 실행 시 실행시킬 수 있는 handler가 몇 개로 정해져 있다. 이를 trap table이라 한다. trap 0x80과 같이 trap 명령어는 index를 전달하는 방식으로 동작한다.CPU에서 trap handler를 등록하는 방법을 별도로 제공해주며, 커널은 이를 사용하여 부팅 시 trap table을 초기화한다.x86 아키텍처에서는 trap 명령어를 int라고 부르지만, 교재와 강의에서는 trap 명령어와 인터럽트를 구분해서 설명하고 있다.필자 주: 공룡책에서 시스템 호출은 소프트웨어 인터럽트 중 하나로 처리된다고 말하는 것으로 볼 때, 여기서 ostep에서 구분하고자 하는 인터럽트는 하드웨어 인터럽트로 추정됩니다.return-from-trap 명령어user mode로 전환하고 trap 명령어를 호출한 곳으로 되돌아간다.⚠ 필자 주: 인터넷에서 잠깐 찾아보았을 때 trap이라는 단어가 다른 맥락에서도 사용됨을 확인했습니다. 조사한 바로는 trap 및 여러 단어들의 용례가 사용되는 의미가 하나로 합의되지는 않았다고 합니다. 하지만 여기서도 공룡책에서도 "trap instruction"라는 용어가 일관적으로 사용되는 것으로 보았을 때 OS 공부할 때 "trap 명령어"라는 말을 사용해도 무방해 보입니다.사용자 프로세스 하나가 실행 중일 때 제어권을 가져와서 다른 사용자 프로세스로 넘기는 과정이 필요하다.예전에 사용했던 기법: 협조(cooperative) 방식사용자 프로세스가 제어권을 양보할 때까지 OS가 기다린다.문제: 사용자 프로세스가 프로그래머의 실수든 고의든 오랫동안 제어권을 양보하지 않으면 OS는 제어권을 가져올 수 없다.현재 사용하는 기법: 비협조 방식하드웨어 지원 기능: timer interruptCPU에서 일정 갯수의 클럭 실행 후 발생시키는 인터럽트timer interrupt 발생 시 제어권이 interrupt handler로 넘어가 OS가 다시 제어권을 가져올 수 있다.문맥 전환 (context switch)문맥 전환 시 저장해야 하는 데이터: 레지스터, PC, SP출처강의: https://pages.cs.wisc.edu/~remzi/Classes/537/Fall2021/Discussion/videos.html책: https://pages.cs.wisc.edu/~remzi/OSTEP/Korean/