Operating System Exam (For Grade 2000)Class Name Student ID一、For each of the following statements, Choosing T rue or False （24 marks）1. Binary semaphores are those that are used by no more than two threads.2. The Banker's algorithm is a way of preventing deadlock .3. A multi-level indexed file permits faster random access than a contiguously allocated file.4. An atomic operation is a machine instruction or a sequence of instructions that must be executed to completion without interruption.5. Deadlock is a situation in which two or more processes (or threads) are waiting for an event that will occur in the future.6. Starvation is a situation in which a process is denied access to a resource because of the competitive activity of other, possibly unrelated, processes.7. While a process is blocked on a semaphore's queue, it is engaged in busy waiting.8. Mutual exclusion can be enforced with a general semaphore whose initial value is greater than 1.9. External fragmentation can be prevented (almost completely) by frequent use of compaction, but the cost would be too high for most systems.10. A page frame is a portion of main memory.11. The working set of a process can be changed in response to actions by other processes.12. Thrashing will never be a problem if the system has 1 GB of real memory.13. A printer is an example of a logical resource.14. Versions of OS/360 are still widely used today.15. When an executing process is stopped by the scheduler, it is said to be blocked.16.Interrupts are used to achieve a typical timesharing OS.1.二进制信号量是指那些不能超过两个线程使用。
2.银行家算法是防止死锁的方法。
3.多层次的索引的文件允许快速比连续分配的文件的随机访问。
4.一个原子操作是一个机器指令或必须完成而不会中断执行的指令序列。
5.死锁是其中两个或多个进程（或线程）等将来会发生的事件的情况。
6.饥饿是在其中一个过程被拒绝对资源的访问由于其他，可能不相关的过程的竞争活动的情况。
7.虽然过程被阻止的信号量的队列，它正在忙着等待中。
8 与一般的信号量，其初始的值大于1，可以强制执行.相互排斥。
9.外部碎片可以（几乎全部）因频繁使用的压缩，但成本会太高了，大多数系统。
10.页面框架是主内存的一部分。
11.一个进程的工作集可以被其他进程更改响应操作。
12 如果系统具有1 GB 的实际内存.大个子决不会有问题。
13.打印机是逻辑资源的示例。
14.版本的OS/360 今天仍在被广泛使用。
15.当调度程序停止时正在执行的进程，据说被阻止。
16.中断用于实现典型的分时操作系统。
二、Multiple Choice Questions (30 marks)For each of the following questions, There is only one correct answer.1. What is the purpose of system calls?a) System calls allow user-level processes to gain resources from the operating system.b) System calls are the standard interface between a user process and a kernel process.c) System calls allow user-level processes to request services of the operating system.d) There is no real purpose to system calls.2. Threads belonging to the same process share thea) stack b) data sectionc) register set d) thread ID3. In Many-to-One thread m odel, What would happen if a thread in a multithreaded process makes a blocking system call ?a) the other threads of the process would continue to runb) the entire process would get blockedc) the blocking thread will get killedd) the blocking thread will never get to run again4. Which of the following Operating systems uses preemptive scheduling?a) Mac OS 8 b) Windows 3.xc) Windows 2000 d) DOS 6.05. A measure of the number of processes completed per time unit is calleda) throughput b) waiting timec) response time d) CPU utilization6. One of the problems with priority scheduling isa) aging b) starvationc) process death d) average waiting time7. Consider the following reference stringsI :{0, 2, 4, 1, 1, 4, 5, 7} ; II :{2, 3, 2, 5, 6, 3, 2, 6}If the FIFO page replacement algorithm with 3 frames is applied,which of the two reference strings will result in fewer page faults?a) reference string I b) reference string IIc) both will have the same number of faults d) c an’t determine from the given data.8.In a time-sharing system, which of the following is the best criterion for CPU scheduling.a) Minimize CPU utilization b) Maximize CPU utilizationc) Maximize system throughput d) Minimize response time.9.The initial value of semaphore S is 2. if the value is -1 at present, how many processes are blocked on this semaphore .a) 1 b) 2 c) 3 d) 410. A system is in a deadlock, if its resource allocation grapha) contains a cycleb) doesn’t contain a cyclec) contains a cycle and there is just one instance of every resourced) has at least one outgoing edge from any one of the process nodes11. Preemption of resources can be enforced to prevent occurrence of deadlocks, but this can’t be applied to all the resource types, as preemption might leave the resource in an undetermined state. Which of the following resources can’t hence be preempted?a) CPU registers b) memory spacec) tape drive d) all of the above12. In the page replacement scheme a reference string isa) the number of frames allocated to a process b) a string of memory referencesc) a string of I/O references d) the times spent on each page-fault service13. Which disk space allocation method supports direct access without external fragmentation?a) linear b) contiguousc) linked d) indexed14. A system is said to be ___________ if it can continue to function even when a node or nodes in the system fail.a) networked b) distributedc) real time d) fault-tolerant15. Considering a system, which uses virtual memory. At what point can address binding be done?a) compile time b) load timec) execution time d) can be any of the above16. Which of the following is NOT associated with segments?a) two dimensional view of memory b) fixed sizec) easy sharing of data or code d) external fragmentation17. Pages can be shared between processes having common reentrant code. Here reentrant code meansa) self-modifying codeb) code which keeps going in and out of memoryc) non-self-modifying coded) code containing shared data variables18. The time to position the head on the disk is thea) seek time. b) access time.c) transmission time d) rotational latency19. _____________ presents a uniform device-access interface to the I/O subsystem, much as system calls provide a standard interface between the application and the operating system.a) Kernel b) A set of device driversc) Bus d) Operating system20. What is the name of the table containing information about all open files?a) file allocation table b) open-file tablec) file table d) file access table三、Consider the following set of processes: (10marks)Process Burst-Time PriorityP1 15 4P2 3 8P3 7 5P4 5 2P5 1 6P6 2 6The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, P6, all at time e FCFS, SJF, Round Robin (quantum is 2), Priority(low numbers have high priority). For each of the algorithms:1 Draw a Gantt chart2. What is the average waiting time for each of the scheduling algorithms？3.What is the average turnaround time for each of the scheduling algorithms？四、Consider a computer system with the following hardware characteristics. (12marks)Main memory size = 16 MbyteMain memory access time =100 nSA verage disk transfer speed = 1 Mbyte/secA verage disk seek plus latency time = 20 mSSmallest addressable unit = 4 bytes (i.e. 1 word)1.Consider an operating system A, which is using contiguous memory allocation scheme. Assuming the entire process, P1 (3 Mbyte), is currently in memory,(1) At time t1, P1 is to be swapped out of memory, what is the time required to roll out P1 to the disk?(2) At time t2, shortly after t1, a new process, P5, of size 4 Mbyte, arrived. Given the snapshot of the memory allocation at time t1, shown in figure 1. Can P5 be rolled in?5M7M11M15M16MFigure 1. Process Partition Map2. Consider again another operating system B, which is using a basic paging system (without using demand paging) with a logical address space of 4,096Kbyte and page size of 256Kbyte (or 65536 words, noting that the smallest addressable unit is a word).(1) How many frames are there in the system?(2) Show the format of the logical address (i.e. How many bits for page number? How many bits for page offset etc.).(3) If a translation look-aside buffer (associative register) with an average access time of 20nS is available/implemented in the hardware, assuming a hit ration of 90%, what is the effective memory access time now?(4) Shortly after t1, where all pages belonging to P1have swapped out, a new process, P5, of size 4 Mbyte, arrived. Again, referring to the snapshot of the memory allocation at time t1, shown in figure 1. Can P5 be rolled in?五、There are three cooperative processes P1, P2, and P3. They read data , denoted as a、b and c,from the same input device，as shown in figure below. The input device is an exclusive access device.The first datum(a) must be read by process P1, the second datum(b) is read by process P2, and the third datum(c) by process P3. These three processes perform the following calculations:P1: x = a + bP2: y = a * bP3: z = y + c - aP1, which is linked to the printer, should print the results of x,y, and z. Write the pseudo code for the three processes, using semaphores to synchronize their activities. (12marks)六、Consider a file system，there is a file of size 20MB . For each of the five allocation strategies: contiguous allocation, linked allocation, index-linked allocation(linked scheme) ,two-level indexed allocation and combined scheme allocation(linux ) . assume that the system block size is 4KB, the block pointer is 32 bits .answer these questions:1．What is maximum file size supported by each of the allocation strategies ?2．Assume File Control Block is already in main memory. Calculate how many disk I/O operations are required to access the byte in position 16M+5.5K for each of the allocation strategies。