❓
물음표살인마 블로그
  • README
  • ALGORITHM
    • Sieve of Eratosthenes
    • Lcm, Gcd
    • Sorting Array
    • Round Up
    • Binary Search
    • Union Find
  • Books
    • CS Note for Interview
      • Ch1. Design Pattern & Programming paradigm
        • 1.1.1 Singleton Pattern
        • 1.1.2 Factory Pattern
        • 1.1.4 Observer Pattern
        • 1.1.5 Proxty Pattern & Proxy Server
        • 1.1.8 Model-View-Controller Pattern
        • 1.2.1 Declarative and Functional Programming
        • 1.2.2 Object Oriented Programming
      • Ch2. Network
        • 2.2.1 TCP/IP Four-Layer Model
        • 2.2.1-1 TCP 3, 4 way handshake
        • 2.3 Network Devices L4, L7
        • 2.4.1 ARP, RARP
        • 2.4.2 Hop By Hop Communication
        • 2.4.3 IP Addressing Scheme
      • Ch3. Operating System
        • 3.1.1 Roles and Structure of Operating Systems
        • 3.2.1 Memory Hierarchy
        • 3.2.2 Memory Management
        • 3.3.1 Processes and Compilation Process
        • 3.3.3 Memory Structure of a Process
        • 3.3.4 Process Control Block (PCB)
        • 3.3.5 Multiprocessing
        • 3.3.6 Threads and Multithreading
        • 3.3.7 Shared Resources and Critical Sections
        • 3.3.8 Deadlock
        • 3.4 CPU Scheduling Algorithm
      • Ch4. Database
        • 4.1 Database Basic
        • 4.2 Normalization
        • 4.3 Transaction and Integrity
        • 4.4 Types of Databases
        • 4.5 Indexes
        • 4.6 Types of Joins
        • 4.7 Principles of Joins
      • Ch5. Data Structure
    • Learning the Basics of Large-Scale System Design through Virtual Interview Cases
      • 1. Scalability based on user counts(1/2)
      • 1. Scalability based on user counts(2/2)
      • 2.Back-of-the-envelope estimation
      • 3. Strategies for System Design Interviews
      • 4. Rate Limiter
      • 5. Consistent Hashing
      • 6. Key-Value System Design
      • 7. Designing a Unique ID Generator for Distributed Systems
      • 8. Designing a URL Shortener
      • 9. Designing a Web Crawler
      • 10. Notification System Design
      • 11. Designing a News Feed System
      • 12. Chat System Design
      • 13. AutoComplete
      • 14. Design YouTube
      • 15. Design Google Drive
      • Loadbalancer Algorithms
      • Cache tier
      • CDN, Content Delivery Network
      • Stateless Web tier
    • Computer System A programmer's perspective
    • Effective Java
      • Item 1. Consider Static Factory Methods Instead of Constructors
      • Item 2. Consider a Builder When Faced with Many Constructor Parameters
      • Item 3. Ensure Singleton with Private Constructor or Enum Type
      • Item 4. Enforce Noninstantiability with a Private Constructor
      • Item 5. Prefer Dependency Injection to Hardwiring Resources
      • Item 6. Avoid Creating Unnecessary Objects
      • Item 7. Eliminate Obsolete Object References
      • Item 8. Avoid Finalizers and Cleaners
      • Item 9.Prefer try-with-resources to try-finally
      • Item10. Adhering to General Rules When Overriding equals
        • Handling Transitivity Issues
        • Ensuring Consistency
      • Item11. Override hashCode When You Override equals
      • Item12. Always Override toString
        • Always Override toString
      • Item13. Override Clone Judiciously
      • Item14. Consider Implementing Comparable
      • Item15. Minimize the Accessibility of Classes and Members
      • Item16. Accessor Methods Over Public Fields
      • Item17. Minimize Mutability
      • Item18. Composition over inherentance
      • Item19. Design and Document for Inheritance, or Else Prohibit It
      • Item20. Prefer Interfaces to Abstract Classes
      • Item21. Design Interfaces with Implementations in Mind
      • Item22. Use Interfaces Only to define Types
      • Item23. Prefer Class Hierarchies to Tagged Classes
      • Item24. Favor Static Member Classes Over Non-Static
      • Item28. Use Lists Instead of Arrays
      • Item29. Prefer Generic Types
      • Item30. Favor Generic Methods
    • Head First Design Patterns
      • Ch1. Strategy Pattern
      • Ch2. Observer Pattern
        • Ver1. Ch2. Observer Pattern
      • Ch3. Decorator Pattern
        • Ch3. Decorator Pattern
      • Ch4. Factory Pattern
      • Ch5. Singleton Pattern
      • Ch6. Command Pattern
      • Ch7. Adapter and Facade Pattern
      • Ch8. Template Method Pattern
    • Digging Deep into JVM
      • Chapter 2. Java Memory Area & Memory Overflow
      • Chapter 3. Garbage Collector & Memory Allocation Strategy (1/2)
      • Chapter 3. Garbage Collector & Memory Allocation Strategy (2/2)
      • Chapter 5. Optimization Practice
      • Chapter 6. Class file structure
  • Interview Practices
    • Restful API Practices
      • Url Shortener API
      • Event Ticket Reservation API
      • Course Management API
      • Search posts by tags API
      • Online Code platform API
      • Simple Task Management API
      • Event Participation API
      • Review System API
      • Car management API
      • Online Library
    • Naver Computer Science
      • Process & Thread
      • TCP & UDP
      • Spring & Servlet
      • Filter & Interceptor & AOP
      • Equals() & ==
      • Dependency Injection
  • F-Lab
    • Week1
      • Client & Server
      • HTTP
      • TCP/UDP
      • REST API
      • Questions
        • Object Oriented Programming
        • HTTP
        • Process & Thread
        • Data Structure
    • Week2
      • OSI 7 layer
      • Web vs WAS
    • Week3
      • RDB vs NoSQL
      • RDB Index
      • Cache
      • Redis
      • Messaging Queue
    • Week4
      • Project - Ecommerce
    • Week5
      • ERD - 1
    • Week6
      • Ecommerce - 2
      • Role
      • pw hashing && Salt
      • CreatedAt, ModifiedAt
      • JWT
      • Copy of ERD - 1
    • Week7
      • Vault (HashiCorp Vault)
    • Week 8
      • Api Endpoints
  • Week10
    • Product Create Workflow
  • TOY Project
    • CodeMentor
      • Implementation of Kafka
      • Implementation of K8s
      • Communication between servers in msa
  • JAVA
    • Java 101
      • JVM Structure
      • Java Compiles and Execution Method
      • Override, Overload
      • Interface vs Abstract Class
      • Primitive vs Object Type
      • Identity and equality
      • String, StringBuilder, StringBuffer
      • Checked Exceptions and Unchecked Exceptions
      • Java 8 methods
      • Try-with-reources
      • Strong Coupling and Loose Coupling
      • Serialization and Deserialization
      • Concurrency Programming in Java
      • Mutable vs Immutable
      • JDK vs JRE
    • Java Questions
      • Week 1(1/2) - Basic Java
      • Week 1(2/2) - OOP
      • Week 2(1/2) - String, Exception, Generic
      • Week2(2/2) Lambda, Stream, Annotation, Reflection
      • Week3(1/2) Collections
      • Week3(2/2) Threads
      • Week4 Java Concurrency Programming
      • Week5 JVM & GC
    • Batch delete instead of Cascade
    • Checked vs Unchecked Exception
    • Thread
    • Memory Visibility
    • Synchronized && ReentrantLock
    • Producer & Consumer
    • BlockingQueue
    • CAS (Compare and Set)
  • SPRING
    • Spring Questions
      • Spring Framework
      • Spring MVC & Web Request
      • AOP (Aspect-Oriented Programming)
      • Spring Boot
      • ORM & Data Access
      • Security
      • ETC
    • using profile name as variable
    • Template Method Pattern
    • Strategy Pattern
    • Proxy Pattern
    • @Transactional
    • Ioc container, di practice
  • Programming Paradigm
    • Declarative vs Imperative
  • JPA
    • Template Page
  • PYTHON
    • Icecream
  • FASTAPI
    • Template Page
  • COMPUTER SCIENCE
    • Computer Architecture 101
      • 3 components of a computer
      • RAM vs ROM
      • CPU vs GPU
      • SIMD
      • Two's complement
      • Harvard Architecture vs. von Neumann Architecture
      • The structure of a CPU.
      • Instruction cycle (CPU operation method)
      • Instruction pipelining
      • Bus
      • Memory area
      • Memory hierarchy structure
        • Reason for using memory hierarchy structure
      • Cache memory
      • L1, L2, L3 Cache
      • Locality of reference (cache)
      • Fixed-point vs Floating-point
        • epresentation of infinity and NaN (Not a Number) in floating-point
      • RISC vs CISC
      • Hamming code
      • Compiler
      • Linking
      • Compiler vs Interpreter
      • Mutex vs Semaphore
      • 32bit CPU and 64bit CPU
      • Local vs Static Variable
      • Page
  • OS
    • Operating System 101
      • Operating system
        • The role of the operating system
        • The composition of the operating system.
      • Process
        • In Linux, are all processes except the initial process child processes?
        • Zombie process, orphan process
        • (Linux) Daemon process
        • Process address space
        • Where are uninitialized variables stored?
        • Determination of the size of the Stack and Heap
        • Access speed of Stack vs Heap
        • Reason for memory space partitioning
        • Process of compiling a process
        • sudo kill -9 $CURRENT_PID
      • Thread
        • Composition of a thread's address space
      • Process vs Thread
        • Creation of processes and threads in Linux
      • Multiprocessing
        • Web Browser
        • Implementation of multiprocessing
        • Application areas of multiprocessing
      • Multithreading
        • Application areas of multithreading
      • Interrupt
        • HW / SW Interrupt
        • Method of handling interrupts
        • Occurrence of two or more interrupts simultaneously
      • Polling
      • Dual Mode
        • Reason for distinguishing between user mode and kernel mode
      • System call
        • Differentiation between system calls
        • Types of system calls
        • Execution process of a system call
      • Process Control Block (PCB)
        • PCB의 구조
        • 쓰레드는 PCB를 갖고 있을까?
        • 프로세스 메모리 구조
      • Context switching
        • Timing of context switching
        • Registers saved during context switching
        • Context switching in processes
        • Context switching in threads
        • Difference between context switching in processes and threads
        • Information of the current process during context switching
      • Interprocess Communication (IPC)
        • Cases where IPC is used
        • Process address space in IPC Shared Memory technique
        • Types of IPC
    • Operating System Questions
      • Week1 OS & How Computer Systems Work
      • Week2(1/2) Process
      • Week2(2/2) Thread
      • Week3 CPU Scheduling
      • Week4 Process Synchronize
      • Week5 Virtual Memory
  • LINUX
    • Template Page
  • SERVER
    • Template Page
  • NETWORK
    • Network 101
      • https://www.google.com
      • TCP vs UDP
      • Http vs Https
      • TLS Handshake 1.2
      • HTTP Method
      • CORS & SOP
      • Web Server Software
    • Network Questions
      • Week1 Computer Network Basic
      • Week2(1/3) Application Layer Protocol - HTTP
      • Week2(2/3) Application Layer Protocol - HTTPS
      • Week2(3/3) Application Layer Protocol - DNS
      • Week3 Application Layer
      • Week4 Transport Layer - UDP, TCP
      • Week5 Network Layer - IP Protocol
    • Blocking, NonBlocking and Sync, Async
    • HTTP 0.9-3.0
  • DATABASE
    • Database Questions
      • Week1 DBMS, RDBMS basics
      • Week2 SQL
      • Week3 Index
      • Week4 Anomaly, Functional Dependency, Normalization
      • Week5 DB Transaction, Recovery
    • Normalization
      • 1st Normal Form
      • 2nd Normal Form
      • 3rd Normal Form
    • Ensuring Data Consistency, Atomicity and UX Optimization (feat.Firebase)
    • Redis: Remote Dictionary Server
    • Enhancing Query Performance - User list
  • DATA STRUCTURE
    • Array vs Linked List
    • Counting Sort
  • GIT, Github
    • git clone, invalid path error
  • INFRA
    • Template Page
  • AWS
    • Server Log Archive Pipeline
    • Image Processing using Lambda
  • DOCKER
    • Docker commands
    • Python Executable Environment
    • Docker and VM
  • docker-compose
    • Kafka, Multi Broker
  • KUBERNATES
    • !Encountered Errors
      • my-sql restarts
      • kafka producer: disconnected
    • Kubernetes Components
    • Helm
      • Helm commands
    • Pod network
    • Service network
      • deployment.yaml
      • services.yaml
    • Service type
      • Cluster IP
      • NodePort
    • service-name-headless?
    • kube-proxy
    • Template Page
  • GraphQL
    • Template Page
  • WEB
    • Template Page
  • Reviews
    • Graphic Intern Review
    • Kakao Brain Pathfinder Review
    • JSCODE 자바 1기 Review
  • 😁Dev Jokes
    • Image
      • Plot twist
      • Priorities
      • SQL join guide
      • Google is generous
      • Genie dislikes cloud
      • buggy bugs
      • last day of unpaid internship
      • what if clients know how to inspect
      • its just game
      • how i wrote my achievement on resume
      • self explanatory
      • chr(sum(range(ord(min(str(not))))))
Powered by GitBook
On this page
  • 절대 주소 지정과 상대 주소 지정의 차이점은 무엇인가요?
  • 메모리 분할에 대해 설명해주세요.
  • 메모리 배치 기법(메모리 관리 전략)에 대해 설명해주세요.
  • 외부 단편화와 내부 단편화에 대해 설명해주세요
  • 메모리 배치 기법중 하나인 Coalescing(통합)에 대해 설명해주세요.
  • 메모리 배치 기법 중 하나인 Compaction(압축)에 대해 설명해 주세요.
  • 메모리 배치 기법 중 하나인 버디 시스템에 대해 설명해주세요.
  • 메모리 배치 기법 중 하나인 페이징에 대해 설명해주세요.
  • 메모리 배치 기법 중 하나인 세그멘테이션에 대해 설명해주세요.
  • 가상 메모리에 대해 설명해 주세요.
  • Swapping이란 무엇인가요?
  • 페이지 교체에 대해 설명해주세요.
  • 페이지 부재를 최소화하려면 어떻게 해야 하나요?
  • 페이지 교체 알고리즘 FIFO에 대해 설명해 주세요.
  • 페이지 교체 알고리즘 LRU에 대해 설명해주세요.
  • 페이지 교체 알고리즘 LFU에 대해 설명해주세요.
  • 페이지 교체 알고리즘 클럭 알고리즘(Clock)에 대해 설명해주세요.
  • 쓰레싱(Thrashing)에 대해 설명해주세요
  • 워킹셋 알고리즘에 대해 설명해주세요.
  • 페이지 부재 빈도(Page Fault Frequency, PFF) 알고리즘에 대해 설명해 주세요.
  1. OS
  2. Operating System Questions

Week5 Virtual Memory

가상 메모리

PreviousWeek4 Process SynchronizeNextTemplate Page

Last updated 6 months ago

절대 주소 지정과 상대 주소 지정의 차이점은 무엇인가요?

  • 절대 주소는 물리적 메모리의 실제 위치를 직접 가리킵니다. 즉, 메모리 주소가 고정되어 있어서 프로그램이 어느 주소를 사용해야 하는지 정확히 알 수 있습니다.

  • 상대 주소는 특정 기준 주소 (주로 프로세스의 시작 주소)로부터의 오프셋을 사용하여 메모리 주소를 지정합니다.

메모리 분할에 대해 설명해주세요.

  • 여러 프로그램을 동시에 메모리에 적재하여 실행하기 위한 메모리 관리 방법(멀티 프로그래밍 시스템)

연속 할당

  • 고정 분할 방식 (Fixed Partitioning): 메모리를 여러개의 고정된 크기로 파티션을 나눕니다.

  • 가변 분할 방식 (Dynamic Partitioning): 메모리를 프로그램의 크기에 맞게 가변적으로 나눕니다.

불연속 할당

  • 프로그램을 여러 개의 작은 조각으로 나누어 메모리의 비연속적인 위치에 적재하는 방식

  • 페이징: 메모리를 일정한 크기로 나누어 각 페이지에 적재하는 방식

  • 세그멘테이션: 의미있는 단위로 프로그램을 나누어 메모리에 적재하는 방식

메모리 배치 기법(메모리 관리 전략)에 대해 설명해주세요.

메모리 배치 기법 또는 동적 메모리 할당 문제

연속 메모리 할당 기법

  • 프로세스를 메모리에 어떻게 배치할지 결정하는 기법입니다. 프로세스를 적재하는 과정에서 외부 단편화 또는 내부 단편화와 같은 문제가 발생

  • First-Fit(최초 적합): (-외부 단편화 발생) 메모리의 빈 공간을 순차적으로 검색하여, 프로세스가 들어갈 수 있는 첫 번째 가용 공간에 프로세스를 배치

  • Best-Fit(최적 적합): (-전체 메모리 풀 스캔) 메모리의 빈 공간 중에서 프로세스가 들어갈 수 있는 가장 작은 공간에 프로세스를 배치

  • Worst-Fit(최악 적합): (-쓸모 없는 작은 조각들이 많이 발생) 메모리의 빈 공간 중에서 가장 큰 공간에 프로세스를 배치

불연속 메모리 할당 기법

  • (메모리) 페이징: 외부 단편화(External Fragmentation) 문제를 해결 프로세스는 여러 페이지로 나누어져 있으며, 각 페이지는 물리 메모리의 비연속적인 페이지 프레임에 적재 내부 단편화(Internal Fragmentation)가 발생

  • (프로그램) 세그멘테이션: 세그멘테이션은 프로그램을 의미 단위로 나누어 메모리에 배치하는 기법입니다. 이 방식에서는 프로그램의 논리 주소 공간을 세그먼트(Segment)라는 비균일한 크기로 나눕니다. 외부 단편화(External Fragmentation)가 발생

외부 단편화와 내부 단편화에 대해 설명해주세요

외부 단편화

  • 연속 메모리 할당 전략에서 주로 발생.

  • 메모리를 할당하고 남은 빈 공간들이 흩어져 있어, 새로운 프로세스를 적재할 충분한 연속된 메모리 공간을 찾을 수 없는 상황

(외부 단편화는 1-4까지 메모리 영역을 사용하는 프로그램이 종료되고 3의 크기를 가진 프로그램이 1-3까지 할당받았을때 남는 4)

내부 단편화

  • 프로세스가 할당된 메모리 블록보다 작을 때, 할당된 메모리 공간 내에서 사용되지 않는 부분이 생기는 상황

메모리 배치 기법중 하나인 Coalescing(통합)에 대해 설명해주세요.

  • 통합은 동적 메모리 할당에서 발생하는 외부 단편화를 줄이기 위한 기법입니다. 메모리의 여러 곳에 나누어져 있는 인접한 빈 메모리 블록을 하나로 합쳐서 더 큰 연속적인 공간을 만드는 방식

  • 인접한 메모리만 합침

메모리 배치 기법 중 하나인 Compaction(압축)에 대해 설명해 주세요.

  • 압축은 메모리 내에서 발생하는 외부 단편화를 해결하기 위한 기법

  • 현재 메모리에 적재되어 있는 프로세스들을 한쪽으로 몰아 빈 공간을 하나로 합칩니다.

  • 프로세스를 재배치함

메모리 배치 기법 중 하나인 버디 시스템에 대해 설명해주세요.

버디 시스템은 메모리 할당 및 관리에서 사용되는 기법으로, 동적 메모리 할당에서 내부 단편화와 외부 단편화 문제를 해결하기 위해 고안되었습니다. 메모리를 관리할 때 크기가 2의 제곱수인 블록 단위로 분할하고 합치는 방식

해제를 하면, 통합을 시도합니다.

메모리 배치 기법 중 하나인 페이징에 대해 설명해주세요.

  • 페이징은 불연속 메모리 할당 전략 중 하나로, 외부 단편화 문제를 해결하기 위해 고안

  • 메모리를 고정된 크기의 **페이지 프레임(Page Frame)**으로 나누고, 프로그램(프로세스)의 주소 공간도 고정된 크기의 **페이지(Page)**로 나눈 후, 페이지 단위로 메모리의 비연속적인 영역에 적재

  • 페이지 테이블로 논리주소를 물리주소로 변환하여 접근

  • 프로그램의 크기가 페이지 크기의 배수가 아닐 경우, 내부 단편화가 발생

메모리 배치 기법 중 하나인 세그멘테이션에 대해 설명해주세요.

  • 세그멘테이션은 불연속 메모리 할당 기법 중 하나로, 프로세스를 의미 있는 논리적 단위로 나누어 메모리에 할당하는 방식

  • 세그먼트 테이블로 논리주소를 물리주소로 변환하여 접근

  • 외부 단편화가 발생할 수 있습니다. 세그먼트의 크기가 가변적이기 때문에, 세그먼트 크기에 맞는 연속된 메모리 공간을 찾는 과정에서 외부 단편화 문제가 발생

  • 압축 과정으로 인해 세그먼트 이동이 발생하면 성능 저하.

가상 메모리에 대해 설명해 주세요.

가상 메모리(Virtual Memory)는 물리적 메모리(RAM)가 부족할 때, 디스크의 일부 공간을 마치 메모리처럼 사용하는 기법

  • 프로세스는 논리적 주소(가상 주소) 공간을 사용하며, 이는 실제 메모리 공간인 물리 주소와는 다릅니다.

  • 가상 메모리는 주로 페이징(Paging) 기법을 사용하여 구현. 프로세스는 페이지(Page)라는 작은 단위로 나누어지고, 각 페이지가 필요할 때만 메모리에 적재

  • 물리 메모리가 부족할 때, 사용하지 않는 페이지를 디스크의 스왑 영역으로 옮기고, 나중에 필요할 때 다시 불러오는 작업을 스와핑(Swapping)

  • 단점으로는 디스크IO 작업과 쓰레싱(시스템이 페이지 교체 작업에 너무 많은 시간을 소비하여 실제 작업을 거의 수행하지 못하는 상태)

Swapping이란 무엇인가요?

Swapping(스와핑)은 물리적 메모리(RAM)가 부족할 때, 실행 중인 프로세스 전체 또는 프로세스의 일부(페이지)를 디스크의 스왑 영역으로 옮기는 작업

단점으로는 성능 저하, 쓰레싱

페이지 교체에 대해 설명해주세요.

  • CPU가 참조하려는 페이지가 물리적메모리에 없을때 발생

  • 물리적메모리에 자리가 없다면 현재 메모리에 있는 페이지 중 하나를 디스크로 내보내고 그 자리에 새 페이지를 적재하는 작업

Swapping vs Page Replacement

  • Swapping은 전체 프로세스를 대상으로 하거나 큰 단위로 메모리를 스왑하는 작업을 말합니다.

  • 페이지 교체는 메모리에 부족한 페이지 공간을 확보하기 위해 특정 페이지 단위로 메모리와 디스크 간에 데이터를 교체하는 작업입니다.

페이지 부재를 최소화하려면 어떻게 해야 하나요?

  • 페이지 부재를 최소화하려면 적절한 페이지 교체 알고리즘을 사용

  • LRU: Least Recently Used

  • LFU: Least Frequently Used

  • FIFO: First In First Out

  • OPT: 이론만. 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체

페이지 교체 알고리즘 FIFO에 대해 설명해 주세요.

FIFO(First-In, First-Out) 알고리즘은 가장 먼저 메모리에 적재된 페이지를 교체하는 방식

  • Queue로 관리.

  • 단점: Belady's Anomaly. 시간 지역성을 고려하지 않아서 페이지 프레임이 늘어나도 페이지 폴트가 증가하는 이상한 상황

페이지 교체 알고리즘 LRU에 대해 설명해주세요.

LRU(Least Recently Used) 알고리즘은 시간 지역성을 고려하여, 참조된지 가장 오래된 페이지를 교체하는 방식

  • 최근에 사용된 페이지가 가까운 미래에도 참조될 가능성이 높다는 시간 지역성 개념에 기반

  • 페이지의 참조 시점을 저장하고 관리해야 하므로, 추적 비용이 발생 & 페이지가 참조될 때마다 모든 페이지의 최근 참조 시간을 업데이트

  • 우선 순위 큐 / 스택 / 이중 연결 리스트로 관리

페이지 교체 알고리즘 LFU에 대해 설명해주세요.

LFU는 Least Frequently Used 알고리즘은 가장 적게 참조된 페이지를 교체하는 방식

  • 단점: U는 참조 횟수만을 기반으로 하기 때문에, 오래전에 자주 사용되었지만 지금은 거의 사용되지 않는 페이지가 메모리에 계속 남음

  • 참조 횟수 추적을 위한 추가 저장 공간 && Starvation -> Aging으로 시간 가중치를 부여하여 해결

페이지 교체 알고리즘 클럭 알고리즘(Clock)에 대해 설명해주세요.

  • 클럭 알고리즘은 LRU 알고리즘을 효율적으로 구현하기 위한 근사화 알고리즘. 페이지 참조 이력을 저장하지 않고도, 페이지 교체를 효율적으로 처리할 수 있도록 설계

  • 각 페이지마다 참조 비트를 두어서 페이지가 참조되었는지 여부를 기록.

  • 클럭 포인터: 교체할 페이지를 가리키는 포인터. 시계 방향으로 순차적으로 이동하며, 참조비트 0을 만나면 교체하고, 1이면 0으로 리셋후 다음 페이지로 이동.

  • Belady 모순 해결하지만, 참조비트가 신뢰성이 있진 않다. 최근에 참조한건지 알 수가 없다.

쓰레싱(Thrashing)에 대해 설명해주세요

페이지 폴트가 너무 자주 발생하여 페이지 교체에 소요되는 시간이 실제 작업을 수행하는 시간보다 더 길어지는 상황

  • 프로세스 수 조절 또는 워킹셋 관리 또는 페이지 프레임을 추가로 할당하여 쓰레싱을 방지.

워킹셋 관리

프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합(워킹셋)을 메모리에 유지하는 방식

워킹셋 알고리즘에 대해 설명해주세요.

  • 워킹셋은 프로세스가 일정 시간 구간 내에 참조한 페이지들의 집합을 의미.

  • 워킹셋에 있는 페이지가 다시 참조되어도 순서 변경X

  • 우선순위 (Deque, HashSet, LinkedHashSet으로 관리)

과정

  • 페이지 참조 시퀀스: 1, 2, 3, 2, 4, 1, 5, 2, 3, 6

3. Δ=5인 상황에서 워킹셋의 변화**:

과정 설명:

  1. 1 -> 1

  2. 2 -> 1, 2

  3. 3 -> 1, 2, 3

  4. 2 -> 1, 2, 3

  5. 4 -> 1, 2, 3, 4

  6. 1 -> 1, 2, 3, 4

  7. 5 -> 1, 2, 3, 4, 5

  8. 2 -> 1, 2, 3, 4, 5

  9. 3 -> 1, 2, 3, 4, 5

  10. 6 -> 2, 3, 4, 5, 6

  1. 초기 참조(1~5번째 페이지 참조): 프로세스는 처음에 페이지 1, 2, 3, 2, 4를 참조합니다. 이 시점에서 워킹셋은 시간 창 Δ(5 참조) 기준으로 1, 2, 3, 4를 포함하고 있습니다. 워킹셋 내의 페이지들은 최근 참조되었으므로, 이 페이지들은 메모리에 유지됩니다.

  2. 참조된 페이지가 워킹셋에 있는 경우:

    • 6번째 참조에서 페이지 1이 다시 참조됩니다. 이 페이지는 이미 워킹셋에 포함되어 있으므로, 교체가 발생하지 않습니다.

  3. 페이지 교체 발생 (10번째 참조):

    • 8번째 참조에서 페이지 6이 참조됩니다. 이제 시간 창 Δ(5 참조) 기준으로 최근 5번 참조된 페이지들은 1, 2, 3, 4, 5입니다. 이 시점에서 페이지 1은 워킹셋에서 오래되어 더 이상 필요하지 않으므로 교체됩니다.

페이지 부재 빈도(Page Fault Frequency, PFF) 알고리즘에 대해 설명해 주세요.

  • 페이지 부재(Page Fault) 발생 빈도를 기반으로 프로세스에 할당할 메모리 페이지 프레임 수를 동적으로 조절하는 메모리 관리 기법

  • 각 프로세스의 페이지 부재율을 주기적으로 모니터링하여, 페이지 부재율이 높거나 낮은 경우에 따라 할당된 메모리 페이지 수를 동적으로 조정하는 방식

  • 상한값과 하한값을 정하여서, 페이지 부재율이 상한값을 초과하면 프레임을 늘리고, 아니면 줄임

  • 단점: 모니터링 오버헤드, 프레임 수의 변동으로 인한 오버헤드