/ Resources / Design / Domain Analysis

Object-Oriented Operating Systems

Choices

Choices is an object oriented operating system written in C++. It is considerablly more OO than the original RCOS code and as a project Choices has shown that OO operating systems provide significant software engineering advantages. A PhD thesis describing the Choices application interface, process management and memory management is available from the Internet (follow the link to Choices above). I have a paper based copy.

The same thesis concludes that there aren't a great many "truly" OO operating systems. RCOS falls under the category of kernel based operating system.

Choices is a complete OO environment. Even application programs are designed to be OO and make use of OS services by a specialised means. This is probably beyond the scope of RCOS.java.

8088 Details

Memory

Divided into 8 bit bytes, instructions can also operate on 16 bit words.

8088 can address 1Mb of RAM by using 20 bit physical addresses (PCs reserve addresses greater than 640K for console display and ROM s/w).

Uses two 16 bit logical addresses to form the one 20 bit physical address of the form SEGMENT:OFFSET. Translation is performed by SEGMENT*16 + OFFSET. Multiplying by 16 = to add low-order 0.

8088 does not support any form of memory management

Interrupts

First 1K of memory from 00000 to 003FF is used for interrupt vectors. Interrupt vector is a four byte segment:offset address of code to be executed upon receipt of a h/w or s/w interrupt. 1K gives space for 256 interrupt vectors.

Registers

8088 contains 12 16-bit registers, an instruction pointer and a 16-bit FLAGS register, summarised in following table.

Register	Use
AX	general purpose
BX	general purpose
CX	general purpose
DX	general purpose
SP	stack pointer
BP	base pointer
SI	source index
DI	destination index
CS	code segment
DS	data segment
ES	extra segment
SS	stack segment
IP	instruction pointer
FLAGS	flags word

CS:IP - segment:offset address of the next instruction
DS:?? - offset for data
SS:SP - stack address
SS:BP - point to the stack frame on the run-time stack

Educational Operating Systems

Problems students have with Operating Systems

The content of an OS course is often very theoretical. Most of the problems in operating systems is taking general, theoretical discussion and extending it and seeing it in a real life situation. A realistic project is especially important in undergraduate operating systems courses, where many of the concepts are best taught, we believe, by example and experimentation. Nachos paper Problems that students have include

Big picture or base knowledge

• what actually is an OS
• what are the components of an OS
• how are they structured and what are the advantages of the different methods
• what is an interrupt
• four classes of interrupts and examples
• interrupt handling
• instruction execution cycle
• the interaction between user, user program (relationship between programming language and machine language), system call, operating system and hardware

Processes

• what is a process, program
• difference between thread of execution (thread) and resource ownership (process)
• difference between a process switch and a context switch
• process scheduling algorithms
• important characteristics for process scheduling (throughput, turnaround time..)
• priorities and starvation

Concurrency

• what is a critical sections,
• why do we need mutual exclusion,
• what is a race condition,
• what is deadlock
• how do semaphores, shared memory, monitors, message passing etc work
• the difference between create and open of semaphores/shared memory

Memory Management

• how various MM algorithms actually work, their data structures etc
• characteristics of MM algorithms
• resident set versus working set
• difference between page placement and page replacement
• the close ties between hardware and OS in address translation and which part is done where
• use of caches, where and when
• difference between paging and segementation, where would you use them, the advantages of both

Disk and File management

• disk scheduling how and why do it
• the concept of a layered file system, which responsibilities go where, what are those responsibilities
• data structures used to track block allocation to files, files to directories and free blocks

RCOS

Most obvious candidate, the experience of designing (at least observing the design) and using RCOS will aid development of RCOS.java. Problems with RCOS that need fixing

• design that is not truly OO, needs some redesign to be more portable and also to work within restrictions (no pointers, multiple inheritance) and advantages (inherent portability means no longer any need for platform abstraction layer) of Java
• amount and level of comments throughout source code below what is needed for CQU students
• the simulation is less than clear in areas including
  • interrupts
  • instruction execution cycle
  • separation between h/w and OS, students still having difficulty knowing which code belongs where
• portability of the code is questionable, won't run on some machines (MS-DOS), won't run mouse etc, troubles compiling
• lack of documentation that explains structure

Nachos

Wayne A. Christopher, Steven J. Procter, Thomas E. Anderson, The Nachos Instructional Operating System, Proceedings Usenix Winter Technical Conferences, San Diego, January 1993, pp 25-29

Challenges in building Nachos

• tradeoff between simplicity and realism
• balance between time students spend reading code versus adding features to existing code versus learning new concepts

Nachos assignments used to demonstrate

• computer system design,
• concurrency and synchronization,
• caching and locality,
• tradeoff between simplicity and performance,
• building reliability from unreliable components
• dynamic scheduling
• the power of a level of translation
• layering
• distributed computing

Aim is to provide the simplest implementation for each sub-system to provide a working base. The students are asked to add functionality and improve performance. Nachos is about 2500 lines of code, half of which are devoted to interface descriptions and comments.

Nachos features

• UNIX based.
• use programs are C programs compiled for the MIPS R2/3000 integer instructions
• can simulate a network of workstations with separate Nachos processes communicating
• deterministic simulation via a simulated time that is incremented whenever user program executes or low-level OS routines are called. Interrupt handlers are then invoked when the simulated time reaches the appropriate point
• simulation is randomizable
• h/w simulation routines are hidden from the reas of nachos via machine-dependent interface layer
• implemented in a subset of C++
• assignments take a quantitative approach to operating system design

Nachos threads normally non-preemptive but has a command line option that causes threads to be time-sliced at "random".

Nachos CRC

Please note the information contained on the following pages is obtained directly from the Nachos source code.

Devices	Interrupts	CPU and machine
Console Disk	Interrupt PendingInterrupt	Instruction Machine Timer TranslationEntry
Network	File System	Threads
PacketHeader Network MailHeader Mail MailBox PostOffice	DirectoryEntry Directory FileHeader FileSystem OpenFile SynchDisk	Scheduler Thread
Synchronization	User Programs	Miscelanous
Semaphore Lock Condition SynchList	AddrSpace	Statistics ListElement List BitMap

Tunix

Robert Switzer, Operating Systems: A Practical Approach, Prentice-Hall, 1993

Operating system in C but with architecture similar to RCOS including

• kernel responsible for
  • message passing
  • catching page faults and sending messages to MM
  • catching interrupts from peripheral devices and sending messages to PM (process manager)
  • catch interrupts from system clock and send messages to PM
  • carry out task switches on the h/w level with appropriate CPU instructions
  • build and destroy page tables according to directions from MM
• file manager
• drivers
• memory manager
• inter-process communication manager (messages etc)

All Tunix processes (MM, FM, IPCM etc) are implemented as independent UNIX processes.

You can't execute user programs with TUNIX not directly anyway. You can by linking a UNIX C program with some stubs that uses messages to communicate.

Tunix Threads

Following table summarises Tunix threads.

Function	Purpose
thrd_init()	Called only once and must be called before other thread routines. Initializes the thread system and saves the context. Used for when a thread_end is reached, control passes back to instruction just after thread_init.
thrd_start()	Start new thread (and generate new context)
thrd_end()	terminates previously started thread and destroy corresponding context, switch to any non-suspended threads, otherwise restart context saved by thread_init
thrd_sleep( EVENT ev )	suspend thread until EVENT occurs, if other threads active switch to them otherwise start context saved by thrd_init
thrd_wakeup( EVENT ev )	All threads that are suspended on EVENT are waken up.

File System

Implements a very UNIX like file system with superblocks, inodes etc Modules in Tunix file system include

• fm - main module
• knows who the client processes are and keeps information about them in particular the process file table
• sys - manages the table of all open files, mediates between proc and the more basic routines in inode, buffer, etc
• dir - implements the concepts directory and path
• super - implements super blocks, disk inodes, free list for linear blocks
• inode - implements data abstraction inode
• buffer
• kcall - implements system requests to kernel
• devcall - implements communication with device drivers
• raw - implements direct data transfers between device driver and user
• comm - implements receive and reply
• chan - implements communication channels
• thread - implements the threads

Memory Management

Uses the abstraction region (also used by Unix). Each process owns several regions

• TEXT (code)
• DATA_W (initialized data)
• BSS (uninitialized data, blank static storage)
• DATA_R (read-only data)
• STACK

Tunix further divides regions into pages and assumes that it has h/w paging support.

Modules in Tunix MM include

• MM - manages communication with the other processes
• pregion - maintains a process region table for all processes
• region - implements the concept region
• frame - i mplementes the abstract data type frame
• swap - implements the actual swapping in and out
• fmcall - manages communication with FM
• kcall - manages system requests to the kernel
• memmap - administers the heap for the arrays in region
• devcall - manages communication with the driver of the swap device

Process Management

Implements management system between RCOS and UNIX, closer to UNIX.

Modules include

• pm - manages communication between PM and other processes
• proc - administers the process table, implements system calls
• callout - implements the callout table for the system call alarm
• fmcall - manages the communication with FM
• mmcall
• ipccall
• kcall

IPC

Implement semaphores, messages and shared memory.

OSP

Tunis

Holt, R. Concurrent Euclid, the UNIX System and TUNIS, Addison-Wesley, 1983

Minix

Xinu

PRMS