Dreams in a Nutshell

Dreams in a Nutshell : 

Dreams in a Nutshell Steven Sommer steve@mpce.mq.edu.au Microsoft Research Institute Department of Computing Macquarie University

Overview : 

August 1997 USENIX Windows NT Workshop Overview 1. Background 2. Dreams Model 3. Overrun 4. Implementation

Dreams : 

August 1997 USENIX Windows NT Workshop Dreams Distributed Real-time Extensions with Application to Multimedia Systems Extend conventional operating systems to support distributed real-time applications Paradigm preserving

Key Paradigm Differences : 

August 1997 USENIX Windows NT Workshop Key Paradigm Differences Multiple competing applications Temporal protection Absence of a priori knowledge Different kinds of applications Subsystems (servers) Interrupts Dynamic distribution

2. The Dreams Model : 

August 1997 USENIX Windows NT Workshop 2. The Dreams Model Transient Periodic Processes Periodic Invocations Specified Period Deadline Execution Time

The Dreams Model : 

6 The Dreams Model

3. Overrun Concepts : 

August 1997 USENIX Windows NT Workshop 3. Overrun Concepts System guarantee: A real-time task will receive its reserved resources between each invocation’s start-time and deadline A task which consumes its reserved capacity without completing has overrun Only overrun tasks can miss their deadlines Task continues in overrun state Overrun tasks receive refreshed resources at the start of their next period

Slide 8: 

Waiting Runnable Overrun Invocation’s Start Time Scheduled Thread Invocation Completion Invocation Overrun Overrun Leave Overrun Try Scheduling and Overrun 8

Sample Schedule : 

Sample Schedule 0 100 200 300 400 Time ID 01234567890123456789012345678901234567890123456789 ---- 4500 1 .......RC........RC........RC........RC........R1O 4500 2 .......SR2222222C...............R22222R22C........ 4500 3 33333333........R3R333333333R3333........R333333.R 5000 1 .......C.........R1O..RC...R1C.......R1O..C....R1O 5000 2 .......R2222222C................R22222.R22C....... 5000 3 33333333.......R33.R33C.........................SR 5500 1 .......C.........R1O.......C.........R1O.......C.. 5500 2 .......R2222222C................R22222.R22C....... 5500 3 33333333.......R33.R3333333R33333.........R3333R33 Legend:(S)tart(time) (R)un (scheduled) (C)ompleted (O)verrun Multiple Process Period Reservation Av. Execution Time first scheduled T1 100 20 20 ~70 T2 250 110 100 ~70 T3 1000 440 400 ~480 . = 10ms

4. Implementation : 

4. Implementation Windows NT 3.51 implementation Minimal impact on: Non-real-time execution Existing operating system code Programming paradigm

Slide 11: 

Win32 Subsystem Win32™ Client Protected subsystems (servers) User mode Kernel mode System Trap Message Passing / Shared Memory Dreams Subsystem Applications Dreams Client System services I/O manager Kernel File systems Cache manager Device drivers Network drivers Hardware abstraction layer Security Reference Monitor Object Manager Process Manager Virtual Memory Manager Local Procedure Call Executive 11

Slide 12: 

Kernel Mode Dreams Window NT Kernel Dreams Subsystem Memory Space Dreams Client Application Memory Space Kernel Call Application Process Dreams DLL Real-Time Thread Dreams DLL Real-Time Scheduler + Enforcer Real-Time Thread Manager API Call API Call Non real-time priority Real-time priority Procedure call via named pipes Shared Data Area Requests / Process Table Blocking Access Non blocking access Non blocking communication Shared Memory Periodic Invocation Reservation Manager Scheduling via NT Priority Control Create Thread 12

Implementation Experience : 

Implementation Experience Dreams extensions in a subsystem Meet implementation goals Simpler development, modification, and testing Priority inheritance Useful in all operating systems (not just real-time) Performance improvement Two tiered scheduler (with priority inheritance) Hides scheduling complexities Simpler scheduling Simpler schedulability model Simpler timing and enforcement

Summary : 

August 1997 USENIX Windows NT Workshop Summary Background Dreams Model Overrun Implementation

Sample Schedule : 

Sample Schedule 0 100 200 300 400 Time ID 01234567890123456789012345678901234567890123456789 ---- 4500 1 .......RC........RC........RC........RC........R1O 4500 2 .......SR2222222C...............R22222R22C........ 4500 3 33333333........R3R333333333R3333........R333333.R 5000 1 .......C.........R1O..RC...R1C.......R1O..C....R1O 5000 2 .......R2222222C................R22222.R22C....... 5000 3 33333333.......R33.R33C.........................SR 5500 1 .......C.........R1O.......C.........R1O.......C.. 5500 2 .......R2222222C................R22222.R22C....... 5500 3 33333333.......R33.R3333333R33333.........R3333R33 Legend:(S)tart(time) (R)un (scheduled) (C)ompleted (O)verrun Multiple Process Period Reservation Av. Execution Time first scheduled T1 100 20 20 ~70 T2 250 110 100 ~70 T3 1000 440 400 ~480 . = 10ms