GaeunLee blog

Page Fault Frequency (residence bit = 0)가 높을 수록 가상메모리의 장점이 줄어든다. → 커널의 개입을 통한 디스크와의 입출력을 요구 (프로세스 대기) 9.1 하드웨어의 사용 mapping에 걸리는 시간을 최소화 = 가상메모리의 성능 UP 추가 비용을 들여 하드웨어를 장착(ex. TLB) 📌 페이지를 관리하기 위한 정보 참조 비트 : 해당 페이지가 변경 없이 단순 참조 갱신 비트 : 해당 페이지의 내용 변경 9.2 관리 기법 적재 정책 실행에 필요한 페이지를 언제 적재할지 결정하는 정책 요구 적재(Demanding Fetch) 페이지가 참조될 때 적재하는 기법 장점 : 메모리에 관한 오버헤드가 없음 단점 : 적재될 때까지 해당 프로세스를 대기로 만드는 문맥교환과 디스크 입출..

8.1 가상메모리 프로그램을 작은 조각으로 나누어 적재한다. 사실은 제한적인 크기지만 큰 메모리가 있는 것처럼 여겨지게 한다. 가상메모리의 관리 : 한 번에 전송되는 단위(블록) 페이징 세그멘테이션 시스템 조각의 크기가 같음 (페이지) 조각의 크기가 다름 (세그먼트) 주소의 사상(mapping) : 가상 주소를 실 주소로 변환해주는 작업 가상주소: 프로그램에서 참조하는 주소 실제주소: 메모리상 주소 주소 사용 주소의 지정 컴파일 시에 일어남: 프로그램이 실행될 때 참조하는 주소가 컴파일 시 지정 참조 주소 = 실 주소 프로그램은 항상 메모리의 지정된 곳으로 적재(고정분할, 절대로더) 재배치: 메모리에서의 위치를 적재될 때마다 바꿈 프로그램이 통째로 연속적으로 메모리에 적재 프로그램의 첫 번째 줄을 0, ..

7.1 메모리의 구성 다중 프로그래밍의 정도(Multiprogramming Degree) degree란 메모리에 있는 프로세스의 개수 메모리의 분할 각 프로세스에게 메모리를 얼마나 할당 메모리의 분할 시기 고정 분할(fixed) / 정적 분할(static) 가변 분할(variable) / 동적 분할(dynamic) 메모리 할당 연속적 or 비연속적 7.2 메모리의 관리 적재 기법 요구 적재(demand fetch) 주로 사용 예상 적재(Anticipatory fetch) 배치 기법 적합 기법(fit) 교체 기법 메모리 공간이 부족할 경우 새로 적재돼야 할 프로세스를 위해 이미 메모리에 있는 프로세스를 골라 빼내서 공간 확보 할당 기법 프로세스에게 얼마나 메모리를 줄지 결정 7.3 단일 프로그래밍 한 번에..

6.1 교착 상태 둘 이상의 프로세스가 각자 가지고 있던 자원을 보유한 채로 외부적 조치가 없는 한 영원히 그 상태에서 기다리고 있는 상황 근본 원인 시스템이 가지고 있는 한정적인 자원보다 사용하고자 하는 프로세스들의 요청이 더 많아서 생김 문제점 프로세스들이 더 이상 실행되지 못하여 사용자들에게 응답해 주지 못한다. 보유된 자원들이 교착 상태에서 벗어나기 전까지 전혀 활용되지 못한다. 자원 (Resource) 선점 가능(Preemptible) 선점 불가능(Nonpreemptible) 운영체제에 의해 사용 도중 뺏길 수 있음 선점이 불가능(뺏길 시 정상 진행 포기해야함) 공유 가능 자원(Sharable) 배타적 사용 자원(Exclusive) 동시에 사용가능 한번에 하나씩 사용 공유가능 프로그램, 공유 데..

5.1 병행 프로세스 병행(concurrent): 메모리에 다수의 프로세스가 같이 존재한다는 것 처리기(CPU)의 개수 상관 X 논리적 concurrent - 단일 처리 (실제로는 parallel 아님) 물리적 concurrent - 다중 처리(진정한 parallel) 병렬(Parallel): 다중처리 시스템의 경우 여러개의 프로세스가 동시에 병렬로 실행 병행(concurrent)전제 💡 병행 프로세스 사이의 비동기적(Asynchronous) 다른 프로세스들이 어떤 상태에 있는지, 어떤 자원을 가지고 있는지, 어디까지 실행됐는지 전혀 모름. 독립적이다. 병행 프로세스 사이의 Rule: 공유된 자원에 대해 한 번에 한 프로세스만이 접근하도록 하고, 해당 자원에 대해 의도했던 실행을 완료하도록 보장 5.2 ..

4.1 스케줄링의 단계 4.2 스케줄링의 목적과 기준 사용자 관점 응답 시간(reponse time) : 대화형 시스템에서 프로세스의 요청에 시스템이 최초 출력을 하는 시간 인터렉티브시스템 반환 시간(turn around time) : 일괄 처리의 경우, 요청으로부터 결과를 받는데 걸린 시간 배치시스템(일괄처리 시스템) 예측가능성 : 언제 끝날지 예측가능한가? 시스템 관점 처리량 : 단위 시간 동안 완료한 프로세스의 개수 ex. 인터렉티브시스템 활용도 : 주어진 시간 동안 특정 자원이 가동된 시간의 비율 ex. 배치시스템(일괄처리 시스템) 공평성 : CPU사용시간 공평하게 나누었나? 스케줄링 정책을 만들 때 고려해야할 기준 연산위주(CPU- bound) /입출력위주(I/O-bound)(비중높다) 응답 시..

3.1 프로세스란 무엇일까? 프로세스란 프로세스 = 잡 = 태스크 =/= 스레드! CPU 할당받게 되는 단위 & 자신에게 주어진 자원들의 소유자 수행중인 프로그램 수행 중 ⇒ 프로그램, 데이터, 환경 포함 (실행, 보류 모두 포함) 프로그램과 데이터를 기본으로 정상적인 실행을 위해 필요한 환경을 시스템에서 부여받은 능동적인 존재 +)프로세서는 하드웨어를 의미 (CPU) 프로세스 제어 블록 프로세스에 대한 모든 정보를 가진 자료구조 프로세스번호 (PID) 상태(status) 프로그램 우선순위 프로그램 카운터 (PC) 메모리 포인터 = 메모리의 자리, 시작 주소 문맥 데이터 = 인터럽트 발생시 문맥교환하기위한 파일들의 정보 계정정보 입출력 정보 프로세스의 상태 변화 보류 상태가 필요한 이유 보류 준비 = 메..

1.1 OS란 컴퓨터의 여러 응용프로그램 설치 여러 장치 효율적으로 작동 사용자가 컴퓨터를 손쉽게 이용할 수 있게 해줌 사용자 인터페이스, 자원 관리를 위한 프로그램의 집합 1.2 OS 역사 1세대 운영체제 일괄 처리 시스템 (Single-Stream Batch Processing System) 다수개의 프로그램을 읽어 저장, 한 번에 한 개씩의 프로그램을 실행 한꺼번에 여러 개 준비시켜, 다음 작업을 자연스럽게 연결해 실행 작업이 끝날 때까지 사용자의 중간개입 허용되지 않음 배치 한 개의 작업이 시작되면 그 일이 완전히 끝날때까지 다른 작업은 기다려야 함 2세대 운영체제 다중 프로그래밍 시스템 다수의 작업이 같이 주기억장치에 넣어서, CPU가 바로 다음작업을 하도록 함 다중처리 시스템 여러 개의 처리장..

disjoint set(분리 집합)이란? 분리 집합: 서로 "중복되지 않는 부분 집합들"로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조 집합을 구현하는 방법은 다양하게 있지만, 보통 트리를 이용해서 구현한다.4 분리 집합의 구현 (tree) - 트리 하나가 각각 한 개의 집합을 의미한다. - 자식이 부모를 가리키는 방향으로 저장한다. - 루트 노드의 부모는 자기 자신을 가리킨다. 분리 집합의 3가지 연산 1. Make-set(x) : x를 유일한 원소로 하는 집합을 생성한다. 2. Find(x) : x가 속한 집합의 대표값(root node)을 반환한다. ➔ 서로 같은 집합인지 다른 집합인지 판단할 때에 쓴다. 3. Union(x, y) : x가 속한 집합과 y가 속한 집합을 병합한다. 3가..

1. DFS, BFS의 기본 개념 깊이 우선 탐색(DFS) 탐색을 하고자 하는 그래프상에서, 깊이를 우선적으로 탐색하는 기법 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다. 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있다. *참고 탐색에서는 중복된 상태를 막기 위하여 2개의 리스트를 사용한다. OPEN 리스트: 확장은 되었으나 아직 탐색하지 않은 상태들이 들어있는 리스트 CLOSED 리스트: 탐색이 끝난 상태들이 들어있는 리스트 closed 리스트: 방문 완료를 나타내는 배열(visited) 사용 open 리스트: 탐색할 대상을 stack에 넣어서 사용 (혹은, 재귀를 활용해서 구현) void dfs(int node) { visited[node] = true; cou..