본문 바로가기

CS101

[DB] B-Tree (Balanced Tree): 데이터베이스 인덱스 저장 방식 데이터베이스에서 인덱스를 저장하는 자료구조로 B-Tree를 주로 씁니다. B-Tree의 개념과 조건에 대해서 알아봅니다. [ Contents ] 1. B-Tree (Balanced Tree) 한쪽으로 치우치지 않도록, 모든 leaf node가 같은 level를 유지하는 트리 B-Tree는 Binary Tree(이진 트리)의 준말이 아닙니다. Balanced(균형잡힌) Tree로서, 한쪽으로 치우치지 않고 좌우가 균등한 트리를 뜻합니다. Tree 형태의 탐색 시간은 O(logN)의 시간복잡도를 갖지만, 극도로 치우쳐져 일자로 나열된 트리는 O(N)의 시간복잡도를 가질수도 있습니다. 따라서 트리의 탐색 효율을 보장하려면 좌우가 균등해야 합니다. 2. B-Tree가 되기위한 조건 1. 모든 노드들은 최대 m개.. 2023. 8. 7.
[SW공학] 기능점수(Function Points)의 개념과 산정방식, 예시 SW 개발단가를 주로 LoC(Line of Code) 기준으로 산정하곤 합니다. 단순히 코드량을 기준으로 보수를 측정하는 방식으로, 하청을 받는 중소기업 개발자를 '단순 코더'로 만든 주범이기도 합니다. 그래서 간혹 클린코드와는 전혀 거리가 먼 '복붙 코드'나 '하드 코딩'을 보기도 합니다. 반면 기능점수는 '기능별 난이도'를 고려해서 개발단가를 산정하는 방식입니다. 이에 대한 설명과 산정 방식을 알아보도록 하겠습니다. [ Contents ] 1. 기능점수 (Function Points) 소프트웨어의 각 기능별로 가중치를 부여한 산출방식 기능별로 구현 난이도는 다르므로, 가중치를 두어 개발단가(개발 규모)를 산정하는 방식입니다. 지금도 단순 명료한 LoC 방식을 많이 사용하지만, 최근에는 기능점수(FP).. 2023. 8. 4.
[SW공학] 작업 네트워크의 임계경로[CPM]: 가장 늦게 시작하는 날, 가장 빨리 시작하는 날, 여유 기간 구하는 방법 CPM은 SW공학에서 프로젝트를 효율적으로 관리하는 기법 중 하나입니다. 네트워크 구조로 작업 간 선후체계를 표시하고, 임계경로를 구해서 전체 프로젝트 일정을 조율합니다. 이 글에서는 CPM에서 작업 네트워크를 그리고, 임계경로와 각 작업별 최소 시작 시간(Earliest Start Time), 최대 종료 시간(Latest Finish Time), 여유 시간(Slack Time)를 구해보는 실습을 해보겠습니다. [ Contents ] 1. CPM(Critical Path Method) 작업별 선후체계를 그래프로 나타낸 작업 네트워크 작업 작업 내용 선행 작업 소요 기간 (일) S 시작 - - A 인터뷰 S 8 B 포커스그룹 S 15 C 설문조사 S 10 D 리팩토링 및 유지보수 S 25 E 기획설계 A,.. 2023. 8. 3.
[OS] 교착상태 회복기법: 프로세스 종료/회복, 자원 선점 (ft. 희생자 선택의 원칙) 교착상태는 작업에 필요한 자원을 얻지 못해 더 이상 진행하지 못하는 상황을 말합니다. 일명 Dead Lock이라고 불리는 이 현상을 타개하는 회복 기법에 대해서 알아봅니다. [ Contents ] 1. 프로세스 종료 (Process Termination) 1) 교착상태에 빠진 프로세스 일괄 종료 오류가 났을 때 컴퓨터를 재부팅하는 것과 비슷합니다. 가장 간단한 방법으로, 해당 프로세스의 자원을 모두 반환시켜서 다른 프로세스가 자원을 이용할 수 있도록 합니다. 하지만 중요 프로세스가 포함된 경우에는 일괄 종료가 어렵습니다. 또한 진행 중이던 프로세스가 롤백되므로, 작업 효율에도 영향이 있습니다. 2) 교착상태가 해결될 때까지 하나씩 프로세스 종료 오류가 났을 때 작업관리자에서 하나씩 프로그램을 강제 종료시.. 2023. 8. 2.
[OS] 교착상태 회피방법: 은행원 알고리즘(Banker's Algorithm) 프로세스가 필요한 자원을 얻지 못해 무한정 대기하는 상황을 교착상태라고 합니다. 이러한 교착상태가 생기지 않도록 회피하는 방법인 '은행원 알고리즘'에 대해 알아봅니다. [ Contents ] 1. 은행원 알고리즘 은행에서 돈을 빌려주듯이, 운영체제가 자원을 할당할 때 요구한 양만큼 차례차례 빌려주는 알고리즘 은행원 알고리즘은 교착상태가 되지 않도록 회피하는 자원 할당 방식입니다. 교착상태는 대체로 Hold and Wait 상태로부터 기인합니다. 따라서 프로세스의 요구 자원을 모두 챙겨주고 이를 반환시키는 걸 목표로 합니다. 은행으로 비유하자면, 전액 빌려줄 수 있는 대출부터 차근차근 해주는 프로세스입니다. 만약 일부만 대출해줄 경우, 잔금을 받아낼 때까지 갚지 않을 테니까요. 2023.07.31 - [C.. 2023. 8. 2.
[OS] 교착상태(Dead Lock)의 정의와 발생조건 4가지: 상호배제, 점유와 대기, 비선점, 환형대기 절대 풀리지 않는 죽음의 대기상태를 Dead Lock, 교착상태라고 합니다. 이 교착상태가 생기는 4가지 조건에 대해 알아봅니다. [ Contents ] 1. 교착상태 (Dead Lock) 프로세스가 더 이상 진행되지 않고 (필요한 자원을) 무한정 대기하는 상태 교착상태는 작업에 필요한 자원을 얻지 못해 무한정 대기하는 상태를 말합니다. 대체로 일부 자원은 확보했으나 나머지 자원을 받지 못해서 발생합니다. 젓가락 예시를 많이 들며, 다들 젓가락 1개씩만 갖고 있어서 식사를 못하는 상태를 '교착상태'로 비유하곤 합니다. 젓가락 1개를 더 얻어야 하지만, 이미 다른 사람들이 1개씩 다 가져가서 없죠. 그렇다고 남의 젓가락을 뺏을수도 없고, 내가 얻은 젓가락을 포기할 수도 없습니다. 그래서 첨예한 대치상태로 .. 2023. 7. 31.
[OS] 병행성 제어: 뮤텍스(Mutex)와 세마포어(Semaphore) 공유 자원을 동시에 여러 프로세스가 사용하는 것을 통제하기 위해, '상호배제 기법'을 사용합니다. 운영체제에서 사용되는 상호배제 기법 중, 가장 일반적인 뮤텍스와 세마포어에 대해서 알아봅니다. [ Contents ] 1. 뮤텍스 (Mutex) 단일 프로세스만 사용할 수 있는 공유 자원의 이용 여부 단순한 상호배제 기법입니다. 공유자원을 사용할 때 뮤텍스에 '사용중' 표기를 하고, 다 쓰고나면 '사용가능' 표기를 남깁니다. 만약 접근하려는 공유자원이 사용중이라면 기다려야 겠죠. 2. 세마포어 (Semaphore) 현재 사용가능한 공유자원의 수 세마포어는 공유자원이 여러 개일 때 사용합니다. 공유자원을 사용할 때 세마포어를 -1하고, 사용이 끝나면 +1을 합니다. 접근하려는 공유자원의 세마포어가 0이라면, .. 2023. 7. 24.
[OS] 상호배제(Mutual Exclusion)와 임계구역(Critical Section) CPU는 다양한 작업을 번갈아가며 수행합니다. (멀티태스킹) 병렬 작업에서 생길 수 있는 문제를 해결하기 위한 '상호배제 기법'과 '임계구역'에 대해서 알아보겠습니다. [ Contents ] 1. 상호배제 (Mutual Exclusion) 두 개 이상의 프로세스가 공유 자원에 동시에 접근하면 못하도록 방지 병렬 작업 시, 가장 큰 문제는 '데이터 동기화'입니다. 동일한 데이터를 동시에 읽기/쓰기 작업을 하면 데이터 무결성이 침해될 수 밖에 없습니다. 수정되기 전 데이터를 열람하거나, 같이 수정해서 덮어씌워지기도 합니다. (예를 들어, git이나 svn과 같은 형상관리 시스템에서 충돌[conflict]나면 머리 아프죠...) 그래서 운영체제에서는 공유자원을 상호 베타적으로 이용하도록 조치하며, 이는 DB에.. 2023. 7. 24.
[OS] CPU 스케줄링 기법: FCFS, SJF, SRT, 라운드 로빈, Multi Level (Feedback) Queue CPU 스케줄링 기법에는 선점형과 비선점형이 있습니다. 어떠한 특성인지 살펴보고, 특성별 스케줄링 기법에 대해서도 알아보겠습니다. [ Contents ] 1. 스케줄러 구분 1) 선점형 (Preemptive) 다른 프로세스가 점유 중인 CPU를 사용가능 빠른 응답이나 모바일, 대화식 시분할 시스템에 적합한 방식입니다. 하지만 CPU를 교대로 사용하는 과정에서 오버헤드(Overhead)가 발생하는 단점이 있습니다. 이를 Context Switching이라고 합니다. 작업을 번갈아가며 하려면, 이전 작업의 맥락을 파악하는 시간이 필요하겠죠. CPU도 작업을 교체할 때 현재 진행하고 있는 작업의 상태를 저장하고, 다음 진행할 작업의 상태를 읽고 준비하는 시간이 소요됩니다. 2) 비선점형 (Non-preempt.. 2023. 7. 21.

티스토리툴바