《操作系统基础基本理论、基本方法复习》由会员分享，可在线阅读，更多相关《操作系统基础基本理论、基本方法复习（18页珍藏版）》请在金锄头文库上搜索。
1、Chapter 1 Introduction1. Abstract View of System Components2. Multiprogrammed Batch SystemsSeveral jobs are kept in main memory at the same time, and the CPU is multiplexed among them. Chapter 2: Computer-System Structures1. Computer-System Architecture2. Interrupt Time Line For a Single Process Doi
2、ng Output3. Moving-Head Disk Mechanism4. Direct Memory Access Structure5. Storage-Device Hierarchy6. Use of A Base and Limit Register7. Hardware Address ProtectionChapter 3: Operating-System Structures1. MS-DOS Execution2. MS-DOS Layer StructureChapter 4: Processes1. Diagram of Process State2. Proce
3、ss Control Block (PCB)3. CPU Switch From Process to Process4. Representation of Process Scheduling5. Addition of Medium Term SchedulingChapter 5: Threads1. Single and Multithreaded Processes2. Many-to-One Model3. One-to-one Model4. Many-to-Many ModelChapter 6: CPU Scheduling1. Alternating Sequence o
4、f CPU And I/O Bursts2. First-Come, First-Served (FCFS) SchedulingProcessBurst TimeP124 P2 3 P3 3 l Suppose that the processes arrive in the order: P1 , P2 , P3 The Gantt Chart for the schedule is:l Waiting time for P1 = 0; P2 = 24; P3 = 27l Average waiting time: (0 + 24 + 27)/3 = 173. Example of Non
5、-Preemptive SJFProcessArrival TimeBurst Time P10.07 P22.04 P34.01 P45.04l SJF (non-preemptive)l Average waiting time = (0 + 6 + 3 + 7)/4 - 4 4. Example of Preemptive SJFProcessArrival TimeBurst Time P10.07 P22.04 P34.01 P45.04l SJF (preemptive)l Average waiting time = (9 + 1 + 0 +2)/4 - 3 5. Example
6、 of RR with Time Quantum = 20ProcessBurst TimeP153 P2 17 P368 P4 24l The Gantt chart is: l Typically, higher average turnaround than SJF, but better response.6. Dispatch LatencyChapter 7: Process Synchronization1. Implementation Semaphore operations now defined as wait(S):S.value-; if (S.value 0) ad
7、d this process to S.L;block;signal(S): S.value+;if (S.value = 0) remove a process P from S.L;wakeup(P);2. Deadlock two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes. Let S and Q be two semaphores initialized to 1P0 P1 wait(S);wait(Q);
8、wait(Q);wait(S); M M signal(S);signal(Q);signal(Q)signal(S);3. Bounded-Buffer Problem Shared datasemaphore full, empty, mutex;Initially:full = 0, empty = n, mutex = 1Problem Producer Processdo produce an item in nextp wait(empty);wait(mutex); add nextp to buffer signal(mutex);signal(full); while (1)
9、;Problem Consumer Processdo wait(full)wait(mutex); remove an item from buffer to nextc signal(mutex);signal(empty); consume the item in nextc while (1);4. Readers-Writers Problem Shared datasemaphore mutex, wrt;Initiallymutex = 1, wrt = 1, readcount = 0Writer Processwait(wrt); writing is performed s
10、ignal(wrt);Reader Processwait(mutex);readcount+;if (readcount = 1)wait(rt);signal(mutex); reading is performed wait(mutex);readcount-;if (readcount = 0)signal(wrt);signal(mutex):5. Dining-Philosophers Problem Shared data semaphore chopstick5;Initially all values are 1 Philosopher i:do wait(chopstick
11、i)wait(chopstick(i+1) % 5) eat signal(chopsticki);signal(chopstick(i+1) % 5); think while (1);Chapter 8: Deadlocks1. Example of a Resource Allocation Graph2. Basic Facts If graph contains no cycles no deadlock. If graph contains a cycle if only one instance per resource type, then deadlock. if sever
12、al instances per resource type, possibility of deadlock.3. Safe State When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state. System is in safe state if there exists a safe sequence of all processes. Sequence is safe if for each Pi
13、, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, with jI. If Pi resource needs are not immediately available, then Pi can wait until all Pj have finished. When Pj is finished, Pi can obtain needed resources, execute, return allocated resources, and terminate. When Pi terminates, Pi+1 can obtain its needed resources, and so on. 4. Bankers Algorithm Multiple instances. Each process must a priori claim maximum use. When a process requests a resource it may have to wait. When a process gets all its
