Multiprocessor Operating Systems

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesMultiprocessor Operating SystemsCS 6410: Advanced SystemsKai MastDepartment of Computer ScienceCornell UniversitySeptember 4, 2014Kai Mast — Multiprocessor Operating Systems1/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesLet us recallMultiprocessor vs. MulticoreFigure: Multiprocessor [10]Kai Mast — Multiprocessor Operating SystemsFigure: Multicore [10]2/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesLet us recallMessage Passing vs. Shared MemoryShared MemoryThreads/Processes access the same memory regionCommunication via changes in variablesOften easier to implementMessage PassingThreads/Processes don’t have shared memoryCommunication via messages/eventsEasier to distribute between different processorsMore robust than shared memoryKai Mast — Multiprocessor Operating Systems3/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesLet us recallMiscellaneousCache CoherenceInter-Process CommunicationRemote-Procedure CallPreemptive vs. cooperative MultitaskingNon-uniform memory access (NUMA)Kai Mast — Multiprocessor Operating Systems4/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesCurrent Systems are DiverseDifferent Architectures (x86, ARM, .)Different Scales (Desktop, Server, Embedded, Mobile .)Different Processors (GPU, CPU, ASIC .)Multiple Cores and/or Multiple ProcessorsMultiple Operating Systems on a System (Firmware,Microkernels .)Kai Mast — Multiprocessor Operating Systems5/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesHow about the Future?Moore’s Law(Source: Wikimedia Commons)Kai Mast — Multiprocessor Operating Systems6/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesHow about the Future?Single-Core doesn’t scale anymoreFigure: Possible power-consumption of a 10GHz chip [3]Kai Mast — Multiprocessor Operating Systems7/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesHow about the Future?Rock’s LawManufacturing cost increases with amount ofsemiconductorsRock’s Law eventually collides with Moore’s LawOne solution: Higher production quantityAnother approach: Multiple mid-range processors insteadof one high-end processorKai Mast — Multiprocessor Operating Systems8/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesHow about the Future?But.Multiprocessor Systems are reality today!Existing Operating System had to be adapted to supportmultiple coresApplications heavily rely on multi-threading (just think ofthe assignment.)Kai Mast — Multiprocessor Operating Systems9/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesInterconnects are evolvingDirect Wiring does not scaleOn-chip networks are more efficient in terms ofpower-consumption and area [2].Kai Mast — Multiprocessor Operating Systems10/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesInterconnects are evolvingMany-Core ChipsFigure: 36-core Chip from MIT [4]Kai Mast — Multiprocessor Operating Systems11/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesAre Operating Systems ready for this?In-Kernel Lockingn threads on n cores execute the following:1f open ( ” f i l e n a m e ” ) ;23456while ( true ) {f 2 dup ( f ) ;close ( f2 ) ;}Kai Mast — Multiprocessor Operating Systems12/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesAre Operating Systems ready for this?In-Kernel LockingFigure: Decreasing performance with increasing amount of Coresin Linux [8]Kai Mast — Multiprocessor Operating Systems13/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesAre Operating Systems ready for this?OSes optimized for most common configuration(s)Evolutionary improvements towards scalabilitySome special applications are highly coupled to hardwareconfigurationCan we abstract from hardware and gain performance?Kai Mast — Multiprocessor Operating Systems14/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesMultikernel and TornadoFigure: Barrelfish/Mulitkernel[1]Kai Mast — Multiprocessor Operating SystemsFigure: Tornado [6]15/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesThe Multikernel OSThe Paper”The Multikernel: A new OS architecture for scalablemulticore systems”Presented on SOSP in 2009Kai Mast — Multiprocessor Operating Systems16/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesThe Multikernel OSAuthor InfoAndrew BaumannWas post-doc at ETH ZurichNow at Microsoft ResearchSeveral Projects focused around OS designSimon PeterWas post-doc at ETH ZurichNow at University of WashingtonCurrent Project: Arrakis[9] (a Barrelfish fork)Kai Mast — Multiprocessor Operating Systems17/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesThe Multikernel OSThe OS itself is a distributed systemActually, multiple operating systemsExplicit communication between coresAbstract design to allow easier portabilityNote, that only the communication layer is abstractedKai Mast — Multiprocessor Operating Systems18/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesBarrelfishWhat is it?Multikernel OS is just a conceptBarrelfish is an example for an actual implementationClaims to have all the properties described before(scalable, modular, portable.)Let us evaluate and discuss later!Kai Mast — Multiprocessor Operating Systems19/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesBarrelfishOverviewFigure: Structure of Barrelfish [1]Kai Mast — Multiprocessor Operating Systems20/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesBarrelfishComponent SummaryApplication(Possibly) distributed over several kernelsMonitorGeneric (same for all cores)But still single threadedCPU driverArchitecture/Hardware specificSingle-threadedKai Mast — Multiprocessor Operating Systems21/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesBarrelfishMemoryMemory is still a shared and global resourceLogic is handled by the monitor, not the CPU driverPages of memory a mapped to specific monitorsBut virtual/shared memory pages are also possibleKai Mast — Multiprocessor Operating Systems22/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesBarrelfishPerformance EvaluationFigure: Latency of Unmapping a Memory Page [1]Kai Mast — Multiprocessor Operating Systems23/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesBarrelfishPerformance EvaluationAre the numbers meaningful?No complex applications were evaluatedOnly implemented on x86OS doesn’t support any advanced features yetKai Mast — Multiprocessor Operating Systems24/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesIs this an important paper?ProsProposes a new type of Operating SystemsThe concept could represent a paradigm-shiftSuch an approach would make OSes ”future proof”ConsNo complex benchmarks exist yetDoes not support systems that are distributed over thenetworkKai Mast — Multiprocessor Operating Systems25/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesOpen QuestionsDoes it make sense to split monitor and CPU driverperformance-wise?What would be a good communication model forMultikernels?How to support systems without a global shared memory?Kai Mast — Multiprocessor Operating Systems26/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesOther MultikernelsInvasive ComputingFigure: invasIC Architecture [7]Kai Mast — Multiprocessor Operating Systems27/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesTornado”Tornado: Maximizing Locality and Concurrency in a SharedMemory Multiprocessor Operating System”Presented on SOSP in 1999Evaluated mostly on NUMAchine at UofTorontoKai Mast — Multiprocessor Operating Systems28/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesTornadoAuthorsBen GamsaFormer Ph.D. student at University of TorontoNow working at Altera (unrelated to his research)Orran KriegerFormer VMware employeeWorking IBM T.J. Watson Research Center at the time ofpublicationNow leading the ”Center for Cloud Innovation” at BostonUniversityKai Mast — Multiprocessor Operating Systems29/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesTornadoOverviewApplication 1Application 2Clustered Object(s)Server Object(s)Server Object(s)KernelKernelCore 1Core 2Kai Mast — Multiprocessor Operating Systems30/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesClustered ObjectsFigure: Tornado [6]Same problem as before: Some resources need to besharedShared object can have more than one instance (orrepresentative)Kai Mast — Multiprocessor Operating Systems31/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesResolving Clustered ObjectsUser calls a functionCall Object Miss HandlerNoHas Reference?Object Unknown?YesCall Global Miss HandlerRetrieve ReferenceKai Mast — Multiprocessor Operating SystemsYesNoForward call to Rep32/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesResolving Clustered ObjectsMiss HandlerFigure: Miss Handling Table [6]Kai Mast — Multiprocessor Operating Systems33/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesGarbage CollectionShared Memorymight usepersistent referenceThread(s)temporary referenceClustered ObjectObject must ensure that all references are gone beforeremovalFortunately, we know of all references because of the misshandlerKai Mast — Multiprocessor Operating Systems34/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesInter-Process CommunicationIPC is a core component of any modern OSExecuting on local core is more effective (handoffscheduling)Cross-process call through local repKai Mast — Multiprocessor Operating Systems35/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesBoth Papers in nel92009497Why does Multikernel seem to have a higher impact?Kai Mast — Multiprocessor Operating Systems36/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesConclusionSimilaritiesThreat OS as network of (almost) independent coresAs little globally shared data as possibleHowever, both assume global shared memoryDifferencesTornado hides more from the userBarrelfish is built more modularTargeting different hardware (10 years difference)Kai Mast — Multiprocessor Operating Systems37/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesDiscussionIs the support for virtual memory a good idea? Should amodern OS expect the applications to do messagepassing?Is a hardware-neutral operating system realistic?Even with modularity, can one OS (architecture) cover allpossible configurations? What about low-powerembedded systems?Are the approaches really future-proof? What aboutsystems that are distributed across the network?Kai Mast — Multiprocessor Operating Systems38/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesExokernelsYet Another ApproachFigure: ”End-to-End” Design of an Exokernel [5]Kai Mast — Multiprocessor Operating Systems39/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesExokernelsCoreyFigure: A Webserver powered by the Corey OS [8]Kai Mast — Multiprocessor Operating Systems40/47

Introduction Multikernel Tornado Conclusion Discussion Outlook ReferencesExokernelsArrakisFigure: Design of Arrakis (a Barrelfish fork) [8]Kai Mast — Multiprocessor Operating Systems41/47