Hệ điều hành - Chapter 8: Multiple processor systems

Multiple Processor SystemsChapter 88.1 Multiprocessors 8.2 Multicomputers 8.3 Distributed systems 1Multiprocessor SystemsContinuous need for faster computersshared memory modelmessage passing multiprocessorwide area distributed system2MultiprocessorsDefinition:A computer system in which two or more CPUs share full access to a common RAM3Multiprocessor Hardware (1)Bus-based multiprocessors4Multiprocessor Hardware (2)UMA Multiprocessor using a crossbar switch5Multiprocessor Hardware (3)UMA multiprocessors using multistage switching networks can be built from 2x2 switches (a) 2x2 switch (b) Message format6Multiprocessor Hardware (4)Omega Switching Network7Multiprocessor Hardware (5)NUMA Multiprocessor CharacteristicsSingle address space visible to all CPUsAccess to remote memory via commandsLOADSTOREAccess to remote memory slower than to local8Multiprocessor Hardware (6)(a) 256-node directory based multiprocessor(b) Fields of 32-bit memory address(c) Directory at node 369Multiprocessor OS Types (1)Each CPU has its own operating systemBus10Multiprocessor OS Types (2)Master-Slave multiprocessorsBus11Multiprocessor OS Types (3)Symmetric MultiprocessorsSMP multiprocessor modelBus12Multiprocessor Synchronization (1)TSL instruction can fail if bus already locked13Multiprocessor Synchronization (2)Multiple locks used to avoid cache thrashing14Multiprocessor Synchronization (3)Spinning versus SwitchingIn some cases CPU must waitwaits to acquire ready listIn other cases a choice existsspinning wastes CPU cyclesswitching uses up CPU cycles alsopossible to make separate decision each time locked mutex encountered15Multiprocessor Scheduling (1)Timesharingnote use of single data structure for scheduling16Multiprocessor Scheduling (2)Space sharingmultiple threads at same time across multiple CPUs17Multiprocessor Scheduling (3)Problem with communication between two threadsboth belong to process Aboth running out of phase18Multiprocessor Scheduling (4)Solution: Gang SchedulingGroups of related threads scheduled as a unit (a gang)All members of gang run simultaneouslyon different timeshared CPUsAll gang members start and end time slices together19Multiprocessor Scheduling (5)Gang Scheduling20MulticomputersDefinition:Tightly-coupled CPUs that do not share memoryAlso known as cluster computersclusters of workstations (COWs)21Multicomputer Hardware (1)Interconnection topologies(a) single switch(b) ring(c) grid(d) double torus(e) cube(f) hypercube22Multicomputer Hardware (2)Switching schemestore-and-forward packet switching23Multicomputer Hardware (3)Network interface boards in a multicomputer24Low-Level Communication Software (1)If several processes running on node need network access to send packets Map interface board to all process that need itIf kernel needs access to network Use two network boardsone to user space, one to kernel25Low-Level Communication Software (2)Node to Network Interface CommunicationUse send & receive ringscoordinates main CPU with on-board CPU26User Level Communication SoftwareMinimum services providedsend and receive commandsThese are blocking (synchronous) calls(a) Blocking send call(b) Nonblocking send call27Remote Procedure Call (1)Steps in making a remote procedure callthe stubs are shaded gray28Remote Procedure Call (2)Implementation IssuesCannot pass pointerscall by reference becomes copy-restore (but might fail)Weakly typed languagesclient stub cannot determine sizeNot always possible to determine parameter typesCannot use global variablesmay get moved to remote machine29Distributed Shared Memory (1)Note layers where it can be implementedhardwareoperating systemuser-level software30Distributed Shared Memory (2)Replication(a) Pages distributed on 4 machines(b) CPU 0 reads page 10(c) CPU 1 reads page 1031Distributed Shared Memory (3)False SharingMust also achieve sequential consistency32Multicomputer SchedulingLoad Balancing (1)Graph-theoretic deterministic algorithmProcess33Load Balancing (2)Sender-initiated distributed heuristic algorithmoverloaded sender34Load Balancing (3)Receiver-initiated distributed heuristic algorithmunder loaded receiver35Distributed Systems (1)Comparison of three kinds of multiple CPU systems36Distributed Systems (2)Achieving uniformity with middleware37Network Hardware (1)Ethernet(a) classic Ethernet(b) switched EthernetComputer(a)(b)38Network Hardware (2)The Internet39Network Services and Protocols (1)Network Services40Network Services and Protocols (2)Internet ProtocolTransmission Control ProtocolInteraction of protocols41Document-Based Middleware (1)The Weba big directed graph of documents42Document-Based Middleware (2)How the browser gets a pageAsks DNS for IP addressDNS replies with IP addressBrowser makes connection Sends request for specified pageServer sends fileTCP connection releasedBrowser displays textBrowser fetches, displays images43File System-Based Middleware (1)Transfer Models(a) upload/download model(b) remote access model(a)(b)44File System-Based Middleware (2)Naming Transparency(b) Clients have same view of file system(c) Alternatively, clients with different view45File System-Based Middleware (3)Semantics of File sharing(a) single processor gives sequential consistency(b) distributed system may return obsolete value46File System-Based Middleware (4)AFS – Andrew File Systemworkstations grouped into cellsnote position of venus and viceClient's view47Shared Object-Based Middleware (1)Main elements of CORBA based systemCommon Object Request Broker Architecture48Shared Object-Based Middleware (2)Scaling to large systemsreplicated objectsflexibilityGlobedesigned to scale to a billion usersa trillion objects around the world49Shared Object-Based Middleware (3)Globe structured object50Shared Object-Based Middleware (4)A distributed shared object in Globecan have its state copied on multiple computers at once51Shared Object-Based Middleware (5)Internal structure of a Globe object52Coordination-Based Middleware (1)Lindaindependent processescommunicate via abstract tuple spaceTuplelike a structure in C, record in PascalOperations: out, in, read, eval53Coordination-Based Middleware (2)Publish-Subscribe architecture54Coordination-Based Middleware (3)Jini - based on Linda modeldevices plugged into a networkoffer, use servicesJini Methodsreadwritetakenotify55