topcue

The Way To ThinkOverall OrganizationFile Organization: The InodeDirectory OrganizationFree Space ManagementAccess Paths: Reading and WritingCaching and BufferingThe Way To ThinkUNIX의 전형적인 File system 형태인 VSFS(Very Simple File System)을 다룰 것이다.또한 data structures와 access methods 두 가지 관점에서 file system을 다룰 것이다.block: 4KB, Sector: 512B (atomic)Overall Organization디스크를 4KB block 단위로 나눌 수 있다.vsfs에서는 아래 ..

IntroFileCreate fileRead fileRead and Write file (not sequentially)Write file immediately - fsync()Rename fileFile informationRemove fileDirectoriescreate directoryRead directoryDelete directoryHard LinksSymbolic LinksMaking and Mounting a File SystemIntroblock 안에 sector들이 있다. sector는 보통 512 바이트. block은 4KB(UNIX) or 8KB. 섹터는 atomic하게 처리 가능하다.UNIX에서 metadata를 i-node라고 부른다. head가 여러 block을 가리키고 있다..

The InterfaceBasic GeometryA Simple Disk DriveSingle-track Latency: The Rotational DelayMultiple Tracks: Seek TimeSome Other DetailsI/O Time: Doing The MathDisk SchedulingFIFOSSTF: Shortest Seek Time FirstElevator (a.k.a. SCAN or C-SCAN)SPTF: Shortest Positioning Time FirstOther Scheduling IssuesThe InterfaceSectorHDD를 이루는 512B 단위이며 atomic하게 읽거나 쓸 수 있다.디스크 판은 자화(N/S) 되어있다. head는 arm을 통해 전해지는 전기 ..

System ArchitectureA Canonical DeviceThe Canonical ProtocolLowering CPU Overhead With InterruptsMore Efficient Data Movement With DMAMethods Of Device InteractionFitting Into The OS: The Device DriverCase Study: A Simple IDE Disk DriverSystem Architecture다음은 전형적인 컴퓨터 시스템을 도식화한 그림이다.CPU가 memory bus를 통해 메인 메모리와 연결되어 있는 것을 볼 수 있다. 그리고 몇몇 장치들이 general I/O bus(PCI)를 통해 연결되어 있다. 더 내려가보면 SCSI, SATA, US..

Common Concurrency ProblemsNon-Deadlock BugsAtomicity-Violation BugsOrder-Violation BugsDeadlock BugsConditions for DeadlockPreventionCircular WaitHold-and-waitNo PreemptionMutual ExclusionAvoidDeadlock Avoidance via SchedulingDetect and RecoverCommon Concurrency ProblemsWhat Types Of Bugs Exist?concurrent program에서 발생할 수 있는 버그는 Non-Deadlock Bug와 Deadlock Bug로 나눌 수 있다.Non-Deadlock BugsAtomicity-..

Semaphores: A DefinitionBinary Semaphores (Locks)Semaphores As Condition VariablesThe Producer/Consumer ProblemFirst AttemptA Solution: Adding Mutual ExclusionSolution: Avoiding DeadlockReader-Writer LockThe Dining PhilosophersBroken SolutionA Solution: Breaking The DependencyHow To Implement SemaphoresSemaphores: A Definitionsemaphore는 value와 queue를 갖는 synchronization primitive이다. lock과 conditi..

Definition and RoutinesIssue: Spin-based Approachcondition variableThe Producer/Consumer ProblemA Broken Solution (with condition variable)Better, But Still Broken: While, Not IfThe Single Buffer Producer/Consumer Solution (with Empty and Fill)The Final Producer/Consumer SolutionCovering ConditionsDefinition and RoutinesIssue: Spin-based ApproachParent Waiting For Child: Spin-based Approachvolat..

Too Much SpiningBad Performancepriority inversionA Simple Approach: Just YieldUsing Queues: SleepingDifferent OS, Different Support (Futex)Spin vs SleepTwo-Phase LocksToo Much Spiningspin을 사용하는 정책의 고질적인 문제가 있다.Bad Performance한 스레드가 lock 상태에서 spin을 돌면 다른 스레드는 lock을 얻기 힘들어진다.priority inversionspin의 또 다른 문제점은 priority inversion이다. 이는 우선순위가 낮은 job이 먼저 스케줄 되는 상황을 말한다.우선순위가 있는 스케줄링이라고 가정하자.Priority in..