[CS] 페이지 교체 알고리즘

📌 페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시, 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법 ( → 메모리가 꽉 찼을 때 어떤 페이지를 스왑 영역으로 내보낼지 결정하는 알고리즘) 🧷 프레임 : 물리 메모리를 일정한 크기로 나눈 블록 🧷 페이지 : 가상 메모리를 일정한 크기로 나눈 블록 ▶️ 페이지 교체 알고리즘의 종류 1️⃣ FIFO(First In First Out) 알고리즘 : 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘 구현이 간단하지만 성능은 좋지 않은 편 들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장할 수 있음 Belady’s Anomaly 현상이 발생할 수 있음 🔑 Belady’s Anomaly :..

• format_list_bulleted CS/OS
• · 2024. 3. 1.
• textsms

[CS] 페이징과 세그멘테이션

👩🏻‍💻 페이징 (Paging) 📌 프로세스를 일정한 크기의 페이지로 분할해서 메모리에 적재하는 방식 페이지 : 고정 사이즈의 가상 메모리 내 프로세스 조각 프레임 : 페이지 크기와 같은 주 기억 장치의 메모리 조각 → 하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 한다는 제약을 없애는 메모리 관리 방법 ▶️ 페이징 테이블 (Paging Table) → 페이징 테이블의 매핑 물리 메모리는 고정 크기의 프레임으로, 가상 메모리는 고정크기의 페이지로 분리되어 있음 개별 페이지는 순서에 상관 없이 물리 메모리에 있는 프레임에 매핑되어 저장 → 즉, 모든 프로세스는 하나의 페이징 테이블을 가지고 있으며, 여기에는 메인 메모리에 적재되어 있는 페이지 번호와 해당 페이지가 위치한 메인 메모리의 시작 주소가 ..

• format_list_bulleted CS/OS
• · 2024. 3. 1.
• textsms

[CS] 세마포어(Semaphore) & 뮤텍스(Mutex)

🔑 공유자원을 안전하게 관리하기위한 방법인 상호배제(Mutual Exclusion) - 상호배제란 ? : 어떤 프로세스가 임계 영역을 수행 중이면 다른 모든 프로세스들은 그 임계 영역에 들어가지 못하게 막음 → 세마포어와 뮤텍스는 이를 위해 고안된 기법 📌 공유 자원에 대하여 한 번에 하나의 프로세스만이 이에 접근할 수 있도록 통제해야하는데, 그러한 통제가 필요한 영역을 임계영역이라고 부름 👩🏻‍💻 세마포어(Semaphore) 📌 - 정수값을 갖는 변수이자 자원의 갯수. - 동기화 기법 중 추상적인 방법. 세마포어는 여러 프로세스들에 의해 공유되는 변수로 정의 → 이 변수는 오직 wait과 signal이라는 연산에 의해서만 접근이 가능 wait : 세마포어의 수를 1줄임. 0이되면 lock. signal..

• format_list_bulleted CS/OS
• · 2024. 2. 25.
• textsms

[CS] 경쟁 상태(Race Condition)

📌 공유 자원에 대해 여러 프로세스가 동시에 접근을 시도할 때, 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태 → 공유 자원에 여러 프로세스가 동시에 접근할 때 자료의 일관성을 해치는 결과가 나타날 수 있음 ▶️ 발생하는 경우 커널 코드 실행 중에 인터럽트가 발생할 경우 문제점 : 커널모드에서 데이터를 로드해 작업을 수행하다가 인터럽트가 발생해 같은 데이터를 조작하는 경우 해결 : 커널모드에서 작업을 수행하는 동안 인터럽트를 disable시켜 CPU제어권을 가져가지 못하도록 함 프로세스가 ‘system call’을 하여 커널모드로 진입하고 작업을 수행하는 도중 문맥 교환이 발생할 때 문제점 : 프로세스 1이 커널모드에서 데이터를 조작하던 도중 시간이 초과되어 CPU제어권이 프로세스 2로 넘어가 ..

• format_list_bulleted CS/OS
• · 2024. 2. 25.
• textsms

[백준] 2504 괄호의 값

문제링크 : https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class BJ2504 { public static void main(String[] args) throws IOException { BufferedReader..

• format_list_bulleted Algorithm/Java
• · 2024. 2. 22.
• textsms

[백준] 2258 정육점

문제링크 : https://www.acmicpc.net/problem/2258 2258번: 정육점 첫째 줄에 두 정수 N(1 ≤ N ≤ 100,000), M(1 ≤ M ≤ 2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나 www.acmicpc.net 코드 import java.io.*; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; public class Main { static int n, m; public static void main(String[] args) throws IOE..

• format_list_bulleted Algorithm/Java
• · 2024. 2. 17.
• textsms