Paradigms & Patterns - 3Token-Passing AlgorithmsBenefits of Token-Passing AlgorithmsMicrokernel PatternContext & ProblemForcesSolutionCRC CardsMore CRC cardsStatic RelationshipsScenario IScenario IIVariantAnother Variant – Distributed Microkernel SystemExamplesConsequences10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 81Paradigms & Patterns - 3ECEN 5053 SW Eng of Distributed SystemsUniversity of Colorado, Boulder10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 82Token-Passing AlgorithmsA token is a special kind of message used to convey informationsynchronize access to replicated filesachieve conflict resolution that is fairdetermine global states in distributed computationsUsing two tokens in opposite directionsSolve distributed mutual exclusionCan bypass a failed nodeCan regenerate a lost token10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 83Benefits of Token-Passing AlgorithmsEasy to generalize to synchronization solutionsCompared to distributed semaphoresDecentralized and fair, tooToken-passing requires far fewer messages10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 84Microkernel PatternFound in POSA 1, pp. 171-192Also found in Real-Time Design Patterns: Robust Scalable Architecture for Real-Time Systems, Bruce Powel Douglass, Addison Wesley, 2003.The Microkernel architectural pattern applies to software systems that must be able to adapt to changing system requirements. It separates a minimal functional core from extended functionality and customer-specific parts. The microkernel also serves as a socket for plugging in these extensions and coordinating their collaboration.10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 85Context & Problem Context: The development of several applications that use similar programming interfaces that build on the same core functionality. Problem: Want to develop software for an application domain that needs to cope with a broad spectrum of similar standards and technologies. Systems like operating systems and GUI’s often have a long life-span. New technologies emerge; old ones change.10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 86ForcesApplication platform must cope with continuous hw and sw evolutionApplication platform should be portable, extensible, and adaptable to allow easy integration of emerging technologiesApplications in the domain need to support different but similar application platforms. The applications may be categorized into groups use the same functional core in different waysrequire the underlying application platform to emulate existing standards.Functional core  separate component with minimal memory size and services that consume as little processing as possible10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 87SolutionEncapsulate fundamental services in a microkernel component.Internal servers contain core functionality that cannot be implemented in the microkernel without causing an unnecessary increase in size or complexity.External servers implement their own view of the underlying microkernel using mechanisms available through the interfaces of the microkernel. Every external server is a separate process that represents an application platform. A microkernel system is an application platform that integrates other application platforms.Clients communicate with ext. servers using comm facilities provided by microkernel10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 88CRC CardsClass CollaboratorsMicrokernel Internal serverResponsibilityProvides coremechanismsOffers communi-cation facilitiesEncapsulates sys-tem dependenciesManages andcontrols resourcesClass CollaboratorsInternal server MicrokernelResponsibilityImplementsadditional servicesEncapsulates some system depen-denciesClass CollaboratorsExternal server MicrokernelResponsibilityProvides program-ming interfaces forits clients.10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 89More CRC cardsClass CollaboratorsClient AdapterResponsibilityRepresents anapplicationClass CollaboratorsAdapter External server MicrokernelResponsibilityHides system depen-dencies such as communication facilities from theclient.Invokes methods ofexternal servers onbehalf of clients10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 810Static RelationshipsExternal ServerreceiveRequestdispatchRequestexecuteServiceMicrokernelexecuteMechanisminitCommunicationfindReceivercreateHandlesendMessagecallInternalServerAdaptercreateRequestcallServiceClientdoTaskInternal ServerreceiveRequestexecuteServiceinitializescommunicationsends requestcalls service10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 811Scenario I10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 812Scenario II10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 813VariantMicrokernel System with indirect Client-Server connections. A Client and Server communicate with each other indirectly using the microkernel as a message backbone. All requests pass through the microkernel. Useful when security requirements force the system to control all communication between participants.10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 814Another Variant – Distributed Microkernel SystemA microkernel acts as a messaging backbone responsible for sending messages to remote machines or receiving messages from them. Every machine in the distributed system uses its own microkernel implementation. From the user’s viewpoint, the whole system appears as a single Microkernel system – distribution is transparent. A Distributed Microkernel System allows you to distribute servers and clients across a network of machines or microprocessors. The microkernels in a distributed implementation must include additional services for communicating with each other.10-16-2006 ECEN 5053, Paradigms & Patterns, Wk 815ExamplesWindows NT and 4 others in POSADouglass says: an RTOS is common subsystem Core set of services include create and delete a task, allocate and deallocate memory, provide task event & message queues, and schedule/execute a task set. Plus, a developer can link in additional components to provide more services. Common service components for RTOS include bus communications, file services, networking services, and middleware services. Thus an RTOS becomes usable in a much wider set of application problems from tiny, highly