《計算機操作系統(tǒng)》課程教學大綱

1、計算機操作系統(tǒng)課程教學大綱課程編號學分3.5總學時64理論54實驗/上機10英文課程名Operating Systems開課院（系）信息學院開課系計算機系、網(wǎng)絡系修訂時間2006年9月1日課 程 簡 介“計算機操作系統(tǒng)”是計算機應計算機科學與技術專業(yè)學生必修的重要專業(yè)基礎課，是一門涉及較多硬件知識的計算機系統(tǒng)軟件課程。在計算機軟硬件課程的設置上，它起著承上啟下的作用。其特點是概念多、較抽象和涉及面廣，其整體實現(xiàn)思想和技術難于理解。操作系統(tǒng)對計算機系統(tǒng)資源實施管理，是所有其他軟件與計算機硬件的唯一接口，所有用戶在使用計算機時都要得到操作系統(tǒng)提供的服務。操作系統(tǒng)技術是衡量一個國家計算機技術整體實力

2、和創(chuàng)新能力的關鍵。本課程主要內容包括：操作系統(tǒng)引論、進程管理、存儲器管理、文件系統(tǒng)、設備管理等方面的概念和技術方法等。課 程 大 綱一、課程的性質與任務： 操作系統(tǒng)是計算機科學與技術專業(yè)的主干課程，它綜合了計算機軟件和硬件技術，具有很強的系統(tǒng)性，是衡量教學質量和學生專業(yè)技能整體水平的重要課程。操作系統(tǒng)技術的掌握與應用決定了一個國家計算機系統(tǒng)軟件的研發(fā)能力，是培養(yǎng)計算機創(chuàng)新人才的重要途徑。學生通過本課程的學習，理解操作系統(tǒng)的基本概念和主要功能，它是如何組織和運作的，從而在本質上掌握計算機系統(tǒng)的運行機制，為迅速發(fā)展我國自己的操作系統(tǒng)，振興我國信息產(chǎn)業(yè)打下堅實基礎。二、課程的目的與基本要求：l 本課

3、程的目的掌握操作系統(tǒng)這一重要系統(tǒng)軟件的結構與構造，它的各組成部分的具體工作原理與技術實現(xiàn)方法,各部分之間的相互聯(lián)系。通過系統(tǒng)的學習，學生站在一定高度掌握計算機系統(tǒng)的軟硬件協(xié)作關系和整體工作原理，為今后從事專業(yè)工作打下堅實基礎。l 基本要求1、 掌握理論上的重要概念和重要技術，例如多道程序、并發(fā)、分時、進程、進程間通信、虛擬存儲器等。2、 由于本課程難度很高，對于專業(yè)技術經(jīng)驗不足的一般學生來講本課程的內容不容易消化和掌握，加上課內學時有限等因素，建議教學過程中多建設網(wǎng)絡視頻資源，教師將講授之內容以網(wǎng)絡教學資源的形式提供給學生，一方面便于學生課前預習、課后復習，突破學時限制，另一方面為交互式教學和

4、自主式學習創(chuàng)造條件，而且可以擴大課堂容量。3、 知識掌握要有層次結構。第一個層次是主流操作系統(tǒng)(類UNIX)的常用命令，第二個層次是學會用系統(tǒng)調用編寫C語言應用程序，第三個層次是操作系統(tǒng)原理的掌握。這種層次結構教學方法保證不同層次的學生均有收獲和成就感，也體現(xiàn)了由淺入深、由表及里的教學方法的靈活運用。4、 教學過程避免“重理論、輕實踐”的現(xiàn)象，應該緊密結合一個具體操作系統(tǒng)來幫助學生理解深奧的理論與技術。三、面向專業(yè)計算機科學與技術、信息管理與信息系統(tǒng)四、先修課程計算機組成原理、匯編語言、C語言程序設計、數(shù)據(jù)結構。五、本課程與其它課程的聯(lián)系操作系統(tǒng)是一門綜合性較強的課程，需要學生有一定的計算機硬

5、件基礎知識，而操作系統(tǒng)本身是一個大型的系統(tǒng)軟件，它的功能是通過定義數(shù)據(jù)結構和程序描述來實現(xiàn)的。為此，學習本課程之前學生應具備計算機組成、匯編語言、C語言程序設計、數(shù)據(jù)結構等方面的知識。操作系統(tǒng)又是其它許多后續(xù)課程如計算機網(wǎng)絡、編譯原理、軟件體系結構等的先行課程，它為進一步學習后續(xù)課程打下基礎。六、教學內容安排、要求、學時分配及作業(yè)： 第一章 引言(INTRODUCTION)，(理論2學時，實驗2學時)§1.1什么是操作系統(tǒng)(WHAT IS AN OPERATING SYSTEM?)從功能擴展機和資源管理器兩個角度掌握操作系統(tǒng)的概念(Extended Machine & Res

6、ource Manager)作業(yè)：1. What are the two main functions of an operating system?2. What is the difference between kernel mode and user mode? Why is the difference important to an operating system?§1.2 操作系統(tǒng)歷史(HISTORY OF OPERATING SYSTEMS)結合硬件發(fā)展了解操作系統(tǒng)的由來，通過現(xiàn)有的操作系統(tǒng)產(chǎn)品重點掌握分時系統(tǒng)和多任務系統(tǒng)的概念。作業(yè)：1. What is mult

7、iprogramming?2. What is spooling? Do you think that advanced personal computers will have spooling as a standard feature in the future?§1.3 操作系統(tǒng)中的重要概念(OPERATING SYSTEM CONCEPTS)結合實際抽象出并理解進程、文件、shell等概念。(Processes, Files, and Shell)作業(yè)：1. Write a shell that is similar to Fig. 1-10 but contains en

8、ough code that it actually works so you can test it. You might also add some features such as redirection of input and output, pipes, and background jobs.§1.4 系統(tǒng)調用(SYSTEM CALLS)通過演示UNIX下的帶有系統(tǒng)調用的C語言程序，使學生理解操作系統(tǒng)中各種主要的系統(tǒng)調用功能和使用方法。作業(yè)：1. Write a program (or series of programs) to test all the MINIX

9、3 system calls. For each call, try various sets of parameters, including some incorrect ones, to see if they are detected.§1.5 操作系統(tǒng)結構(OPERATING SYSTEM STRUCTURE)一般了解單一結構、分層結構、虛擬機操作系統(tǒng)，理解微內核操作系統(tǒng)結構。作業(yè)：1. Examine the difference between a micro-kernel system and a monolithic system第二章 進程(PROCESSES),

10、 (理論16學時，實驗2學時)§2.1 進程引言(INTRODUCTION TO PROCESSES)，1學時掌握進程模型，理解進程實現(xiàn)，了解線程作業(yè)：1. Why is multiprogramming central to the operation of a modern operating system?2. What are the three main states that a process can be in? Describe the meaning of each one briefly.§2.2 進程間通信(INTERPROCESS COMMUNIC

11、ATION)，2學時理解競爭條件、臨界區(qū)、臨界資源以及信號量的概念，掌握用信號量解決進程同步與互斥的方法作業(yè)：1. Does the busy waiting solution using the turn variable work when the two processes are running on a shared-memory multiprocessor, that is, two CPUs, sharing a common memory?2. Consider a computer that does not have a TEST AND SET LOCK instruc

12、tion but does have an instruction to swap the contents of a register and a memory word in a single indivisible action. Can that be used to write a routine enter_region such as the one found in Fig. 2-12?3. Give a sketch of how an operating system that can disable interrupts could implement semaphore

13、s.4. Show how counting semaphores (i.e., semaphores that can hold an arbitrarily large value) can be implemented using only binary semaphores and ordinary machine instructions.5. In a situation with a high-priority process, H, and a low-priority process, L, was described, which led to H looping fore

14、ver. Does the same problem occur if round-robin scheduling is used instead of priority scheduling? Discuss.§2.3 經(jīng)典進程同步問題(CLASSICAL IPC PROBLEMS)，1學時掌握進餐的哲學家問題，了解讀者-寫者和理發(fā)師問題作業(yè)：1. In the solution to the dining philosophers problem (Fig. 2-20), why is the state variable set to HUNGRY in the proced

15、ure take_forks?2. Consider the procedure put_forks in Fig. 2-20. Suppose that the variable statei was set to THINKING after the two calls to test, rather than before. How would this change affect the solution for the case of 3 philosophers? For 100 philosophers?3. The readers and writers problem can

16、 be formulated in several ways with regard to which category of processes can be started when. Carefully describe three different variations of the problem, each one favoring (or not favoring) some category of processes. For each variation, specify what happens when a reader or a writer becomes read

17、y to access the data base, and what happens when a process is finished using the data base.§2.4 進程調度(SCHEDULING)，1學時掌握輪轉和多級隊列調度算法作業(yè)：1. Round- robin schedulers normally maintain a list of all runnable processes, with each process occurring exactly once in the list. What would happen if a process

18、 occurred twice in the list? Can you think of any reason for allowing this?2. Five batch jobs A through E, arrive at a computer center at almost the same time. They have estimated running times of 10, 6, 2, 4, and 8 minutes. Their (externally determined) priorities are 3, 5, 2, 1, and 4, respectivel

19、y, with 5 being the highest priority. For each of the following scheduling algorithms, determine the mean process turnaround time. Ignore process switching overhead.(a) Round robin.(b) Priority scheduling.(c) First-come, first-served (run in order 10, 6, 2, 4, 8).(d) Shortest job first. For (a), ass

20、ume that the system is multiprogrammed, and that each job gets its fair share of the CPU. For (b) through (d) assume that only one job at a time runs, until it finishes. All jobs are completely CPU bound.§2.5 MINIX中進程的實現(xiàn)(IMPLEMENTATION OF PROCESSES)，11學時了解源代碼的組織和頭文件(1學時)；掌握MINIX引導和系統(tǒng)初始化(1學時)，MI

21、NIX的中斷處理、進程間通信和調度(4學時)，硬件相關的內核支持(1學時)作業(yè)：1. During execution, MINIX maintains a variable proc_ptr that points to the process table entry for the current process. Why?2. MINIX does not buffer messages. Explain how this design decision causes problems with clock and keyboard interrupts.3. When a messag

22、e is sent to a sleeping process in MINIX, the procedure ready is called to put that process on the proper scheduling queue. This procedure starts out by disabling interrupts. Explain.4. The MINIX procedure mini_rec contains a loop. Explain what it is for.5. MINIX essentially uses the scheduling meth

23、od in Fig. 2-43, with different priorities for classes. The lowest class (user processes) has round-robin scheduling, but the tasks and servers always are allowed to run until they block. Is it possible for processes in the lowest class to starve? Why (or why not)?6. Add code to the MINIX kernel to

24、keep track of the number of messages sent from process (or task) i to process (or task) j. Print this matrix when the F4 key is hit.7. Modify the MINIX scheduler to keep track of how much CPU time each user process has had recently. When no task or server wants to run, pick the user process that has

25、 had the smallest share of the CPU.8. Modify the hwint_master and hwint_slave macros in mpx386.s so the operations now performed by the save function are performed inline. What is the cost in code size? Can you measure an increase in performance?第三章 輸入/輸出(INPUT/OUTPUT) (理論16學時，實驗2學時)§3.1 I/O硬件原

26、理(PRINCIPLES OF I/O HARDWARE)，1學時了解I/O設備、設備控制器以及DMA等概念作業(yè)：1. What is memory-mapped I/O? Why is it sometimes used?2. Explain what DMA is and why it is used.3. Although DMA does not use the CPU, the maximum transfer rate is still limited. Consider reading a block from the disk. Name three factors that

27、might ultimately limit the rate of transfer.§3.2 I/O軟件原理(PRINCIPLES OF I/O SOFTWARE)，1學時了解I/O軟件的目標；掌握中斷處理程序、設備驅動程序、設備無關I/O件以及用戶空間I/O軟件的概念、原理以及它們之間的層次調用關系作業(yè)：1. Each device driver has two different interfaces with the operating system. One interface is a set of function calls that the operating s

28、ystem makes on the driver. The other is a set of calls that the driver makes on the operating system. Name one likely call in each interface.2. Why do operating system designers attempt to provide device-independent I/O wherever it is possible?3. In which of the four I/O software layers is each of t

29、he following done?(a) Computing the track, sector, and head for a disk read.(b) Maintaining a cache of recently used blocks.(c) Writing commands to the device registers.(d) Checking to see if the user is permitted to use the device.(e) Converting binary integers to ASCII for printing.4. Why are outp

30、ut files for the printer normally spooled on disk before being printed?§3.3 死鎖(DEADLOCKS)，1學時一般了解死鎖的概念和原理；了解死鎖檢測、預防和避免的算法§3.4 MINIX I/O系統(tǒng)概述(OVERVIEW OF I/O IN MINIX)，2學時掌握MINIX中斷處理程序、設備驅動程序、設備無關I/O軟件以及用戶空間I/O軟件的實現(xiàn)。作業(yè)：1. Why are RS232 terminals interrupt driven, but memory-mapped terminals

31、not interrupt driven?2. Why do operating systems provide escape characters, such as CTRL-V in MINIX?3. After receiving a CTRL-C (SIGINT) character, the MINIX driver discards all output currently queued for that terminal. Why?§3.5 MINIX塊設備(BLOCK DEVICES IN MINIX)，2學時掌握MINIX塊設備驅動程序的軟件結構作業(yè)：Describ

32、e the general principle of MINIX block device drivers.§3.6 RAM盤驅動(RAM DISKS)，1學時理解MINIX RAM盤驅動程序的結構及工作原理§3.7 磁盤驅動(DISKS)，2學時了解磁盤硬件和軟件；掌握硬盤驅動程序的工作原理作業(yè)：Modify the MINIX floppy disk driver to do track-at-a-time caching.§3.8 時鐘(CLOCKS)，2學時了解時鐘硬件和軟件；掌握時鐘驅動程序的工作原理作業(yè)：1. Modify MINIX to displ

33、ay current time every minute on the upper right corner of the screen.2. The clock interrupt handler on a certain computer requires 2 msec (including process switching overhead) per clock tick. The clock runs at 60 Hz. What fraction of the CPU is devoted to the clock?§3.9 終端驅動(TERMINALS)，4學時掌握驅動

34、程序的結構；理解鍵盤驅動程序；了解顯示器驅動程序作業(yè)：1. Write a graphics driver for the IBM color display, or some other suitable bitmap display. The driver should accept commands to set and clear individual pixels, move rectangles around the screen, and any other features you think are interesting. User programs interface t

35、o the driver by opening /dev/graphics and writing commands to it.2. Modify the terminal driver so that in addition to a having a special key to erase the previous character, there is a key to erase the previous word.第四章 存儲器管理(MEMORY MANAGEMENT) (理論12學時，實驗2學時)§4.1 分區(qū)(PARTITION MANAGEMENT ALGORIT

36、HM)，2學時理解位示圖、鏈表等數(shù)據(jù)結構；掌握BF, WF, FF等分區(qū)分配算法；掌握虛地址、實地址、地址變換、重定位等概念與技術。作業(yè)：1. A computer has 1 GB of RAM allocated in units of 64 KB. How many KB are needed if a bitmap is used to keep track of free memory?2. What is the difference between a physical address and a virtual address?3. Using the page mapping

37、 of Fig. 4-8, give the physical address corresponding to each of the following virtual addresses：(a) 20 (b) 4100 (c) 8300§4.2 分段(SEGMENTATION)，2學時理解保護模式下分段系統(tǒng)的硬件支持；掌握段表等重要的數(shù)據(jù)結構；掌握段的共享與保護機制。作業(yè)：1. Describe the principle of segmentation.2. What mechanisms does Pentium use to protect one process acc

38、essed from another? Describe the corresponding hardware and tables.3. What mechanisms does Pentium use to protect kernel data accessed from common process? Describe the corresponding hardware and tables.§4.3 分頁系統(tǒng)(PAGING SYSTEMS)，2學時掌握分頁系統(tǒng)中頁表結構、TLB、MMC及缺頁中斷等概念；掌握分頁系統(tǒng)的地址變換過程；了解工作集、抖動等概念；掌握LRU和FIF

39、O等頁面置換算法；了解分頁與分段的對比；了解段頁式存儲管理方案。作業(yè)：1. Explain the difference between internal fragmentation and external fragmentation. Which one occurs in paging systems? Which one occurs in systems using pure segmentation?2. When segmentation and paging are both being used, as in the Pentium, first the segment de

40、scriptor must be looked up, then the page descriptor. Does the TLB also work this way, with two levels of lookup?§4.4 MINIX存儲器管理(MEMORY MANAGEMENT IN MINIX)，6學時理解存儲管理系統(tǒng)的頭文件和數(shù)據(jù)結構(1學時)；掌握FORK、EXIT、WAIT、EXEC系統(tǒng)調用的實現(xiàn)(2學時)；掌握信號處理過程(3學時)。作業(yè)：1. It was pointed out that on an exec call, by testing for an

41、 adequate hole before releasing the current process' memory, a suboptimal implementation is achieved. Reprogram this algorithm to do better.2. In Sec. 4.8.4, it was pointed out that it would be better to search for holes for the text and data segments separately. Implement this improvement.3. Re

42、design adjust to avoid the problem of signaled processes being killed unnecessarily because of a too-strict test for stack space.4. To tell the current memory allocation of a MINIX process you can use the command： chmem +0 a.out, but this has the annoying side effect of rewriting the file, and thus

43、changing its date and time information. Modify chmem to make a new command showmem, which simply displays the current memory allocation of its argument.第五章 文件系統(tǒng)(FILE SYSTEMS) (理論8學時，實驗2學時)§5.1 文件及目錄(FILES AND DIRECTORIES),1學時了解文件、文件系統(tǒng)、目錄、路徑、絕對路徑、相對路徑、文件屬性等概念。作業(yè)：1. NTFS uses Unicode for naming f

44、iles. Unicode supports 16-bit characters. Give an advantage of Unicode file naming over ASCII file naming.2. Some files begin with a magic number. Of what use is this?3. Fig. 5-4 lists some file attributes. Not listed in this table is parity. Would that be a useful file attribute? If so, how might i

45、t be used?4. Give 5 different path names for the file /etc/passwd. (Hint： think about the directory entries "." and ".".)§5.2 文件系統(tǒng)實現(xiàn)(FILE SYSTEM IMPLEMENTATION),1學時理解連續(xù)分配、鏈接分配、文件分配表等文件存儲方法；掌握基于索引節(jié)點的文件存儲方式；掌握基于索引節(jié)點的目錄結構和路徑搜索方法；掌握UNIX磁盤空閑空間管理算法。作業(yè)：1. What is the difference bet

46、ween a hard link and a symbolic link? Give an advantage of each one.2. When a file is removed, its blocks are generally put back on the free list, but they are not erased. Do you think it would be a good idea to have the operating system erase each block before releasing it? Consider both security a

47、nd performance factors in your answer, and explain the effect of each.3. Three different protection mechanisms that we have discussed are capabilities, access control lists, and the UNIX rwx bits. For each of the following protection problems, tell which of these mechanisms can be used.(a) Ken wants

48、 his files readable by everyone except his office mate.(b) Mitch and Steve want to share some secret files.(c) Linda wants some of her files to be public.For UNIX, assume that groups are categories such as faculty, students, secretaries, etc.§5.3 MINIX文件系統(tǒng)(MINIX FILE SYSTEM),4學時掌握MINIX文件系統(tǒng)布局、位圖

49、、i-節(jié)點、高速緩存、文件描述符、文件鎖等的實現(xiàn)原理；了解文件系統(tǒng)調用的實現(xiàn)細節(jié)。1. The size of the filp table is currently defined as a constant, NR_FILPS, in fs/const.h. In order to accommodate more users on a networked system you want to increase NR_PROCS in include/minix/config.h. How should NR_FILPS be defined as a function of NR_PRO

50、CS?2. Suppose that a technological breakthrough occurs, and that nonvolatile RAM, which retains its contents reliably following a power failure, becomes available with no price or performance disadvantage over conventional RAM. What aspects of file system design would be affected by this development

51、?3. Symbolic links are files that point to other files or directories indirectly. Unlike ordinary links such as those currently implemented in MINIX, a symbolic link has its own i-node, which points to a data block. The data block contains the path to the file being linked to, and the i-node makes i

52、t possible for the link to have different ownership and permissions from the file linked to. A symbolic link and the file or directory to which it points can be located on different devices. Symbolic links are not part of MINIX. Implement symbolic links for MINIX.§5.4 MINIX文件系統(tǒng)實現(xiàn)(IMPLEMENTATION

53、),2學時掌握MINIX文件系統(tǒng)的實現(xiàn)過程。作業(yè)：1. Although the current limit to a MINIX file size is determined by the 32-file pointer, in the future, with 64-bit file pointers, files larger than 232 1 bytes may be allowed, in which case triple indirect blocks may be needed. Modify FS to add triple indirect blocks.2. Sho

54、w if setting the (now-unused) ROBUST flag might make the file system more or less robust in the face of a crash. Whether this is the case in the current version of MINIX has not been researched, so it may be either way. Take a good look at what happens when a modified block is evicted from the cache

55、. Take into account that a modified data block may be accompanied by a modified i-node and bitmap.3. Design a mechanism to add support for a "foreign" file system, so that one could, for instance, mount an MS-DOS file system on a directory in the MINIX file system.4. Write a pair of programs, in C or as shell scripts, to send and receive a message by a covert channel on a MINIX system. Hin