전체 글
-
[Algorithms/python] Union Find (Disjoint Set, 서로소 집합)Data Structure & Algorithms 2024. 4. 2. 20:16
[Algorithms/python] Union Find (Disjoint Set, 서로소 집합) Union Find (Disjoint Set, 서로소 집합) Union Find : 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘 (서로소 집합을 찾아내는 알고리즘) 노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find연산으로 이루어짐 코테 활용 Union Find를 활용하여 양방향 그래프에서 cycle 여부를 판단할 수 있다. 각 간선의 두 노드의 루트 노드를 확인한다. 루트노드가 서로 다르면 union 연산 실행 루트노드가 서로 같으면 cycle 발생한 것 1. 개념 및 기본 원리 1) init 연산 arr = [i for i in range(N+1)] 2) Union 연산 def unio..
-
[Algorithms/python] 위상 정렬(Topological Sort)Data Structure & Algorithms 2024. 4. 2. 20:07
[Algorithms/python] 위상 정렬(Topological Sort) DAG : Directed Acyclic Graph 사이클이 없는 방향 그래프 → 일의 선후 관계 등을 표현할 때 사용하기 용이함 Topological Sort란 DAG에서 그래프의 방향성을 거스르지 않고 정점을 나열하는 정렬방법 Topological Sort의 방법 : 시간복잡도 : O(V+E) 그래프 그리기, 진입 차수 세기 가장 먼저 진입차수가 0인 노드들 queue에 넣기 queue를 돌며 해당 노드와 연결되어 있는 다른 노드들의 진입 차수를 하나씩 낮춰주고, 이 진입 차수가 0이 되었다면 또 queue에 삽입 Directed Acyclic Graph (DAG) : 순환(Cycle)을 가지지 않는 "방향" 그래프 위상 ..
-
2024 운영체제 정리 - 6. 메모리 관리와 Virtual MemoryOperating System 2024. 4. 2. 19:19
2024 운영체제 정리 - 6. 메모리 관리와 Virtual Memory 1. 운영체제란 2. Process & Thread 3. IPC 4. CPU Scheduling 5. Synchronization 6. 메모리 관리와 Virtual Memory 지금까지 운영체제가 CPU에서 어떻게 프로세스를 스케줄링하는지에 대해서 살펴보았다 이제부터는 운영체제가 메모리에 프로세스를 어떻게 할당하고 관리하는지를 살펴보겠다 스케줄러 복습 장기 스케줄러 (Job Scheduler) : 어떤 프로세스를 Ready Queue로 옮길지 결정 New -> Ready 많은 프로세스 중에서 어떤 것을 메모리에 올릴지 (Ready Queue) 하드디스크에 올릴지 결정 메모리와 디스크 사이의 스케줄링 담당 중기 스케줄러 (Swappe..
-
2024 운영체제 정리 - 5. Synchronization & DeadlockOperating System 2024. 4. 2. 19:19
2024 운영체제 정리 - 5. Synchronization & Deadlock 1. 운영체제란 2. Process & Thread 3. IPC 4. CPU Scheduling 5. Synchronization & Deadlock 6. 메모리 관리와 Virtual Memory Race Condition 문제 동시다발적으로 수행되는 쓰레드/프로세스에서, 서로 다른 쓰레드/프로세스가 같은 메모리 영역을 공유하기 때문에 여러 쓰레드/프로세스가 동일한 자원에 동시에 접근할 때 발생하는 문제 발생 이를 해결하기 위한 방법 - Synchronization! 이때, 동시에 접근하게 되는 공동의 자원을 공유자원, shared resource라고 한다 이 공유 자원은 전역 변수, 파일, 입출력 장치, 보조기억 장치 등이..
-
2024 운영체제 정리 - 4. CPU SchedulingOperating System 2024. 4. 2. 19:17
2024 운영체제 정리 - 4. CPU Scheduling 1. 운영체제란 2. Process & Thread 3. IPC 4. CPU Scheduling 5. Synchronization 6. Virtual Memory Process Status New Ready Running Waiting Terminated Scheduling Queue 프로세스들의 프로세스 제어 블록(PCB)이 링크드 리스트 형태로 연결 리스트의 첫 번째와 마지막 PCB를 가리키는 포인터를 포함 Job Queue : 시스템 상에 있는 모든 프로세스들 Ready Queue : memory에 올라와 있으면서 CPU에 할당되기를 기다리는 프로세스들의 집합 Device Queue (Wait Queue) : 입출력 장치에서 처리되기를 기..
-
2024 운영체제 정리 - 3. IPCOperating System 2024. 4. 2. 19:16
2024 운영체제 정리 - 3. IPC 1. 운영체제란2. Process & Thread3. IPC4. CPU Scheduling 5. Synchronization6. Virtual Memory IPC와 관련된 코드적인 내용은 아래 링크에 더 자세히 설명해두었다 https://asidefine.tistory.com/94 시스템 프로그래밍 실습 8주차 : IPC시스템 프로그래밍 실습 8주차 : IPC [목차] - IPC - Open Files in Kernel - I/O Redirection - Pipes - Anonymous Pipe - Named Pipe (FIFOs) IPC란? IPC = Inter Process Communication..
-
2024 운영체제 정리 - 2. Process & ThreadOperating System 2024. 4. 2. 19:15
2024 운영체제 정리 - 2. Process & Thread 1. 운영체제란 2. Process & Thread 3. IPC 4. CPU Scheduling 5. Synchronization 6. Virtual Memory Process Process란 ? 프로그램이 실행되기 위해 memory에 적재되어 CPU에 의해 실행되는 작업의 단위 프로세스는 크게 1) Logical Control Flow, 2) Private Address Space라는 특징을 가지고 있다. 1) Logical Control Flow 마치 CPU를 혼자 쓰는 것처럼 보인다는 특징과 2) Private Address Space 한 프로세스당 하나의 메모리 영역를 할당 받는 것을 의미한다 위의 특징은 전 포스팅에서 설명한 메모리..
-
2024 운영체제 정리 - 1. 운영체제란Operating System 2024. 4. 2. 19:14
2024 운영체제 정리 - 1. 운영체제란 1. 운영체제란 2. Process & Thread 3. IPC 4. CPU Scheduling 5. Synchronization 6. Virtual Memory 운영체제란 ? 실행할 프로그램 또는 프로세스들을 1) CPU에 효율적으로 스케쥴링하며, 2) 메모리에 할당하는 역할을 하는 것 Linux, MacOS, Windows 등이 있음 메모리는 주로 1) 커널 영역과, 2) 사용자 영역으로 나뉘어지는데, 운영 체제는 여기서 커널 영역에 위치하여 사용자 영역에 있는 실행 프로그램을 관리한다 CPU는 1) 커널 모드와 2) 사용자 모드로 명령어를 실행하는데, 커널 모드에서는 하드웨어에 저장된 자원들을 직접 접근할 수 있으며 사용자 모드는 불가능하다 그래서 사용자 ..