📑 Category

[운영체제] 페이지 교체 알고리즘 - FIFO, OPT, LRU, NRU, LFU, MFU

페이지 교체 알고리즘 필요한 페이지가 메모리에 없을 때 페이지 부재(page fault)가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 한다. 이때, 물리 메모리에 빈 프레임이 존재하지 않는다면 물리 매모리 내 페이지 중 하나를 선택해서 디스크의 스왑 영역을 보내야 한다.(Swapping) 이를 페이지 교체라고 한다. 메모리 내 페이지 부재율을 최소하하기 위한 목적으로 디스크의 스왑 영역으로 보낼 페이지를 결정하는 알고리즘을 페이지 교체 알고리즘이라고 한다. FIFO(First In First Out) 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘 구현이 간단하지만 페이지의 향후 참조 가능성을 고려하지 않기 때문에 비효율적인 상황이 발생할 수 있음 들어온 시간을 저장하거나 올라..

[운영체제] 메모리 할당, 페이징(Paging)과 세그멘테이션(Segmentation)

메모리 할당 시작 메모리 위치, 메모리 할당 크기를 기반으로 메모리에 프로그램 할당 연속 할당과 불연속 할당으로 나뉨 1. 연속 할당 메모리에 연속적으로 공간 할당 물리 메모리를 다수의 공간으로 분할하여 하나의 분할 공간에 하나의 프로세스가 적재되도록 함 고정 분할 방식과 가변 분할 방식으로 나뉨 1-1) 고정 분할 방식(Fixed Partition Allocation) 메모리 공간을 미리 분할하여 고정된 크기로 나누어 관리하는 방식 분할 크기는 모두 동일할 수도 있고 다를 수도 있음 분할된 공간은 영구적으로 고정되기 때문에 메모리에 올릴 수 있는 프로그램의 수 및 크기가 제한적이고 융통성이 떨어짐 내부 단편화(내부 조각)와 외부 단편화(외부 조각) 문제가 발생할 수 있음 1-2) 가변 분할 방식(Va..

[운영체제] 내부 단편화(Internal Fragmentation)와 외부 단편화(External Fragmentation)

💡단편화(Fragmentation)란? 메모리 공간이 부분으로 나뉘어서 충분히 사용 가능한 메모리가 남아있지만, 프로세스 할당이 불가능한 상태 내부 단편화(Internal Fragmentation) 프로세스가 필요한 양보다 더 큰 메모리가 할당되어 메모리 공간 낭비 발생 프로세스는 실제로 사용하지 않는 메모리 영역을 가지고 있게 됨 Ex) 100MB의 메모리에 80MB 크기의 프로세스 적재 다음과 같은 20MB의 내부 단편화 발생 (해당 메모리 사용 불가) 외부 단편화(External Fragmentation) 남아있는 총 메모리 공간이 프로세스가 요청한 메모리 공간보다 크지만, 남아있는 공간이 연속적이지 않아 사용할 수 없는 경우 쪼개진 메모리 공간을 사용할 수 없어 메모리 낭비 발생 프로세스들이 메모..

[운영체제] 뮤텍스(Mutex)와 세마포어(Semaphore) - 동기화

교착 상태: https://zu-techlog.tistory.com/128 [운영체제] 교착 상태 (Dead Lock, 데드락) 교착 상태(Dead Lock, 데드락) 두 개 이상의 프로세스들이 서로가 가진 자원을 무한정 기다리며 멈추어 있는 상태 프로세스 A는 자원 1을 가지고서 자원 2를 요구, 프로세스 B는 자원 2를 가지면서 자 zu-techlog.tistory.com 임계 영역과 경쟁 상태: https://zu-techlog.tistory.com/129 [운영체제] 임계 영역(Critical Section)과 경쟁 상태(Race Condition) 임계 영역(Critical Section) 둘 이상의 프로세스 또는 스레드가 공유 자원에 접근할 때 순서 등의 이유로 결과가 달라질 수 있는 코드 영..

[자료구조] 단순/원형/이중 연결리스트(Linked List) 구현 - 파이썬(Python)

연결리스트(Linked List) 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장하는 선형 자료구조 연결리스트는 Node로 구성되어 있고, Node 안에는 Data와 Link(Next)로 구성 Data: 데이터 값 저장 Link(Next): 다음 노드를 가리킴 장점 데이터 추가, 삭제에 유리 배열: 시간복잡도 O(n) 연결리스트: 시간복잡도 O(1) 공간복잡도 측면에서 유리 (배열처럼 연속된 공간을 할당하지 않고 필요 시에만 메모리를 동적 할당하기 때문) 메모리 누수 X 유연한 메모리 관리 단점 데이터 탐색 시 불리 (데이터의 논리적 저장 순서와 물리적 저장 순서가 일치하지 않아 인덱스 접근이 아닌 전체를 순회해야 하기 때문) 배열: 시간복잡도 O(1) 연결리스트: 시간복잡도 O..

[운영체제] 임계 영역(Critical Section)과 경쟁 상태(Race Condition)

임계 영역(Critical Section) 둘 이상의 프로세스 또는 스레드가 공유 자원에 접근할 때 순서 등의 이유로 결과가 달라질 수 있는 코드 영역 한 번에 하나의 프로세스나 스레드만 접근할 수 있는 코드 영역 한 프로세스가 critical section에 접근하고자 했지만 다른 프로세스가 이미 해당 영역에서 작업을 하고 있다면 entry section에서 대기하고 있다가 exit section으로부터 작업 종료 신호를 받으면 critical section에 진입하도록 동기화 필요 상호 배제(Mutual Exclusion): 한 프로세스가 임계 영역에서 작업 중이라면 다른 프로세스가 접근하지 못하도록 통제가 필요함 진행(Progress): 아무도 임계 영역에 진입하지 못하면 안되며 아무도 임계영역에 ..

[운영체제] 교착 상태 (Dead Lock, 데드락)

교착 상태(Dead Lock, 데드락) 두 개 이상의 프로세스들이 서로가 가진 자원을 무한정 기다리며 멈추어 있는 상태 프로세스 A는 자원 1을 가지고서 자원 2를 요구, 프로세스 B는 자원 2를 가지면서 자원 1을 요구 교착 상태 발생 조건 상호 배제(Mutual Exclusion) 한번에 하나의 프로세스만이 공유 자원을 사용할 수 있어야 함 점유와 대기(Hold and Wait) 모든 프로세스는 최소 하나의 자원을 점유하면서 다른 프로세스가 가지고 있는 자원을 기다리고 있어야 함 비선점(Non Preemption) 다른 프로세스가 자신에게 할당된 자원을 모두 사용해 반환할 때까지 강제로 뺏어올 수 없어야 함 환형 대기(Circular Wait) 공유 자원과 해당 자원을 사용하기 위해 대기하는 프로세스..

[운영체제] CPU 스케줄링 알고리즘 - 비선점형, 선점형

💡 CPU 스케줄링 척도 1. CPU 이용률(CPU utilization): 시간당 CPU를 사용한 시간의 비율 2. 처리율(Throughput): 시간당 처리한 작업의 비율 3. 반환시간(Turnaround Time): 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간 4. 대기시간(Waiting Time): 대기열에 들어와 CPU를 할당받기까지 기다린 시간 5. 반응시간(Response Time): 대기열에서 처음으로 CPU를 얻을 때까지 걸린 시간 -> CPU 이용률과 처리율은 극대화하는 것이 좋고 반환시간, 대기시간, 반응시간은 줄이는 것이 좋다 1. CPU 스케줄링 알고리즘 - 비선점형 비선점형 방식(non-preemptive)은 프로세스가 스스로 CPU 소유권을 ..