topcue

IntroductionLocks: The Basic IdeaPthread LocksEvaluating LocksControlling InterruptsA Failed Attempt: Just Using Loads/StoresBuilding A Working Spin Lock(with Test-And-Set)Compare-And-SwapLoad-Linked and Store-ConditionalFetch-And-Add (번호표)Introductionconcurrency에서 instruction이 atomic하지 않아서 문제가 발생한다. 이를 해결하기 위해 critial section을 lock으로 감싸서 atomic하게 만든다.Locks: The Basic Idealock_t mutex; // some g..

An IntroductionAn Example: Thread CreationWhy It Gets Worse: Shared DataThe Heart Of The Problem: Uncontrolled SchedulingThe Wish For AtomicityOne More Problem: Waiting For AnotherInterlude: Thread APIThread CreationAn Introduction각 프로세스마다 virtual memory를 주고 address space라는 개념을 이용해 하나의 physical CPU를 여러 개의 virtual CPU처럼 사용할 수 있었다.앞으로 thread를 다룰 것이다. multi-threaded program은 PC register가 여러 개고, 같은 ..

Cache ManagementOptimalFIFORandomLRU(Least-Recently-Used)Workload ExamplesApproximating LRUConsidering Dirty PagesCache Management메인 메모리가 page들을 가지고 있다면 그 페이지들은 virtual memory page들의 cache로 볼 수 있다.따라서 우리의 목표는 disk에서 fetch 해올 때 cache miss를 최소화하는 replacement policy를 선택하는 것이다. (또는 cache hits 최대화)cache hit과 cache miss는 AMAT(Average Memory Access Time)로 계산할 수 있다.AMAT=(Hit%⋅TM)+(Miss%⋅TD)AMAT = (\text..

Beyond Physical Memory: MechanismsSwap SpaceThe Present BitThe Page FaultPage Fault Control FlowWhen Replacements Really OccurSummaryBeyond Physical Memory: MechanismsAssumption지금까지는 모든 running process들의 address space가 메모리에 들어간다는 가정을 했다.하지만 이는 비현실적이고, 따라서 memory hierarchy를 더 추가하려 한다.많은 페이지를 저장할 수 있을 만큼 큰 메모리는 hard disk drive이다. 하드 디스크는 느리지만 매우 크며, 이는 과거의 memory overlay와 대조된다.Swap Space디스크에 페이지를 ..

ProblemSimple Solution: Bigger PagesHybrid Approach: Paging and SegmentsMulti-level Page TablesInverted Page TablesProblemPage table은 크기가 너무 커서 많은 메모리가 필요하다.예를 들어 address space가 32-bit이고 page 크기가 4KB(2122^{12}212), PTE entry 크기는 4-byte라고 가정해보자. 이 경우 page table 크기는 4MB이다.게다가 page table은 per-process data structure라서 더 많은 메모리를 차지한다.Simple Solution: Bigger PagesPage table 크기를 줄이기 위한 간단한 방법 중 하나는 더 ..

Paging: Faster Translations (TLBs)TLB Basic AlgorithmExample: Accessing An Array지역성(Locality)Who Handles The TLB Miss?TLB Miss Handle : H/WTLB Miss Handle : S/WOS handle TLB miss 1 : return form trapOS handle TLB miss 2 : avoid infinite chainAdvantage of software-managed TLBTLB Contents: What’s In There?TLB valid bit & Page Table valid bitTLB Issue: Context SwitchesFlush TLBASID(Address Space ID..

Introduction: PagingAdvantagesPage tableAddress TranslationIntroduction: Pagingspace-management에는 크게 두 가지 방법이 있다.먼저 가변 크기로 나눠서 관리하는 방법 중 segmentation이 대표적이다. segment는 서로 다른 크기의 chunk 때문에 fragmentation이 발생한다.두 번째로 고정된 크기로 나눠서 관리하는 paging 기법이 있다. 고정된 크기의 단위인 page로 나눠서 관리하는 방법이다.paging에서는 physical memory를 page frame이라고 불리는 fixed-size slot들의 배열로 본다. 각 page frame은 virtual memory page를 하나씩 가지고 있다.Over..

Free-Space ManagementIntroductionAssumptionsLow-level MechanismsBasic StrategiesBest FitWorst fitFirst fitNext fitBuddy AllocationFree-Space ManagementIntroduction나중에 다룰 paging을 이용하면 메모리를 고정된 크기로 나누기 때문에 메모리 관리가 더 쉽다.free-space management가 어려운 이유는 user-level에서 malloc을 이용해 고정되지 않은 크기의 메모리를 할당하기 때문이다.바로 이런 이유 때문에 external fragmetation이 발생한다.external fragmentationfree space가 used space 사이사이에 존재하는 경..