Advanced Operating Systems Design, Implementation, and Real Time Stanley A. Wileman, Jr. University of Nebraska at Omaha This is an incomplete work-in-progress. It is primarily intended for the students in Computer Science 8530 at the University of Nebraska at Omaha.iiCopyright, 2007, Stanley A. Wileman, Jr.iiiTable of Contents (Topics) — Not Nearly Final Table of Contents (Topics) Table of Contents (Detailed) List of Figures List of Tables Preface Part I – The Tempo Operating System 1. Introduction 2. The Tempo Operating System 3. Processes 4. Interrupt Handling 5. Memory Management 6. System Services 7. Input/Output 8. File Systems 9. Ethernet Services 10. TCP/IP 11. CIFS (Common Internet File System) Part II – Real-Time Systems and Programming 12. Introduction to Real-time 13. POSIX Real-time Extensions 14. It’s About Time 15. Signals 16. Semaphoresiv 17. Messages 18. Memory, Sharing and Locking 19. Real-time Input/Output 20. Real-time Scheduling 21. Priority Inversion, Solutions Appendices A. Obtaining and Installing Tempo B. Tempo Development Environment: Cygwin and Bochs C. Device/Chipset Details (Datasheet abstractions) C.1 Intel 8237 DMA Controller C.2 Intel 8254 Programmable Interval Timer C.3 Intel 8259A Programmable Interrupt Controller C.4 Maxim 14285 Real-Time Clock C.5 XXX – 6845 Video Controller C.6 XXX – 16550 UART C.7 XXX – Parallel port C.8 XXX – NatSemi DP8390 NIC C.9 XXX – Intel 8042 (keyboard) D. References XXX – Books XXX – Manuals XXX – Web Sites IndexIntroduction Advanced Operating Systems — Design, Implementation, and Real Time 1Introduction 1 These notes are provided for those individuals who need to gain a more complete understanding of operating systems than is provided by a typical undergraduate course. The notes are currently a “work in progress” and suggestions to the author are welcome. 1.1 Background and Prerequisites All undergraduate computer science curriculum recommendations include a course on operating systems. This required course is not one in which the user is taught how to enter commands, create and list directories, and install and maintain the operating system. These are certainly appropriate skills, but don’t provide the understanding of operating systems expected by the designers of computer science curricula. Instead, the undergraduate operating systems course that is an appropriate prerequisite for this material covers the purposes of an operating system, the variety of designs possible, and the traditional algorithms used in an operating system implementation. Two topics covered in some depth in that course are concurrency and mutual exclusion. These topics are not exclusively part of the operating system domain, but the undergraduate operating systems course is usually the first one in which students are exposed to these topics. There is a wealth of information to be covered in the undergraduate course, and it is rare that students have many opportunities to engage in significant implementation tasks (except for small “toy” projects). Indeed, it is usually the case that there is insufficient time in the course to cover all of the background material. 1.2 The Approach There are two parts to the material in these notes. Although they are presented sequentially, the material in the first part will prove beneficial later. 1.2.1 Design and Implementation of the Tempo Operating System We will first examine in detail the design and implementation of an operating system called Tempo. This is not a “toy” operating system of the kind that is usually provided for use with undergraduate operating system textbooks (with some exceptions). Instead, it is a complete system that can boot and run on most typical x86-based personal computers. There are numerous goals we hope to achieve by studying this system: • Better understanding of the purpose of system calls: By examining the detail of how system resources and services are provided to application programs, we can better appreciate the facilities provided by those operating systems we typically use (e.g. Microsoft Windows and UNIX varieties).Introduction 2• Better understanding of design alternative and their effects: There are often multiple approaches that can be taken to manage the resources of a computer system, each with positive and negative consequences. A real operating system will allow us to examine the effects of such design decisions. • Better understanding of existing operating systems: By examining the design and implementation of Tempo, we will gain insights into how popular operating systems deal with similar issues. • Better understanding of concurrency and mutual exclusion: Reading about concurrency and studying classic algorithms for synchronization is valuable, but seeing the implementation and use of these in a real operating system gives real understanding of them. We know that modern processors have almost reached the “legal” speed limit, and understand that only by utilizing multiple processes running on multiple processors will we achieve additional performance gains. Multiple processes concurrently or simultaneously working on the same data must be synchronized. • Better understanding of how applications can use system services: Every application uses the services of the operating system, but those services are usually hidden below a layer of library functions. Application designers often overlook available facilities and resources because they mistakenly limit themselves to the features provided by a particular programming language. Even if only those language-provided facilities are used, understanding the system services their implementations use will improve the application designer’s understanding of the cost of those facilities. 1.2.2 Introduction to Real-Time1 Systems and Applications The second part of these notes provides introductory material on real-time systems and programming. Real-time systems have two parts: a real-time operating system and one or more real-time applications. It is common for such systems to be dedicated to running those applications (as opposed to attempting to be general-purpose, or all things to all applications). If you could successfully enumerate all the computer systems and applications in use at any instant, you would find that perhaps as much as ninety percent of