湖南大学操作系统作业-(5)

操作系统第五次作业第八章8.1Explainthedifferencebetweeninternalandexternalfragmentation.简述内部碎片和外部碎片的区别答：内部碎片存在于块的内部，如内存块大小为512k，而某逻辑内存要求一个200k大小的块，此时操作系统会分配给它一个大小为512k的块（由于块是内存分配的最小单元），所以会造成了312k大小的内存碎片，这部分碎片即使是空的也无法使用，称作内部碎片。减少内部碎片可以通过减小块的大小来解决。外部碎片是指在连续内存分配的进程装入和移出内存的过程中，空闲的内存空间被分成了较多小片段，这些小片段不连续，所以无法被连续分配，这样会造成即使碎片大小之和大于新进程所需内存，但是也无法给新进程分配的情况，这就是外部碎片。外部碎片可以通过紧缩来解决。8.3Givenfivememorypartitionsof100KB,500KB,200KB,300KB,and600KB(inorder),howwouldeachofthefirst-fit,best-fit,andworst-fitalgorithmsplaceprocessesof212KB,417KB,112KB,and426KB(inorder)?Whichalgorithmmakesthemostefficientuseofmemory?给出100kb，500kB，200kB，300kB，600kB大小的内存空间（按顺序），对于首次适应，最佳适应和最差适应算法，要按顺序放置212kB，417kB，112kB和426kB大小的进程会是怎样安排的？哪个算法的内存利用率最高？答：首次适应是每次从头开始找，直到找到第一个比当前要放置的内存大小要大的内存空间时，放置该内存。最佳适应是每次遍历内存空间一次，找大于当前要放置的内存块大小要大的中间的最小者，放置该内存。最差适应则相反，是取大于当前内存大小中的最大者。下面给出三种存储分配方式的最终分配结果：首次适应：对于212kB的进程，选择第一个大于它大小的内存空间，为500kB，并分配给它相应大小的空间，该部分剩余大小500-212=288KB对于417kB的进程，选择第一个大于它的大小的内存空间，为600kB，分配给它相应大小的空间，该部分剩余大小为600-417=183KB对于112kB的进程，选择第一个大于它大小的内存空间，为288kB，分配给它相应大小的空间，该部分剩余大小288-112=176KB对于426kB的进程，找不到比他大的内存空间，无法分配，只能等待其他进程释放空间才能为它分配空间。内存利用率为（212+417+112）/（100+500+200+300+600）*100%=43.6%最佳适应：对于212kB的进程，选择大于它大小的内存空间中的最小者，为300kB，并分配给它相应大小的空间，该部分剩余大小300-212=88KB对于417kB的进程，选择大于它大小的内存空间中的最小者，为500kB，分配给它相应大小的空间，该部分剩余大小为500-418=83kB对于112kB的进程，选择大于它大小的内存空间中的最小者，为200kB，分配给它相应大小的空间，该部分剩余大小200-112=88kB对于426kB的进程，选择大于它大小的内存空间中的最小者，为600kB，分配相应大小的空间，该部分生育大小为600-426=174kB内存利用率为（212+417+112+426）/（100+500+200+300+600）*100%=68.6%最差适应：对于212kB的进程，选择大于它大小的内存空间中的最大者，为600kB，并分配给它相应大小的空间，该部分剩余大小600-212=388kB对于417kB的进程，选择大于它大小的内存空间中的最大者，为500kB，分配给它相应大小的空间，该部分剩余大小为500-417=83kB对于112kB的进程，选择大于它大小的内存空间中的最大者，为388kB，分配给它相应大小的空间，该部分剩余大小388-112=276kB对于426kB的进程，找不到比他大的内存空间，无法分配，只能等待其他进程释放空间才能为它分配空间。内存利用率为（212+417+112）/（100+500+200+300+600）*100%=43.6%综上所述，本例中最佳适应的内存利用率最高，为68.6%8.9Considerapagingsystemwiththepagetablestoredinmemory.a.Ifamemoryreferencetakes200nanoseconds,howlongdoesapagedmemoryreferencetake?b.Ifweaddassociativeregisters,and75percentofallpage-tablereferencesarefoundintheassociativeregisters,whatistheeffectivememoryreferencetime?(Assumethatfindingapage-tableentryintheassociativeregisterstakeszerotime,iftheentryisthere.)考虑一个分页系统将页表存在内存中A如果一个内存访问占用200ns，那么一个页面内存查询占用多少时间？B如果添加相关寄存器，且所有页表中的75%的访问可以在寄存器中找到，那么有效内存访问时间为多少？（假设寻找页表条目不花时间）答：A首先访问内存中的页表项，耗时200ns，然后在页表项中查询对应的物理地址（0ns），然后根据对应物理地址去访问内存，耗时200ns，一共耗时为400ns。B（书上翻译associativeregisters是TLB，感觉不是很恰当，但是只能当作TLB来理解）首先去查找TLB表，如果命中（75%的概率），就直接得到了物理地址，此时可以直接访问物理地址，耗时200ns。如果TLB不命中（25%的概率），此时要按照A中的步骤先访问页表再访问主存，耗时400ns。所以耗时期望E（t）=200*0.75+400*0.25=250ns8.12Considerthefollowingsegmenttable:SegmentBaseLength02196001230014290100313275804195296Whatarethephysicaladdressesforthefollowinglogicaladdresses?a.0,430b.1,10c.2,500d.3,400e.4,112考虑下面的段表，要求对应逻辑地址的物理地址是多少答：A0，430先查询段号为0的基地址为219，然后判断是否在段内，由于430600，所以在段内，对应物理地址为219+430=649B1，10，首先查找段号为1的基地址2300，然后判断是否在段内，由于1014,所以在段内，对应物理地址为2300+10=2310C2,500,首先查找段号为2的基地址90，然后判断是否在段内，由于500100，所以不在段内，访问非法D3，400，首先查找段号为3的基地址1327，然后判断是否在段内，由于400580,所以在段内，对应物理地址为1327+400=1727E4,112，首先查找段号为4的基地址1952，然后判断是否在段内，由于11296，所以不在段内，访问非法第九章9.4Acertaincomputerprovidesitsuserswithavirtual-memoryspaceof232bytes.Thecomputerhas218bytesofphysicalmemory.Thevirtualmemoryisimplementedbypaging,andthepagesizeis4096bytes.Auserprocessgeneratesthevirtualaddress11123456.Explainhowthesystemestablishesthecorrespondingphysicallocation.Distinguishbetweensoftwareandhardwareoperations.某电脑提供给虚拟存储一个2^32b大小的空间，电脑只有2^18b大小的物理存储，虚拟存储以分页存储，页面大小4096b，一个用户进程产生虚拟地址11123456，解释系统如果建立对应的物理地址，区分硬件和软件的操作。答：11123456化成二进制表示为00010001000100100011010001010110由于虚存有32位地址，页面大小为2^12b，所以页偏移就有12位，取虚拟地址的后12位为页偏移，这也是物理地址上的偏移，而虚拟地址剩余的20位则是页号，物理地址剩余的6位是物理页号在查询11123456时，操作系统先根据前20位00010001000100100011查询页表，查找到对应的物理页号，这是软件操作；然后找到物理页号后计算出对应的物理地址，这也属于软件操作。而在查询页表时，如果发生缺页，此时对页面的调度则是硬件操作。9.13Apage-replacementalgorithmshouldminimizethenumberofpagefaults.Wecandothisminimizationbydistributingheavilyusedpagesevenlyoverallofmemory,ratherthanhavingthemcompeteforasmallnumberofpageframes.Wecanassociatewitheachpageframeacounterofthenumberofpagesthatareassociatedwiththatframe.Then,toreplaceapage,wesearchforthepageframewiththesmallestcounter.页面调度算法应该最小化页面错误，我们可以通过分配常被使用的页面给其他内存来做最小化操作，而不是让他们竞争一小片内存。可以给每个页帧设置一个计数器来记录和他相关的页数，然后，为了调换页面，在所有页帧中选择计数值最小的那个。ADefineapage-replacementalgorithmusingthisbasicidea.Specificallyaddresstheproblemsof(1)whattheinitialvalueofthecountersis,(2)whencountersareincreased,(3)whencountersaredecreased,and(4)howthepagetobereplacedisselected.设计一个页面调换算法使用这个基础思想；特别要注意的问题是：1计数器的初值，2何时计数器增加，3何时计数器减少，4页面应该怎么被替换和选择b.Howmanypagefaultsoccurforyouralgorithmforthefollowingreferencestring,forfourpageframes?1,2,3,4,5,3,4,1,6,7,8,7,8,9,7,8,9,5,4,5,4,2.在你的算法用4个页帧里调度以下顺序的页面会出多少错？c.Whatistheminimumnumberofpagefaultsforanoptimalpage-replacementstrategyforthereferencestringinpartbwithfourpageframes?最优置换算法中用4个页帧调度上述顺序会出现多少个页面错误？答：A考虑这样一个页面调度算法，初始化各页帧counter值均为0，每个页帧每一次调入一个新的页时，counter+1，这个值在调入的页面不会再次出现时还原，即counter-1，每次有新的页面需要调入页帧时，先对所有页帧进行判断，选择当前counter值最小的页帧作为置换页，如果有多个相同counter值的页帧，则选取最先