Design Techniques II Chapter 9 03/31/24 Crowley OS Chap. 9 1

Design Techniques II Chapter 9 03/31/24 Crowley OS Chap. 9 1

Key concepts in chapter 9 Indirection State machines Win big, then give some back Separation of concepts Reducing a problem to a special case Reentrant programs Using models for inspiration Adding a facility to a system 03/31/24 Crowley OS Chap. 9 2

Design technique: Indirection Access an object indirectly, through a third object This allows you to gain control whenever an access occurs – access becomes an event to which you can attach actions 03/31/24 Crowley OS Chap. 9 3

Indirection in C 03/31/24 Crowley OS Chap. 9 4

Indirection in text formatting Direct formatting: attach formats (e.g., bold, italics, font, etc.) to the text directly Indirect formatting: attach a formatting code to each character of the text, then attach formats to each formatting code – the formatting code is the logical formatting – the formats attached to the formatting code is the physical formatting. 03/31/24 Crowley OS Chap. 9 5

Indirect formatting 03/31/24 Crowley OS Chap. 9 6

Indirection in OSs Message queues Initial process RPC implementation (with stubs) Implementing “shared memory” with page faults Dynamic loading Character generator memory 03/31/24 Crowley OS Chap. 9 7

Indirection in CS Two-level implementations Access private data in an object Memory management Sorting large objects Passing parameters by reference Defined constants 03/31/24 Crowley OS Chap. 9 8

Dangling pointers after compaction 03/31/24 Crowley OS Chap. 9 9

Indirection using memory handles 03/31/24 Crowley OS Chap. 9 10

Sorting using indirection 03/31/24 Crowley OS Chap. 9 11

Indirection examples Source object – – – – – – Reference Indirect object Reference Desired object Process Send Message queue Receive Process OS Create by hand Initial process Create Processes Client process RPC call RPC client stub Server RPC Server process Process Memory ref. Indirect pointer Memory ref. Data object Statement Name Symbolic constant Table lookup Value Characters Name Abstract style Style sheet Concrete format 03/31/24 Crowley OS Chap. 9 12

State machine 03/31/24 Crowley OS Chap. 9 13

Design technique: State machines State machines (a.k.a. state diagrams) are an effective way to represent information – but they are only good for state-transition oriented systems Good visual representations are powerful We have seen process state diagrams 03/31/24 Crowley OS Chap. 9 14

Design technique: Win big, then give some back Some techniques produce huge gains in speed or space used – but the lose some useful property – Example: video compression But, often we can give up some of the gains to regain the property 03/31/24 Crowley OS Chap. 9 15

Video compression 03/31/24 Crowley OS Chap. 9 16

OS examples Shortest-response-ratio-next (SRN) scheduling – Shortest-job-first minimizes average wait time but penalized long jobs too much – SRN has a very good average wait time (short jobs run quickly) but does not penalize long job so much Multiprogramming – increases system efficiency but introduces parallelism and hence race conditions – Mono-programming in critical section solves that problem we lose some parallelism but regain correctness 03/31/24 Crowley OS Chap. 9 17

Design technique: Separation of concepts Often the first version of an idea combines two concepts – e.g. processes threads resource holding Separation of the concepts allows them to be used independently – smaller building blocks – so they are more flexible 03/31/24 Crowley OS Chap. 9 18

OS examples Process thread resource holder Create process fork exec Messages synchronization information transfer 03/31/24 Crowley OS Chap. 9 19

Design technique: Reducing a problem to a special case Motivation – Implement mutual exclusion with semaphores general mutual exclusion for any length of time – But we need mutual exclusion in the OS to implement semaphores special mutual exclusion: only a few machine instructions so busy waiting to acceptable 03/31/24 Crowley OS Chap. 9 20

OS examples Mutual exclusion Process blocking: OS does it but then we have to blocking OS system calls Name servers: expensive to broadcast for names in a network but once we find the name server it can resolve names for us Unique global names: use hierarchy so we only have to generate locally unique names 03/31/24 Crowley OS Chap. 9 21

CS examples Help systems: it is hard to remember how to use all the commands but if you can remember how to use the “help” command it can tell you about the others Text editor data structures: – sequential characters is time-inefficient – a linked list of characters is space-inefficient – but a linked list of line pointers to lines of sequential characters is reasonable efficient 03/31/24 Crowley OS Chap. 9 22

Design technique: Reentrant programs Two threads can execute the same code simultaneously – so the shared global data is a problem Programs with embedded data are not reentrant, also called not thread-safe We make them reentrant by removing the embedded data and allocating it for each execution – data is accessed through a pointer 03/31/24 Crowley OS Chap. 9 23

Non-reentrant and reentrant browsers // Browser using global variables WindowID wBrowser; char *wCurrentDirectory; void redrawWindow( void ) { char ** list GetFileList( wCurrentDirectory ); UpdateListBox( wBrowser, list ); } // Broswer using a state structure typedef struct browserStruct { WindowID browserID; char *currentDirectory } Browser; void redrawWindow( Browser * browser ) { char ** list GetFileList( browser- currentDirectory ); UpdateListBox( browser- browserID, list ); } 03/31/24 Crowley OS Chap. 9 24

Examples Embedded data in threaded programs Embedded data in an OS MS/DOS: most versions are not reentrant Object-oriented programming languages – Each object’s data area is allocated from the free store (the heap) so they are automatically thread-safe 03/31/24 Crowley OS Chap. 9 25

Design technique: Using models for inspiration A model is a representation of a system: an equation, a clay model, a simulation, etc. For the model to predict or prove something about the system the model must be validated to give evidence that it is accurate But a model can also be used to generate ideas about things that might be true in the system or useful – The ideas are validated in the system – so there is no necessity to validate the model 03/31/24 Crowley OS Chap. 9 26

Examples We used computer hardware models to give us ideas about processes and threads File I/O can be based on the disk model or the tape model Blackboard architectures are based on the model of experts sharing a blackboard Some people have used the economic market model for processor scheduling 03/31/24 Crowley OS Chap. 9 27

Design technique: Adding a new function to a system Three ways to add a new function – 1. Use an existing facility to build the new function – 2. Add a new low-level primitive function and use it to build the new function – 3. Add a new high-level function that does exactly what you want All solutions fit into one of these categories – often there are several solutions in a category 03/31/24 Crowley OS Chap. 9 28

OS Examples Receiving from two message queues – 1. Use processes or threads to do the waiting – 2. Add a non-blocking receive and poll – 3. Add a receive from two queues Implementing mutual exclusion – 1. Use the disable interrupts function – 2. Add an exchange-word instruction – 3. Add monitors 03/31/24 Crowley OS Chap. 9 29

Three ways to implement threads 1. Implement user-level threads inside of a process 2. Implement a “scheduler thread” facility – whenever a process makes a system call that would block, the OS calls a designated scheduler thread instead 3. Implement threads in the kernel 03/31/24 Crowley OS Chap. 9 30

CS example Iterate over an encapsulated data structure – 1. Get a chunk of memory that will hold all the items in the data structure and return that – 2. Implement an external iterator interface void StartInteration() void MoveToNextItem() Item GetCurrentItem() Boolean More Items?() – 3. Implement an internal iterator that calls a callback function once for each item in the data structure 03/31/24 Crowley OS Chap. 9 31

Design method Whenever you are adding a facility – look for solutions of all three types – if you are missing a type, think carefully about how you could do it that way Potential problem – adding a new low-level primitive can sometimes cause a security problem if it can be used in unexpected ways, or if it interacts with other functionality 03/31/24 Crowley OS Chap. 9 32

Consequences Using an existing function – no changes required, nothing new to learn – often is inefficient Adding a low-level primitive function – simpler to implement than a high-level function – more flexible than a high-level function and can be used for other purposes Adding a high-level primitive function – can be the most efficient and easy to use – not as flexible or general 03/31/24 Crowley OS Chap. 9 33