OS15 메모리 관리_Demand paging, Page replacement algorithms(FCFS, LRU, LRU Approximation(NRU), LFU, MFU) Paging Paging은 logical memory를 physical memory로 mapping 하는 여러 방법 중 하나입니다. Logical memory를 같은 크기의 page로, physical memory를 page와 같은 크기의 frame으로 나눈 뒤 page를 특정 frame에 할당하여 이를 page table에 기록합니다. Page table의 크기는 매우 커서 main memory에 저장 해야 하는데, CPU가 명령을 수행할 때마다 메모리에 접근하기에는 overhead가 크므로 TLB(일종의 캐시)에 자주 참조될 것으로 예상되는 page에 대한 정보를 저장하여 사용합니다. (Paging에 대한 자세한 설명을 읽어보고 싶으신 분은 여기로) Demand Paging 그렇다면, 프로그램이 로드.. 2022. 6. 21. 메모리 관리_Mapping(Contiguous allocation, Paging, Segmentation) 지난 포스팅에서는 logical memory를 physical memory에 할당하고 physical address를 확정하는 시점에 대해 다루었습니다. Compile time, Load time, Execution time 중에서 현재 사용되고 있는 방식은 Execution time 입니다. 프로세스의 코드 라인이 실행이 될 때 logical memory를 physical memory에 할당하고, 이를 참조할 때마다 MMU가 logical address를 physical address로 변환합니다. 그렇다면, logical memory를 physical memory에 어떻게 할당할 수 있을까요? 본 포스팅에서는 logical memory와 physical memory를 mapping 하는 방법에 대해 .. 2022. 6. 16. 메모리 관리_Address binding(Compile time, Load time, Execution time) Symbolic Address / Logical Address / Physical Address 우리는 프로그램을 작성할 때, 변수명과 함수명을 통해 값에 접근합니다. 값에 접근하기 위해 사용되는 변수와 함수 이름을 Symbolic Address 라고 부릅니다. 이렇게 작성한 프로그램은 컴파일이 되면서 독자적인 공간을 가지게 됩니다. 이를 logical memory라고 하며, 가상의 공간이므로 virtual memory 라고도 불립니다. 일반적으로 logical memory는 0번지 부터 시작하여 상대적 주소로 표현되고, CPU는 logical address를 참조하여 명령을 내리게 됩니다. 프로그램과 데이터는 실제 메모리 주소에 올라가야 합니다. logical memory의 코드와 데이터들은 실제 메모.. 2022. 6. 16. Deadlock_Deadlock의 발생 조건 Deadlock 여러 개의 프로세스들이 공유자원에 동시에 접근할 때 비의도적으로 공유자원의 값이 변경되거나 오염될 수 있는데, 이러한 상태를 Race condition 이라고 부릅니다. Race condition을 방지하기 위해 동기화(Synchronization)를 사용하고, 어떠한 프로세스가 Critical section을 사용하고 있다면 다른 프로세스는 사용하지 못하도록 차단합니다. 그런데, 동기화를 사용하다보면 Deadlock의 상황이 발생될 수 있습니다. Deadlock 이란, 2개 이상의 프로세스들이 서로의 작업이 끝나기만을 기다려 결과적으로 모든 프로세스가 무한히 대기하게 되는 현상을 말합니다. 예를 들어 상황을 설명해보겠습니다. Semaphore 변수 S = 1 과 Q = 1이 존재하고, .. 2022. 6. 15. 동기화_Low Level Synchronization Tools(Spin Lock, Disabling interrupts) Synchronization Tools 여러개의 프로세스(스레드)들이 공유자원에 동시에 접근하여 비의도적으로 공유자원의 값이 변경되거나 오염되는 상태를 Race Condition이라고 합니다. 이를 해결하는 방법론이 Synchronization(동기화)이며, 어떠한 프로세스가 critical section을 실행하고 있을 때 다른 프로세스는 critical section에 접근할 수 없도록 하는 개념입니다. (자세한 설명은 여기에) 이번 포스팅에서는 OS level에서 사용하는 동기화 방법들에 대해 소개합니다. Low Level mechanism Spin Lock(+ Hardware atomic instructions) Critical Section을 보호하는 가장 기본적인 방법은, critical se.. 2022. 6. 14. 동기화_Race condition, Synchronization Synchronization Problem(Critical Section Problem) 일반적으로, 여러 프로세스(쓰레드)는 데이터를 공유하여 사용합니다. 이 때, 여러 프로세스(쓰레드)가 공유 자원에 동시에 접근하게 된다면 비의도적으로 공유 자원의 값이 변경되거나 오염될 수 있습니다. 이러한 상황을 Race condition이라고 하는데, 두 예시를 통해 해당 상황을 자세히 설명해보겠습니다. 공용 계좌에서의 인출 사람 A와 B가 잔액이 100만원인 공용 계좌를 가지고 있고, 각각 10만원씩 인출하려고 합니다. 계좌에서 특정 금액을 인출하는 과정은 다음과 같습니다. void withdraw(account, amount) { balance = get_balance(account); //계좌 잔액 불러오기.. 2022. 6. 14. 스케줄링_Real-Time Scheduling Real Time System Real Time System은 주로 임베디드 장치 안에서 주기적으로 반복되는 작업을 처리할 때 사용됩니다. Real Time System의 3요소는 Running time(t), Deadline(d), Period(p)이며, Deadline을 꼭 지켜야 하는지 여부에 따라 다음과 같이 구분할 수 있습니다. 1) Hard real-time system: Deadline을 꼭 지켜야 하는 real-time system 2) Soft real-time system: Deadline을 지키지 않아도 치명적이지 않은 real-time system 그렇다면, 주기적으로 반복되는 프로세스를 스케줄링 하는 알고리즘들을 알아봅시다. Static Priority Scheduling(Rate.. 2022. 6. 13. 스케줄링_Multilevel (Feedback) Queue Scheduling Combining Algorithms 일반적으로, 현 운영체제에서는 FCFS, SJF, Round Robin과 같은 여러가지 스케줄링 알고리즘을 결합하여 사용합니다. Multilevel Queue Scheduling과 Multilevel Feedback Queue Scheduling은 여러개의 ready queue를 두어 각 queue마다 다른 스케줄링 알고리즘을 적용하는 방식입니다. Multilevel Queue Scheduling 프로세스의 목적과 특성에 따른 여러개의 ready queue를 두어 각 queue마다 다른 스케줄링 알고리즘을 적용합니다. 그렇다면, 각 ready queue 는 어떻게 스케줄링 되어야 할까요? 일반적으로, 각 ready queue는 우선순위 알고리즘에 따라 스케줄링 된다고.. 2022. 6. 13. 스케줄링 알고리즘_Round Robin(RR) Round Robin(RR) Algorithm 프로세스를 ready queue에 도착한 순서대로 스케줄링 하되, CPU를 점유할 수 있는 최대 시간(time quantum)을 정해 놓고 해당 시간이 지나면 다음 프로세스를 스케줄링 하는 방식입니다. Running 중이던 프로세스가 중간에 interrupt 혹은 system call을 받으면, 정해진 time quantum을 모두 사용하지 못하고 CPU에서 내려오게 됩니다. 그러나 중간에 아무런 방해를 받지 않고 쭉 수행되게 된다면, CPU의 timer가 interrupt를 발생시켜 커널 모드로 전환되게 됩니다. Round Robin Algorithm의 성능은 time quantum의 길이에 따라 달라지게 되는데, 1) time qunatum의 길이가 무한.. 2022. 6. 13. 스케줄링_알고리즘_FCFS, SJF, SRTF, Priority Scheduling scheduling algorithm FCFS Scheduling (FIFO) - First Come, First Served - 도착한 순서대로 스케줄링 되는 방식 - 장점: 일반적으로, Non-preemptive 이며, 프로세스 간 fairness가 보장되어 Starvation 문제가 없음 - 단점: 수행시간이 긴 프로세스가 앞에 배치되면 average waiting time이 길어짐(Convoy effect) SJF Scheduling - Shortest Job First - CPU burst time이 작은 순으로 스케줄링 되는 방식 - Non-preemtive SRTF Scheduling - Shortest Remaining Time First - 남아있는 CPU burst time이 작은 순으.. 2022. 5. 11. 이전 1 2 다음