操作系统作业-20110421.doc

操作系统作业（2011-04-21）：1、 假定某采用页式存储管理的系统中，主存容量为1MB，被分成256块，块号为0，1，2，255。现有一个共4页（页号为0，1，2，3）的作业被依次装入到主存的第2，4，1，5块中。请回答： （1）主存地址应该用多少位来表示？（2）作业每一页的长度为多少字节？逻辑地址中的页内地址部分应占用多少位？ （3）画出页表并给出作业中每一页占用的主存块起始地址。 （4）若作业执行中要从第0页的第75单元和第3页的第548单元读信息，那么，实际应从主存的哪两个单元读信息？请把应访问的主存绝对地址用十六进制数表示。分析由于主存容量为 1M，而 1M等于2的20次方，因而主存地址应用20位来表示。1M的主存空间被分成256块，因而每一块的长度为2的20次方2的8次方2的12次方4096（字节）。在页式存储管理的系统中，作业信息分页的大小应该与主存分块的大小一致，故作业每一页的长度应为4096个字节。于是，逻辑地址中的页内地址部分应占12位。因为主存块的大小为4096个字节（4K字节），块的编号从0开始，主存的绝对地址也是从0开始的，故每个主存块的起始地址为： 块长*块号=4K*块号现作业被分成四页（页号为0，1，2，3）且分别装入到第2，4，1，5块中。那么，这四页信息所在主存块起始地址应依次为：8K，16K，4K，20K。作业执行时应把逻辑地址转换成绝对地址，地址转换的一般公式为： 绝对地址=块号*块长+页内地址利用二进制乘法的特性，只要把根据页号从页表中查得的块号作为高地址部分，把逻辑地址中的页内地址作为低地址部分，就能得到对应的绝对地址。根据本题的假设，主存地址共20位，页内地址占用了12位，因而，高地址部分占8位，低地址部分占12位。若作业执行中要从第0页第75单元读信息，则实际应从主存第2块的第兀单元去读信息。于是，高地址部分为块号2，用8位二进制码表示为：00000010；低地址部分为单元号（页内地址）75，用12位二进制码表示为000001001011；形成的20位绝对地址为：000000100000010010if。同样地，当要从第3页的第548单元读信息时，实际应从主存第5块的第548单元去读信息。于是，高地址部分应为块号5，低地址部分应为单元号548，用二进制码表示的20位绝对地址就应该为：00000101001000100100。题中要求把绝对地址用二进制编码的十六进制数来表示，即把每四位二进制码作为一个十六进制的数，其对应关系为： 二进制编码 十六进制编码 0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7 1000 8 1001 9 1010 A 1011 B 1100 C 1101 D 1110 E 1111 F因而，第0页第75单元的绝对地址可表示为：0204B第3页第548单元的绝对地址可表示为：05224题解（1）主存地址应该用20位来表示。（2）作业每一页的长度应为2的12次方=4096个字节，逻辑地址中的页内地址部分应占用12位。（3）作业中每一页占用主存块的起始地址为： 页号 起始地址 0 8K 1 16K 2 4K 3 20K（4）若作业执行中要从第0页的第75单元读信息，则实际应从主存的第2块第75单元读，应访问的主存绝对地址用二进制编码的十六进制数表示为对204B。若要从第3页的第548单元读信息，则实际应从主存的第5块第548单元读，应访问的主存绝对地址用二进制编码的十六进制数表示为：05224。2、 兄弟俩共用一个账号，他们都可以用该账号到任何一家联网的银行自动存款或取款。假定银行的服务系统由“存款”和“取款”两个并发进程组成，且规定每次的存款额和取款额总是为100元。若进程结构如下： begin amount：integer； amount：0； cobegin Process SAVE m1： integer； begin m1：amount； m1：m1+100； amount：m1 end； Process TAKE m2：integer； begin m2：amount； m2：m2-100； amount：m2 end； coend； end；请回答下列问题：（1）请估计该系统工作时会出现怎样的错误？为什么？（2）若哥哥先存了两次钱，但在第三次存钱时弟弟却正在取钱，则该账号上可能出现的余额为多少？正确的余额应该为多少？（3）为保证系统的安全，若用PV操作来管理，应怎样定义信号量及其初值？解释信号量的作用。（4）在程序的适当位置加上P操作和V操作，使其能正确工作。分析由于“存款”和“取款”两个并发进程使用了共享变量amount，在进程中没有对共享变量的使用加以限制，因而当两个进程交叉访问共享变量时可能会出现与时间有关的错误。因amount的初值为“0”，故当哥哥先存了两次钱后，amount的值应该为200（每次存人 100元）。之后，哥哥和弟弟各自调用SAVE和TAKE进行存款和取款，使两个进程同时执行。它们并发执行时可能有如下两种情况：（1）进程在临界区执行没有被打断。此时若哥哥先执行了 m1:=amount；m1:= m1100；amount:=m1；则 amount的值为 300。然后，由弟弟执行 m2:= amount； m2:=m2-100；amount:= m2；则弟弟从 300元中取走了 100元使 amount的值保持为 200。如果弟弟先执行，则弟弟将从已有的200元存款中取出 100元使amount的值成为 100。然后，哥哥再执行存人 100元的工作而使amount的值仍为200。可见，无论是哥哥先执行存款还是弟弟先执行取款，只要各自在临界区的工作没有间断，则均使amount保持正确值。（2）两个进程在临界区交替执行。此时可能哥哥先执行了 m1:=amount，但还没有执行后继操作时弟弟调用的 TAKE进程占用处理器执行了 m2:=amount，那么，m1和 m2都取到了相同的值 200。同样地，若两个进程先后执行了 m2:= amount和 m1:= amount，则 m1和 m2也都取到相同的值200。随后，两个进程并发执行时将使m1=300，m2=100。如果SAVE进程先执行amount:= m1，TAKE进程后执行 amount:= m2，则 amount的终值为 100。如果 TAKE进程先执行 amount:= m2，SAVE进程后执行 amount:= m1，则 amount的终值为 300。可见，进程并发执行时该账号上可能出现的余额为100元，200元，300元，正确的余额数应该为200元。之所以会出现错误是由于没有限制进程互斥地进入相关临界区执行，为保证系统的安全，可用 PV操作实现互斥。用 PV操作管理时只需定义一个互斥信号量，其初值为“ 1”，用以限制每次只有一个进程可以进入临界区执行。题解（1）系统工作时会出现与时间有关的错误，这是因为并发进程中没有对共享变量amount的使用加以限制，进程交叉访问amount时就会出错。（2）账号上可能出现的余额为100元或200元或300元，正确的余额应该为200元。（3）用PV操作管理时可定义一个信号量S,S的初值为1，信号量S用于限制进程互斥地进入相关临界区执行。（4）使用PV操作管理后能保证正确并发执行的进程结构如下：begin amount:integer; s:semaphore; amount:=0; s:=1;cobegin Process SAVE m1:integer; begin P(S); m1:=amount; m1:=m1+100; amount:=m1; V(S) end; Process TAKE m2:integer; begin P(S); m2:=amount; m2:=m2-100; amount:=m2; V(S) end; coend: end;3、 有一仓库，可存放A和B两种产品，每次入库时只能存入A或B一种产品，每次出库时只能取出A或B一种产品。现要求：（1） -30A产品数量-B产品数量40 （2） A产品数量+B产品数量200 试用P、V操作描述产品的入库过程和出库过程。main()Semaphore empty=199;/A+B200Semaphore full=0;Semaphore mutex=1;Semaphore AB=39;/A-B40Semaphore BA=29;/B-A30CobeginInLib();OutLib();Coend入库过程InLib() 出库过程OutLib()while(有产品入库)while(有产品须出库)if(产品为A)if(产品为A)P(empty);P(