Sistemas Operativos

M09_STAL6329_06_SE_C09.QXD

2/21/08

9:32 PM

Page 404

PART FOUR
Scheduling

A

n operating system must allocate computer resources among the potentially competing requirements of multiple processes. In the case of the processor, the resource to be allocated is execution time on the processor and the means of allocation is scheduling. The scheduling function must be designed tosatisfy a number of objectives, including fairness, lack of starvation of any particular process, efficient use of processor time, and low overhead. In addition, the scheduling function may need to take into account different levels of priority or real-time deadlines for the start or completion of certain processes. Over the years, scheduling has been the focus of intensive research, and manydifferent algorithms have been implemented. Today, the emphasis in scheduling research is on exploiting multiprocessor systems, particularly for multithreaded applications, and real-time scheduling.

ROAD MAP FOR PART FOUR
Chapter 9 Uniprocessor Scheduling
Chapter 9 concerns scheduling on a system with a single processor. In this limited context, it is possible to define and clarify many design issuesrelated to scheduling. Chapter 9 begins with an examination of the three types of processor scheduling: long term, medium term, and short term. The bulk of the chapter focuses on short-term scheduling issues. The various algorithms that have been tried are examined and compared.

Chapter 10 Multiprocessor and Real-Time Scheduling
Chapter 10 looks at two areas that are the focus of contemporaryscheduling research. The presence of multiple processors complicates the scheduling decision and opens up new opportunities. In particular, with multiple processors it is possible simultaneously to schedule for execution multiple threads within the same process. The first part of Chapter 10 provides a survey of multiprocessor and multithreaded scheduling. The remainder of the chapter deals withreal-time scheduling. Real-time requirements are the most demanding for a scheduler to meet, because requirements go beyond fairness or priority by specifying time limits for the start or finish of given tasks or processes.

404

M09_STAL6329_06_SE_C09.QXD

2/21/08

9:32 PM

Page 405

CHAPTER

UNIPROCESSOR SCHEDULING
9.1 Types of Professor Scheduling Long-Term Scheduling Medium-TermScheduling Short-Term Scheduling Scheduling Algorithms Short-Term Scheduling Criteria The Use of Priorities Alternative Scheduling Policies Performance Comparison Fair-Share Scheduling Traditional UNIX Scheduling Summary Recommended Reading Key Terms, Review Questions, and Problems Response Time 9.2

9.3 9.4 9.5 9.6

APPENDIX 9A

APPENDIX 9B Queuing Systems Why Queuing Analysis? TheSingle-Server Queue The Multiserver Queue Poisson Arrival Rate

405

M09_STAL6329_06_SE_C09.QXD

2/21/08

9:32 PM

Page 406

406

CHAPTER 9 / UNIPROCESSOR SCHEDULING

In a multiprogramming system, multiple processes exist concurrently in main memory. Each process alternates between using a processor and waiting for some event to occur, such as the completion of an I/O operation.Theprocessor or processors are kept busy by executing one process while the others wait. The key to multiprogramming is scheduling. In fact, four types of scheduling are typically involved (Table 9.1). One of these, I/O scheduling, is more conveniently addressed in Chapter 11, where I/O is discussed.The remaining three types of scheduling, which are types of processor scheduling, are addressed in thischapter and the next. This chapter begins with an examination of the three types of processor scheduling, showing how they are related.We see that long-term scheduling and medium-term scheduling are driven primarily by performance concerns related to the degree of multiprogramming.These issues are dealt with to some extent in Chapter 3 and in more detail in Chapters 7 and 8.Thus, the remainder of...