Solution Manual for Real Time System by Jane W. S. Liu

Real Time System by Jane W. S. Liu (Pearson), the book builds on the student's background in Operating System, Embedded System. It covers techniques for scheduling, resource access control, and validation that are, or are likely to be, widely used in real time computing and communication systems. Each algorithm, protocol, or mechanism is defined by pseudo code or simple rules that can serve as a starting point of implementation. With few exceptions, each scheduling algorithm is accompanied that your application will meet its real time requirement when scheduling according to the algorithm.

Here, in next successive posts, I am going to post solutions for the same Text-book (Real Time System by Jane W. S. Liu). If you find any difficulty or wants to suggest anything, feel free to comment...:)

:: Solutions ::
Exercise 3.1
Exercise 3.2
Exercise 3.3
Exercise 3.4
Exercise 4.1
Exercise 4.2
Exercise 4.4
Exercise 4.5
Exercise 4.7
Exercise 5.1(a) & (b)
Exercise 5.1(c) & (d)
Exercise 5.1(e) & (f)
Exercise 5.2
Exercise 5.3
Exercise 5.4
Exercise 6.4
Exercise 6.5
Exercise 6.6
Exercise 6.7
Exercise 6.8
Exercise 6.9
Exercise 6.10
Exercise 6.11
Exercise 6.13
Exercise 6.15
Exercise 6.21
Exercise 6.23
Exercise 6.31
Exercise 7.1
Exercise 7.2
Exercise 7.3
Exercise 7.4
Exercise 7.5
Exercise 7.19
Exercise 7.23
Exercise 8.1
Exercise 8.2
Exercise 8.3
Exercise 8.7
Exercise 8.10

Friends, 

       Thank you for such a huge response. I tried to cover all important topics and exercise in textbook, Real Time System by Jane W. S. Liu. Still, if you feel any difficulty or any suggestions, feel free to contact me here or you can straightway comment on any post (It will be better for you and others, too).


For more details: http://www.neerajbokde.com/

Editorial Reviews

From the Inside Flap

Preface

This text grew from my lecture notes of a course on real-time systems, which I have been teaching regularly for the past six years. The course is a technical elective for seniors and graduate students in Computer Science and Computer Engineering. It requires as a prerequisite an undergraduate course on operating systems.

Like the course, the book builds on the student's background in operating systems. It covers techniques for scheduling, resource access control, and validation that are, or are likely to be, widely used in real-time computing and communication systems. Each algorithm, protocol, or mechanism is defined by pseudocode or simple rules that can serve as a starting point of implementation. With few exceptions, each scheduling algorithm is accompanied by one or more validation techniques. You can use the techniques to ascertain that your application will meet its real-time requirements when scheduled according to the algorithm.

In addition to information on existing techniques, the book emphasizes basic principles of realtime systems. The foundations of these techniques are presented as theorems and corollaries. (I would like to have avoided this style, but feared that they might be buried in the narratives and details if not thus highlighted. I tried to keep them and their proofs informal.) I cover many of the theorems and proofs in my course in order to give students insight into why and how well the techniques work, and teach them the skills they will need to extend the existing techniques and develop new ones.

While this coverage may make the book a good reference for practitioners, a developer who wants to get information quickly may find its presentation verbose. The summary section at the end of each chapter should help. It gives you either the information you are looking for, or a pointer to the section where you can find the information.

Comments on Contents. The focus of the book is real-time operating systems and networks. It starts with a small part (Chapters 1, 2 and 3) on real-time applications and systems in general. It ends with a part (Chapters 11 and 12) on specific attributes and implementations of network protocols and operating systems. The large part (Chapters 4-10) in the middle covers uniprocessor scheduling, resource access control, and multiprocessor and distributed scheduling. Sections and subsections marked by * are included for the sake of completeness. You can skip over them without loss of continuity.

Chapters 1 and 2. Chapter 1 gives an overview of several sample real-time applica dons for which the techniques described in the book were developed. I find most computer science and engineering students in my classes are unfamiliar with these applications. The chapter tries to explain for them the characteristics of workloads generated by the applications and the reasons for their timing requirements. Chapter 2 follows by giving the definitions of hard and soft real-time systems and the rationales for this classification.

Chapter 3. Chapter 3 describes a reference model of real-time systems. Subsequent chapters (e.g., 4-10) characterize the systems we study according to special variants of the model. The reference model has a rich set of features. We can describe a wide spectrum of real-time applications and underlying platforms in a sufficiently faithful manner in terms of the model so that we can analyze, simulate, and even emulate the system based on the description; indeed, some scheduling and validation tools use this kind of description as input. However, many features of the model are not used in later chapters. Sections describing them are marked by *.

Chapters 4-9. These six chapters describe algorithms and protocols for scheduling and validating real-time systems. In particular, they cover the time-driven approach, the RMA technology, and the dynamic-priority approach.

Chapter 4 gives a brief overview of the three approaches to scheduling: clock-driven, weighted round-robin, and priority-driven, which are treated in depth in later chapters. It also highlights some important facts about priority-driven scheduling. I discuss these facts in the beginning of my course as a way to motivate the techniques to be discussed in the weeks to come. Even if a student drops the course early in the semester, he/she will walk away knowing these facts.

Chapter 5 describes the clock-driven approach in general and cyclic executives in specific. This is the traditional way to schedule more or less deterministic workloads and is still the way used to schedule safety-critical applications.

Chapters 6, 7, and 8 are devoted to algorithms for scheduling and resource access control on one processor (i.e., a CPU, or a network link, I/O bus, a disk, and so on). Most of these algorithms are priority-driven; all of them can be implement easily on modern real-time operating systems and communication networks. The chapters adopt increasingly more complex variants of the periodic-task model: Chapter 6 starts from workloads consisting solely of independent periodic tasks that do not require any resource other than a processor. Chapter 7 adds aperiodic and sporadic tasks, and Chapter 8 adds resource contentions.

Chapter 9 is on multiprocessor and distributed systems. It introduces control and data dependencies among tasks and the end-to-end nature of their timing requirements. It then describes methods for partitioning an application into modules and assigning the modules to processors, controlling their access to resources on multiple processors, and synchronizing the execution of tasks on different processors.

Together, Chapters 6-9 give a comprehensive treatment of the RMA approach, which in essence is synonymous to fixed-priority scheduling. Most algorithms based on this approach allow application components to be added and deleted at run-time and can handle nondeterministic resource demands. The timing behavior of applications scheduled according to the algorithms are nondeterministic. However, the adverse effects of scheduling anomalies are bounded when fluctuations in resource demands are bounded. For most real-time applications, such as those described in Chapter 1, the accompanied validation techniques make it possible for us to predict fairly accurately the worstcase real-time performance of applications thus scheduled. The chapters also describe ways to schedule applications with widely varying resource demands within the deadline-driven framework. As examples, rate-based algorithms can provide timing isolation to sporadic tasks and enables us to predict the real-time performance of a distributed sporadic task independent of other tasks in the system.

Chapter 10. Chapter 10 introduces the concept of flexible applications. A flexible application contains tasks that can trade off the qualities of their results for their time and resource demands. The flexible computation approach is a means for handling overload and increasing availability. This chapter describes workload models that capture the characteristics and requirements of flexible applications and algorithms that have been developed to schedule them. Another subject of discussion is the temporal distance model. The timing requirements of some real-time tasks can be more conveniently defined in the terms of the maximum length of time between completions of consecutive task instances. The temporal distance model captures this kind of requirement.

Chapter 11. Chapter 11 focuses on real-time issues in communication networks, specifically, features and capabilities needed to support real-time applications. It starts by describing low-level, realtime flow control, and scheduling schemes for packet switched networks and medium access protocols for broadcast networks. It then describes resource reservation, internet and transport protocols designed for real-time applications.

Chapter 12. The last chapter examines in depth implementation details that were ignored in earlier chapters. It consists of two parts. The first part discusses how operating systems services and mechanisms should be implemented to enhance the predictability of applications using them. Some services and mechanisms are easy to implement, have low overhead, and can make the implementation of many algorithms described in previous chapters significantly simpler, but are not provided by most commercial operating systems. This part describes examples of them.

The second part gives an overview of several commercial real-time and general purpose operating systems. It highlights good features of real-time operating systems. It explains why Windows NT and Linux, two popular general purpose operating systems, do not work well for real-time applications and how to get better predictability out of them.

From the Back Cover

Written by a renowned expert, Real-Time Systems provides professionals and students with a comprehensive treatment of real-time computing and communication systems. The book covers the most recent advances in real-time operating systems and communications networks. Thus, this book serves as a vehicle for technology transition within the real-time systems community of systems architects, designers, chief scientists and technologists, and systems analysts. Jane Liu's subject matter and adept treatment provide an engaging learning environment for students as well. With real-time systems, the technologies at play include telecommunication, signal processing, command and control, and digital control. Their applications have particular relevance to day-to-day operations, such as engine and break mechanisms in cars, traffic light operations, flight control and air-traffic control, and heart beat and blood pressure monitoring.

Real-Time Systems is both a valuable reference for professionals and an advanced text for Computer Science and Computer Engineering students.

• Real world real-time applications based on research and practice


• State-of-the-art algorithms and methods for validation


• Methods for end-to-end scheduling and resource management


• More than 100 illustrations to enhance understanding


• Comprehensive treatment of the technology known as RMA (rate-monotonic analysis) methods