例题

  • 格式:doc
  • 大小:147.50 KB
  • 文档页数:7

1 1. In a demand-paging system, the page size is 1KB, and there is a process Pi with the size of three pages. The page table for Pi is as follows: page number frame number valid-invalid-bit 0 2 v 1 — i 2 100 v

It takes 100ns to access memory and 20ns to search the TLB (translation look-aside buffers) respectively, and the average page-fault service time is 110ns (including the times for updating the TLB, updating the page table, and page replacement). It is assumed that (1) the TLB contains two page-table entries, and is initially empty; (2) for a logical address generated by the CPU, if its page number is not found in the TLB, a memory reference to the page table is made, and the page entry for this address is then loaded into the TLB; (3) if valid-invalid-bit=i, the page is not in memory, and a page fault occurs (4) there are only two frames allocated to Pi, i.e. frame 2 and frame 100 (5) OS takes the local replacement strategy and the LRU algorithm for page replacement

Given three logical addresses 2300, 1500, and 2500, if the CPU makes accesses to these addresses in order, (1) how long does it takes to access to the addresses 2300, 1500, and 2500 respectively? (2) what is the physical address for the logical address 1500 ?

Answers: (1) 页面大小为1KB,即210byte,因此逻辑地址中,页内偏移占低10位,page number占剩余高位。 逻辑地址2300、1500、2500对应的page number分别为2、1、2 (2) 逻辑地址2300访问过程和访问时间: 首先访问TLB,需要20ns;因TLB初始为空,继续访问page table,得到frame number,需要100ns;合成物理地址后再访问主存单元,并将page table中page number=2对应的entry调入TLB,需要100ns。 共计:20ns+100ns+100ns=220ns。 2

(3) 逻辑地址1500访问过程和访问时间: 首先访问TLB,需要20ns;TLB中无page table中page number=1对应的entry,继续访问page table,需要100ns;由于page table 中无该page number=1对应的entry,发生缺页中断,并进行页置换,耗时110ns;合成物理地址后再访问主存单元,并将page table中page number=1对应的entry调入TLB,需要100ns。 共计:20ns + 100ns + 110ns + 100ns = 330ns。

(4) 逻辑地址2500访问过程和访问时间: 首先访问TLB,需要20ns。因访问2300时已将page number=2对应的entry调入TLB,因此花费20ns便可从TLB中得到物理地址;合成物理地址后再访问主存单元,需要100ns。 共计:20ns+100ns =120ns。

(5) 访问1500时,page number=1,产生缺页中断。由于当前分配给Pi的2个frame已经放置了page0、page2,因此需要进行page replacement。 根据LRU算法,将淘汰page0,将page1放入frame2中, frame2首地址为2048。 因此,1500对应的物理地址为: 2048 + (1500 -1024)=2048 + 476 = 2524

2. In a computer system, the users submit to the system their computational tasks as jobs, and all these jobs are then stored as the standby jobs on the disk. The job scheduler (also known as long-term scheduler) selects the standby jobs on the disk, creates new processes in memory for them, and then starts executing these processes. Each job’s ID is the same as that of the process created for it, for example, Ji and Pi. When the number of concurrent processes in memory is lower than three, the job scheduler takes the FCFS algorithm to select a standby job on the disk to create a new process. Otherwise, the processes should wait in the disk. For the processes in memory, the process scheduler (also known as short-term scheduler) takes the non-preemptive priority-based algorithm to select a process and allocates the CPU to it. 3

It is assumed the system costs resulting from job and process scheduling are omitted. Consider the following set of Jobs J1, J2, J3 , J4 and J5. For 1≤ i ≤5, the arrival time

of each Ji , the length of the CPU burst time of each process Pi, and the priority number for each Ji/Pi are given as below, and a smaller priority number implies a higher priority. Job Arrival Time Burst Time Priority Number (minute) J1 14:00 40 4 J2 14:20 30.01 2 J3 14:30 50.01 3 J4 14:50 20.01 5 J5 15:05 10.01 5

(1) Illustrate the execution of each job/process by charts. (2) What is the turnaround time of each job? (3) What is the waiting time of each job? Note: The waiting time of a job includes the time it waits on the disk and that it waits in memory.

Answer: (1) 4

J1/ P1: 14:0014:40J1, P1

J2/ P2: 14:0014:40P2/J214:2015:10.01P2

J3/ P3: 14:0014:30P3/J315:10.01P316:00.02

J4/ P4: 14:0014:50P4/J4P416:00.0216:20.03

J5/ P5: 14:0015:05J5P516:20.0315:10.01P5/J516:30.04

注:图中Ji部分表示作业被调入内存,Pi表示进程被调度执行。 J1到达时,并发进程数<3,作业被直接调入内存,创建进程P1;P1被调度程序选中,开始执行。 J2到达时,并发进程数<3,作业被直接调入内存,创建进程P2;此时P1在执行,因此P2处于就绪等待状态。P1结束后,系统内有2个作业J1、J2对应的进程P1、P2,优先级高的进程P2开始执行。 J3到达时,并发进程数=2<3,作业被直接调入内存,创建进程P3,等待P2执行完毕。P2执行完毕后,系统内有2个作业J3、J4对应的进程P3、P4,优先级高的进程P3被调度程序选中,开始执行。 J4到达时,并发进程数=2<3,作业被直接调入内存,创建进程P4,等待P3执行完毕。P3执行完毕后,系统内有2个作业J4、J5对应的进程P4、P5,2者的优先级相同,按照FCFS原则,P4先执行。 J5到达时,并发进程数=3,必须等到P2结束后,系统内并发进程数<3,方能创建进程P5。等到P4执行结束后,P5开始执行。

(2)J1 :T1 = 40 (min) J2 :T2 = 20 + 30.01 = 50.01 (min) J3 :T3 = 40.01 + 50.01 = 90.02 (min)