Test 2

Operating Systems

Test 2, 4 April 2012

This test has ten questions; answer at least eight of them.

Up to the first 75 words appearing after a question are taken to be the answer to the question. Words following the 75th word are not part of the answer and will be ignored.

An operating system uses the memory-management unit to implement paging. What is the absolute minimum of information a page-table entry must maintain to support a correct paging implementation? Justify your answer. Do not be concerned with performance, just correctness. The page table may be inverted or not, as you choose.
A page-table entry may be in-use or not; the entry needs a bit to indicate which state it’s in. An in-use page-table entry needs the other half of the translation, either a page-frame number, or a virtual-address page number. The page table is shared among all running processes; each entry needs a process id to associate it with a particular virtual address space.
The answers, approximately verbatim, and in no particular order:
1. The minimum information a page table entry needs is the page frame and the virtual address as well as any modification to the address or pages.¹ With this info the page the data is in can be found² as well as an available physical address data on modification can aid in page replacement by keeping track of modification to decide which pages can be replaced for new pages.³
  
  1: How does the modification information help in translation?
  
  2: How are several virtual-address spaces distinguished?
  
  3: True, but is that necessary for correct paging, as opposed to efficient paging? And how does a MMU determine if a page-table entry contains valid information?
2. The absolute minimum pages a table must contain is one. Without one page in the table there is no table at all.⁴ Although not a lot of information can be stored in one page.⁵ So the performance is bad. If the one page is not the page that is needed, the operating system can eject it or load it from the disk, primary store, or somewhere else. One page is the minimum and a one-page […]⁶
  
  4: That’s true, but the question’s about the contents of a page-table entry, not the number of page-table entries in a page table.
  
  5: How is “information” being used here?
  
  6: … implementation will have many ejections and reloads.
3. We need page frame number and the place of their physical storage. This is needed because we need to treat the page and the frame number to point to the exact location of the page.⁷ This although is not the fastest way to array a page but if the correct way to find a page because we can treat it though ts location and frame number.⁸
  
  7: How does that work? What extra information is needed that the page-frame number doesn’t provide?
  
  8: How does the MMU know if page-table entries contain value information. How does the page table distinguish among several virtual-address spaces?
4. The absolute minimum information that a page table must maintain to support a correct paging implementation are⁹ the frame number, present-absent bit, and the page number.¹⁰ These are the main things needed in a page table.¹¹ Frame number so it¹² can tell you where in the page,¹³ page number to tell you what page¹⁴ and the present absent bit to tell you whether or not its still in the page.¹⁵ This is the least amount¹⁶ […]¹⁷
  
  9: That’s seventeen words that add nothing to the answer.
  
  10: Why are both the page number and the page-frame number both needed?
  
  11: Another ten words that add nothing.
  
  12: “It” refers to what?
  
  13: What? Where what in the page?
  
  14: What? Does this mean the page number indicates the page? Does the page table need to be involved with that?
  
  15: Whether or not what is still in the page?
  
  16: Is this enough information to distinguish between several virtual-address spaces?
  
  17: … of information needed for a page table to preform correctly; all other bits, cache bit, protection bits, pinned bits, and modified referenced bits are all extra information that is not needed but is useful.
5. You need page number, page frame number,¹⁸ page offset,¹⁹ disk block, disk sector.²⁰ The reason you need all of these is for the virtual page number,²¹ the offset on the page itself where what you want is looked at the frame that contains the page.²² Then you also want the physical disk lock and sector that your page is located or has been mapped to.²³
  
  18: Why does a minimal page-table entry need both a page number and a page-frame number?
  
  19: How does having the page offset help when translating the virtual address? Isn’t the translation all about pages?
  
  20: How does having disk-location information help when translating a virtual address?
  
  21: Doesn’t the virtual page number come directly from the virtual address? What information does the page-table entry provide that helps?
  
  22: Does the page offset need to be translated? Isn’t the page offset the same for the virtual and physical addresses?
  
  23: It seems clear that a failed address translation needs to know about disk-location information, but how does a successful translation make use of such information?
6. A page table entry must contain, at minimum, the virtual address of the process it references,²⁴ the physical address on primary store where the process is actually being run,²⁵ and an index value to reference said page table entry.²⁶ This is the absolute minimum of information because if we are only concerned with paging correctness then any information not pertaining to the location of the process in virtual store and the page frame associated with²⁷ […]²⁸
  
  24: What does this mean? Does each page-table entry contain the whole virtual-address space?
  
  25: The process could be running at a lot of physical addresses. How is that represented?
  
  26: An index value into what? Is the page-table entry referring to itself?
  
  27: How does the MMU know if a page-table entry contains valid information?
  
  28: … that added to in primary store is superfluous.
7. If the page table is a linear page table it is an array that has a single entry per page in virtual address. A page table must maintain the location of each page and where it is stored in virtual memory.²⁹ Each entry in the page table at a minimum must have a valid bit and a page number.³⁰ Each page needs to be mapped to a specific page frame.
  
  29: How do all these words answer the question?
  
  30: How does the page table keep track of several virtual-address spaces?
8. The minimum information that must be contained in a page-table entry to support correct paging are the page number, the page offset,³¹ and the base address.³² The page number acts as the index in the page table,³³ the offset designates the amount of address space required,³⁴ and the base address combines with the offset to define the physical address used by the memory management unit.³⁵
  
  31: How does the page offset assist in the virtual-address translation?
  
  32: What’s the base address?
  
  33: Does that make it part of a page-table entry?
  
  34: In total, or per page? And required for what?
  
  35: How is the base address different from the page number?
9. The absolute min. of info a page table entry must maintain to support a correct paging implementation is 1³⁶ the page frame corresponding to the specified virtual page and 2 a present/absent bit. This works because it gives us enough information to map virtual addresses into physical addresses. This can be implemented by getting the virtual address and putting it into two parts: page number and offset. The page number is used as an index³⁷ […]³⁸
  
  36: That’s ninteen words that add nothing to the answer.
  
  37: How does the MMU know if a page-table entry is valid?
  
  38: … into the page table which holds the number of the page frame that corresponds to the virtual address, then the present/absent bit is processed[?]. If the bit is 0 a trap on the OS is caused if the bit is 1 the page frame number found in the page table and is copied to the high-order bits of the output registers along with the offset bits. Together this forms a physical address which is put into the memory bus as the physical address.
10. the smallest amount of information an entry must maintain is equal to the smallest multiple of the disk block size.³⁹ it will be able to keep page overhead in context switching to a minimum to ensure a correct implementation, each entry must contain at least a page frame number and a present-absent bit. this will insure that the page frame can be looked up at any time and also show if it is present or⁴⁰ […]⁴¹
  
  39: isn’t 0 the smallest disk-block size multiple? assuming negative multiples don’t make sense.
  
  40: how would a page-table entry distinguish among several virtual-address spaces?
  
  41: … absent, making it easier for any buffer or frequent[?] operation[?] to have a reference to that entry.
11. At minimum a page table must maintain page frame numbers, modified-reference bit, cache bit,⁴² and pinned bit.⁴³ The page frame number in order to track the correct page in virtual memory. The reference bit to track the page is therefore to after it has been modified.⁴⁴ The cache bit tells where the page is mapped to,⁴⁵ and the pinned bit likes the page to address.⁴⁶
  
  42: What does the cache bit indicate?
  
  43: What does a pinned bit do during translation?
  
  44: How does modified-reference information help in translation?
  
  45: With one bit? How does it do that?
  
  46: What? Maybe that word should be “links”, but then what does it mean to link a page to address, and how is that done in one bit?
12. Virtual addresses are divided into units called pages. Physical memory are called page frames. The page number is used as index of the page table.⁴⁷ It must maintain[?]: — virtual address index of conceptual array⁴⁸ on 4 bit of 16 a bit for most.⁴⁹ — With 4kb pages, 12 bit offset is needed for a totally of 16 bit address, 4kb pages.
  
  47: Is that part of the page table, or of the page-table entry?
  
  48: Is this conceptual array part of a page-table entry? What does it represent?
  
  49: From where do these bits come? What do they represent?
13. The absolute minimum of information a page-table entry must maintain is determined by the software or hardware itself,⁵⁰ but must maintain the overhead of the page-table larger than the one the page is in⁵¹ (i.e., small contains an overhead for a large page table). This is so that the page table entry can properly store information.⁵²
  
  50: Determined how?
  
  51: Does this mean there’s more than one page table per virtual-address space?
  
  52: But what kind of information is being properly stored in a page-table entry?
14. Owning process identifier. Valid indicator. Page number. These are the minimum because this allows the MMU to translate addresses for a given process into the correct physical address. Owing process is required to prevent other processes from accessing other process’s memory. Valid indicator is needed to verify if the entry is actually valid. Page number is required to properly translate the virtual address into the correct physical address.
15. The absolute minimum information a page table entry must maintain to support a correct paging implementation is⁵³ the page numbers. If the page table entry does not have the page number than no page will [??].⁵⁴
  
  53: These are seventeen words that add nothing to the answer.
  
  54: How does the MMU know if page-table entries are valid? How does the page table distinguish among several virtual-address spaces?
16. A page table entry must maintain in its page frame number because you must know where the page is coming from.⁵⁵ Each entry in an inverted page table must consist of the virtual address of that page sorted in the real memory location. Info about the process that owns the page.⁵⁶ They also sometimes require an address-space identifier,⁵⁷ since it usually contains several address spaces mapping physical memory. Or it could be (process-id, page-number).⁵⁸
  
  55: From where can a page come? It’s important to know where a page goes, but why is it important to know from where a page came?
  
  56: What kind of information?
  
  57: What is an address-space identifier? And when is it necessary to have an address-space identifier?
  
  58: How does the MMU know if a page-table entry is valid?
17. The absolute minimum would be a 64-bit addresses⁵⁹ with a 16k page frames,⁶⁰ 2⁴⁸ 2³² mbyte main store 2¹⁶2¹⁶ kbyte page frames.⁶¹
  
  59: What happens then the virtual-address space is 32 bits?
  
  60: Why this size? Why not a size efficiently compatible with the disk-block size?
  
  61: Why?
18. In order to maintain the absolute minimum of info a page table entry must maintain depends in the size of the info. This can depend on the primary store of the page.⁶² The storage units also have virtual address the minimum would be N that is usually 2³² or 2⁶⁴ or 2^p-1⁶³ within the page frames. Virtual store has a large affect. The structure is 2^p units (10 ≤ p ≤ 12). Page # has […]⁶⁴
  
  62: How does this dependence manifest itself?
  
  63: What does N represent? What does p represent?
  
  64: … the rightmost bits in virtual addresses.
19. the minimum information the entry must maintain for correct paging implementation is the page number and the page offset.⁶⁵ within these two bits of info the os would be able to find each page by its virtual address⁶⁶ and assuming the pages are the same size as the page frame used, the page in the page frame.⁶⁷ this does not provide good performance, but make paging possible.
  
  65: what does the page offset add to paging?
  
  66: can’t the page number be derived directly from the virtual address? what does the page-table entry add?
  
  67: how does a page-table entry distinguish among several virtual-address spaces?
A colleague of yours is managing a file-block buffer using an LRU queue replacement algorithm. The buffer is performing well, except for metadata blocks. Suggest some changes your colleague could make to the replacement algorithm to better handle metadata blocks. A good answer to this question will identify the most likely problems with metadata-block handling, and suggest changes to fix those problems.
Adding second-chance to the LRU queue will prevent it from ejecting still active metadata blocks that make it to the head of the queue. Adding the clock variant with a fast second hand to sweep the queue for metadata blocks will write those back to disk more quickly, reducing the risk of file-system inconsistencies in case of failure.
The answers, approximately verbatim, and in no particular order:
1. The problem my colleague is having with metadata block handling has to do with the fact that metadata is not contained in the file and will be flagged as LRU.¹ The solution could be to link the metadata with its corresponding file² so that once the file is used, the metadata will share the same modification time to show it was not LRU.³
  
  1: What does it mean to be flagged as LRU?
  
  2: Isn’t that done already? Metadata with no links to the associated file seems worthless.
  
  3: But what does the LRU queue do with modification times?
2. Because file systems metadata incoherence can be fatal.⁴ It is important or good idea to write-back early and often or write-through always.⁵
  
  4: True, but the problem’s concerned with performance.
  
  5: Quite right, but how can that be done? Is it even possible to do with LRU? How?
3. Use buffer management by amortizing[?] of writes into 0 large writes to the disk. Write throughput buffering of the metadata will also help.⁶ Write block early and often to the disk.⁷ Write through buffering to the disk will also help.⁸
  
  6: Help with what?
  
  7: How should that be done?
  
  8: Is this the same as the previous sentence?
4. The LRU queue making a queue of pages⁹ ordered so the last file in at the tail, and the most easily accessed.¹⁰ It also has the first file¹¹ in at the head. With these files it also has the metadata, or the information about the files. In order to handle these metadata blocks the LRU queue must support the metadata and the file that comes in.¹² The metadata must be put in a secure [?] place […]¹³
  
  9: Or file blocks.
  
  10: Is it the last queued block that’s most easily accessed? And maybe “easily” should be “recently?”
  
  11: Or file block.
  
  12: The question seems to indicate that file buffering does handle both kinds of blocks.
  
  13: … from which the buffer is [??] or the metadata will take up too much space.
5. Some changes that can occur is to change the link blocks¹⁴ that are packed in the instances of the file metadata.f¹⁵ The metadata is not within the file so I would suggest to alter the algorithm to accept everything together.¹⁶ Another suggestion would be to make the file block buffer of the management not to eject all the blocks.¹⁷ However, this may cause more space and time for the overhead and possibly the metadata blocks.
  
  14: Should that be “block links?”
  
  15: Ok, but does LRU buffer management use the format of file blocks to determine how to handle the blocks?
  
  16: Isn’t the LRU algorithm currently handling everything together?
  
  17: Doesn’t the LRU algorithm do that already?
6. Metadata writes are synchronous,¹⁸ therefore a flag bit should be added to the LRU queue replacement algorithm to allow for opening a system call to request a synchronous write.¹⁹ This way when handling metadata blocks, the system can perform synchronously,²⁰ and when it is not the bit will not be set, allowing the currently implemented LRU queue replacement algorithm to function as it is currently implemented (asynchronously).
  
  18: Does this mean writes to metadata, such as to change the file size, or metadata-block I-O? Or both?
  
  19: Would that apply to the file data, or the file metadata? Or both?
  
  20: And what problem would that solve?
7. One thing that you can do is create a pointer to metadata from the block it corresponds to²¹ and if that block is ejected its metadata should also be ejected from the queue.²² The metadata will then leave with the block since if the block is still around it will almost always be accessed by the block.²³
  
  21: Isn’t there already such pointers in the metadata? That’s some of the information in metadata.
  
  22: So if a file’s block is ejected, the metadata associated with the directory holding the file should also be ejected too? How does that improve matters?
  
  23: Does this say a file block accesses its metadata? Is that true?
8. Use external[?] links to separate file data from the metadata.²⁴ This allows the buffer to handle the two types of data separately.²⁵ Since metadata blocks are usually implemented using tlvs (type length variables)²⁶ they do not grow the same as files since each new record²⁷ can be of any size. These also allows better disk utilization by allowing the two types of dcts[?] to be read/written independently. This is true because metadata can be added […]²⁸
  
  24: Isn’t that what happens currently?
  
  25: Doesn’t this happen anyway? A block contains either metadata or file data, but not both.
  
  26: What are type length variables?
  
  27: A record where? In the metadata?
  
  28: … to a file even when the file dcts[?] remains unchanged.
9. One way of dealing with the problem of metadata blocks is to implement a journaling file system.²⁹ This would resolve the issue of metadata coherence³⁰ and make better use of the writes that will inevitably occur. In addition, it will provide a checkpoint for system recovery in the event of a crash or flush.³¹ A priority but should also be added to mark metadata blocks as important data, not to be thrown out until its […]³²
  
  29: That seems rather complicated, particularly since LRU is mostly working well.
  
  30: Is coherence the problem, or is it performance?
  
  31: True, but not an issue in this problem.
  
  32: … associated file-blocks are out of the buffer as well.
10. Metadata blocks are block of data about other data. Metadata is commonly stored in i-nodes.³³ A problem with i-nodes is that they are fixed sizes,³⁴ and small i-nodes usually only contain mapping info for the first dozen or so blocks, which could also cause some problems being fixed size blocks can overflow larger then an i-nodes. This usually causes a new i-nodes to be made. To make an algorithm the programmer has to know how³⁵ […]³⁶
  
  33: Some of the metadata is stored in i-nodes; other metadata is stored elsewhere.
  
  34: Maybe, but is that a problem relevant here?
  
  35: Does this answer mention anything about fixing the LRU algorithm?
  
  36: … the i-nodes structure is used on the system he is writing the algorithm for. He needs to know the max size and length of the i-nodes and the max amount of mapping input-output stored for the metablocks.
11. Likely problem with metadata are sifting though it,³⁷ locating pertinent data for the LRU to use, and organizing the metadata[?].³⁸ Changes that can be made to the algorithm include limiting the data the algorithm looks for to the time the file was last modified, to store it in an array.³⁹ The program⁴⁰ compares it to the current data and time and removes the file with the biggest difference between time last modified and the present.⁴¹
  
  37: Does the buffer-management algorithm care about the block contents?
  
  38: But is organizing metadata something buffer management should worry about?
  
  39: Ok, and then what?
  
  40: Program? Perhaps this means the LRU algorithm?
  
  41: That doesn’t sound much like an LRU queue anymore.
12. LRU is an ok[?] implementation, but must also write-back often. To minimize write-backs, only write-back frequency said[?] files. However, [?] this is an expensive operation we should utilize amortization into a journal entry.⁴² The next data particularly to the files will also be certified here,⁴³ so when the journal is written back to the system, it will pass all the information.
  
  42: The problem’s interested in making LRU better for metadata, not replacing it with something else.
  
  43: What does it mean to certify data? And where is here?
13. metadata contains everything there is to know about the file other than its contents. lru only handles the oldest resident page, not the one that hasn’t been accessed the longest. a better way to implement this queue would be a second change fifo algorithm.⁴⁴ it would use the metadata to check access times as pages pass through the queue. having the second chance allows for multiple passes for a page. it may not be fast […]⁴⁵
  
  44: ok, that handles untimely write-backs. what about timely write-backs?
  
  45: … the first time through,k but it may be fast the second time. this will lead to less metadata blocks because it will be checking the metadata for times as well as file protection values.
14. the most likely problem with the metadata block handling is that metadata forces writes during write-back⁴⁶ and buffer coherence.⁴⁷ these writes are small and scattered, causing an expensive write to occur for little data. to fix this my colleague can amortize writes into a journal or log entry.⁴⁸ this would spread the cost of the write over all the minor writes caused by the metadata and minimize disk arm movement.
  
  46: but isn’t forcing writes eventually the point of write-backs?
  
  47: is buffer coherence a performance problem?
  
  48: isn’t there anything to be done with lru?
15. Blocks can be divided into categories such as i-node block, [??] blocks, directory blocks, full data blocks, and partially full data blocks.⁴⁹ By implementing a true LRU this can be a disadvantage.⁵⁰ Therefor blocks such as metadata blocks also know as i-node blocks according to Hailperin should be written immediately to the disk so they can be accessed.⁵¹
  
  49: How are last two relevant for metadata handling?
  
  50: How? And if so, then why do the block division?
  
  51: And how does that change the LRU algorithm?
16. The problem can be fixed by using the LRU queue policy. The file should not be touched⁵² if they have recently not been open or has been recently mounted.⁵³ This practically put clock replacement effective because we can sweep the file⁵⁴ using the priority replaced[?]. So the block⁵⁵ can be prioritized based on the priority of their content and the block with least priority can be replaced first.⁵⁶
  
  52: Touched by what?
  
  53: When would a file not accessed or mounted be touched?
  
  54: “Sweep the file” means what?
  
  55: Block? Which block is that?
  
  56: But what is LRU doing wrong that this scheme fixes?
17. Buffering metadata is a bad idea.⁵⁷ File systems metadata incoherence can be fatal if a file is written to buffer then is being read from the disk that file is not there yet.⁵⁸ [??] [??] by writing to the disk often, or you can condense the request from several requests into large ones.⁵⁹ So the disk is treated nicely. Combine all writes into a journal entry.⁶⁰ Then a cleaner will untangle the journal back to […]⁶¹
  
  57: Oh? Suppose you want good performance.
  
  58: That may be, but the problem identifies performance as the problem, not coherence.
  
  59: What is the relation between this and LRU?
  
  60: That seems involved. Isn’t there anything to be done to improve LRU?
  
  61: … the file system occasionally. Journal also acts as a checkpoint for crash recovery.
18. Metadata is usually not in the file. LRU is ordered based on access time (queue),⁶² since metadata isn’t accessed with the file my colleague could change the algorithm so that he uses indexed allocation⁶³ to increase throughput⁶⁴ and access all files the same, without excluding the metadata.
  
  62: Or maybe on first access time.
  
  63: Indexed allocation means what?
  
  64: The throughput of what?
19. The problem with metadata blocks is that the information about where the file is stored is with the file.⁶⁵ So when traversing through a file system blocks with metadata needs to be opened, which takes a lot more time to traverse through the file system.⁶⁶ A change that you could make to the replacement algorithm is to put files with metadata at the end of the queue to be read later.⁶⁷ This way they are […]⁶⁸
  
  65: Wasn’t the point behind metadata blocks to separate a file and its metadata?
  
  66: Maybe, but does it have anything to do with LRU buffer management?
  
  67: But all files have metadata. How does this change anything?
  
  68: … read later and do not slow down other files that could be read faster. They will get read eventually.
An operating-system textbook contains the following description of an address-space structure:
The total virtual space is described by 36 bits, representing 64G words. The top 18 bits, [0..17], represent the segment number. The next 8 bits, [18..25], represent the page number, and the lowest 10 bits, [26..35], represent the offset within the segment.
Is this description of the address-space structure correct? If the description is correct, use it to determine the structure of the virtual address 0xbeef0cafe. If the description is incorrect, explain the minimal set of changes you would make to the description to make it correct.
The description is incorrect. If there are 2¹⁸ segments in a 36-bit address space, each segment has 2^{36 - 18} = 2¹⁸-unit maximum size. A 10-bit segment offset isn’t large enough. If there are 2⁸ pages per segment, each page is 2^{18 - 8} = 2¹⁰ units long. It seems most likely that the last word of the description should be “page” rather than “segment.”
The answers, approximately verbatim, and in no particular order:
1. [ unanswered ]
2. [ unanswered ]
3. This doesn’t describe an address-space structure. There is no need for an offset if you are using a virtual address structure.¹ You will only need a page number and a frame number to correctly place in a word in [??] storage.² This will change the number of bits needed to place these words seeing how there are no offsets³ and keeping the 64G words. These would be the only changes needed to correct this address […]⁴
  
  1: Why not? And is it wrong to use an offset, even if it isn’t needed?
  
  2: Is that the problem this question is raising?
  
  3: How can there be no offsets?
  
  4: … structure.
4. This description of the address space structure is incorrect. The minimal set of changes I would make is to make the description correct is the storage units.⁵ I would also say that it is not representing 64G words.⁶ The top 18 bits would not represent segment numbers and the 8 bits are not page number.⁷ The page numbers would represent more than 8 bits and the segment is not as large as 18 bits⁸ […]⁹
  
  5: What about the storage units? How would they change? How would that fix things?
  
  6: What is not representing 64G words?
  
  7: Why not? How is that wrong?
  
  8: What error do these changes correct?
  
  9: … in this case.
5. [ unanswered ]
6. No, as it stands the description is not correct. To change the description, I would suggest moving the lowest 10 bits representing page number, the middle represent the offset, and the top bits the segment as they are already.¹⁰ This puts the page numbers, which act as the index of the page file[?] at the bottom end of the space¹¹ where they should reside for ease of access,¹² while leaving offset and segment afterwards. […]¹³
  
  10: What was the problem the original arrangement caused, and how does this arrangement solve the problem?
  
  11: The space, or the address?
  
  12: What kind of assumptions are needed to make this true?
  
  13: … for space allocation (size) purposes.
7. [ unanswered ]
8. this is incorrect. virtual space is sized based on the needs of the system. because it is virtual,¹⁴ its space is only limited to the size of the disk.¹⁵ virtual store is based on the size of physical store.¹⁶ the unit sizes are the same but the total size of virtual is vastly larger than physical.¹⁷ so the definition should read that virtual space units are equal to that of physical, but total size is […]¹⁸
  
  14: what is virtual? the system or the space (or both)?
  
  15: doesn’t the virtual-address space impose any limits? and does the virtual address change as different capacity disks are added and removed from the system?
  
  16: is it?
  
  17: if that’s so, how is virtual-store size based on physical-store size?
  
  18: … vastly larger.
9. This description is incorrect. That virtual address has an extra bit in front of the x, which is a zero, giving it a total of 40 bits instead of 36.¹⁹ This number in front can be used to say if the number is signed or unsigned.²⁰ The change I would make to the description is the virtual space is described in 37 bits and has one bit to show if the address is signed or²¹ […]²²
  
  19: What? If the description is incorrect, then it doesn’t matter what 0xbeef0cafe is. Also, if there’s an extra bit, then that’s a total of 37 bits, not 40.
  
  20: What problem does signed vs unsigned address?
  
  21: When is a virtual address ever a signed value?
  
  22: … unsigned.
10. The description is correct. If it was used to determine the structure of that virtual address, 0xbeef would be the page number,²³ with 0cafe as the page offset.²⁴
  
  23: The page number’s only 8 bits, not 16.
  
  24: The question doesn’t identify a page offset.
11. The implementation not correct. 1024 bits²⁵ × 1024k²⁶ × 2⁶ = 64G words. 2¹⁰ x 2¹⁰ x 2⁶ = 2²⁶. There are only 2²⁶ addressable units of memory.²⁷ The problem describes 36 bits.
  
  25: What does the 1024 represent?
  
  26: Ditto.
  
  27: Why is this true?
12. The VA address breakout is incorrect. All that is needed are two breakouts.²⁸ Use the leftmost 10 bits to represent the page number and the remaining 26 bits to represent the offset. This creates 1024 pages with up to 2²⁶ available addresses.²⁹ The total virtual space provided is independent of the number of bits used.³⁰ Clever techniques may be required, but they are not [??].
  
  28: Why are two correct? Why not three? Or one?
  
  29: Those are big segments. How would they be handled efficiently?
  
  30: Oh? So I can have a 64G virtual-address space with a 20-bit virtual addresses? Is that so?
13. [ unanswered ]
14. no, this description is not correct. the changes i would make would be to make the top bits refer to the page, the middle bits refer to the page segment and he final bits refer to the offset within the segment.³¹ the top bits would now be 8, referring to the page. the next 18 bits would be segment and the last 10 bits remain the offset.³²³³
  
  31: why is the arrangement described here right, but the arrangement described in the problem wrong?
  
  32: the 10-bit offset is an offset for what?
  
  33: why is this right and the question’s description wrong?
15. This is correct because virtual store and paging use system-defined fragments that cut big programs into pieces.³⁴³⁵
  
  34: True, but the question is whether or not the fragments are being described correctly.
  
  35: And the interpretation of 0xbeef0cafe?
16. No, this description is not correct. The offset with in segment should have less bits than the page number because they are the least significant.³⁶ I would make it 18 bits for segment, 10 bits for page number 8 bits for offset.³⁷
  
  36: Is that “significant” in the technical sense (smaller values), or in the usual sense (less important)? And what does it mean for a segment offset to be less significant than a page number?
  
  37: Is an 8-big offset big enough for either an 18-bit or 10-bit address region?
17. No, this is not correct. You need not only the segment but also the page frame that corresponds to the page.³⁸ The segment number will tell you what bank[?] for example to page can be looked in. The page frame will show what part of the section the page is in then you have the number itself and the offset of the page on which the disk you need is located.
  
  38: Why is that? There isn’t any virtual-physical translation going on, so what is the value of having a page-frame index?
18. A virtual space ids both the page contains the unit and the offset of the unit within the page.³⁹ So, the virtual space only needs the 8 bits that represent the page # [16..25] and the lowest 10 bits [26..35] that represent the offset within the segment.⁴⁰
  
  39: Ok, but what about a segmented virtual-address space?
  
  40: That’s 18 bits; what about the other 18?
19. This is an incorrect description. Out of 36 bits, the lowest 10 bits would represent the offset, but the top 26 bits would be used to indicate the page number.⁴¹⁴² This is how the page is identified within the virtual address It is not necessary to use 10 bits to identify the sequence number because that doesn’t define the page.
  
  41: What happens to the segments?
  
  42: Is a 10-bit offset big enough for a 26-bit page?
Describe the modifications required to the working-set algorithm to make it useful for determining which of a process’s pages should be ejected to satisfy a page fault.
Keeping track of number of times a page has appeared in successive working-set calculations provides a (not too good) approximation to LRU queueing. Scaling the page count by the number of times each page appeared in one calculation may add a useful measure of current access to the result.
The answers, approximately verbatim, and in no particular order:
1. [ unanswered ]
2. One metadata that would make the working set algorithm useful for ejecting pages in a page fault would be to order the working set so they go from most recently used to least recently used.¹ A page that has recently been used is more likely to be used than the page that was used longest ago. Therefore it can determine the least recently used page and eject it probability of being used again is lowest.²
  
  1: by what process would the working-set algorithm be able to establish this ordering?
  
  2: quite true, but is it possible? how?
3. The modifications required to this algorithm that needs to be made in order to eject the pages to satisfy a page fault is the policy in which they adjust[?] a change[?] in the sequence of actual approximations³ must also become required as well as the time interval.⁴ I would allow all of these in order to only eject specific pages to satisfy the page fault.⁵
  
  3: Actual approximations to what?
  
  4: Which time interval?
  
  5: Which specific pages?
4. Since a working set can only have one copy of every page it accessed, then no duplicates are allowed in the working set. If you modify this so that each set is allowed to see duplicates⁶ you can tell which page has been accessed the most, but also which page has been accessed least.⁷ This way you can eject the page that has been accessed least seeing you it is unlikely to be accessed numerous⁸ […]⁹
  
  6: Duplicate pages? How would the working-set algorithm managed pages if it could have duplicates?
  
  7: How? What is the relation between duplicate pages and page access patterns?
  
  8: Sure, but which page would the modified algorithm determine is accessed least?
  
  9: … times in the future if it was only accessed once or twice in time t. This should make the ws more useful in determining what page to throw out.
5. Modifications the working set algorithm requires include a need for the time interval to correspond to the length of the process¹⁰ as opposed to a set parameter and an oversight that would eliminate the presence of the ejected page in future working sets.¹¹
  
  10: What? What is the length of the process? What units is it measured in?
  
  11: Perhaps, but can such a thing be determined? How?
6. The modification required to the working set would be instead of giving the numbers that should be in the ws,¹² give the numbers that should be ejected.¹³ So the ending[?] WS will have all the numbers that were NOT ejected¹⁴ and that will satisfy a page fault.
  
  12: Numbers? Does that mean page-frame numbers? Or something else?
  
  13: Is that possible? How?
  
  14: Doesn’t the unmodified working-set algorithm have that information alreday?
7. Recalculate the working set at a given interval, \(\tao\), and change the depth which records the pages in working set most recently used.¹⁵ Pages resident in memory but are not found within the depth within interval \(\tao\) are candidates for ejection.¹⁶ Pages should contain a reference/modified bit the algorithm should clear in interval \(\tao\), this will ensure the working set contains most used pages and create acceptable rejection candidates.
  
  15: What is the depth in the working-set algorithm?
  
  16: How is depth measured, and what is its relation to recent access?
8. Some modification that one required to determine which of a process’s pages should be ejected to satisfy a page fault is to¹⁷ keep track of which pages are in the working set. This can be done by using the aging algorithm;¹⁸ any page contains a 1 bit among the high-order n bits of the counter¹⁹ is considered to be part of the working set. If the page has not been referenced in n consecutive clock […]²⁰
  
  17: That twenty-two words that add nothing to the answer.
  
  18: Which aging algorithm?
  
  19: What counter?
  
  20: … ticks it is removed from the working set.
9. The modification needed to be made is the working set algorithm to determine pages to be ejected to satisfy a page fault include²¹ the ability to track all the pages that the process accesses in the given time span.²² When a page fault occurs, this list²³ is compared to the pages allocated, and then any pages not accessed are removed and pages that are accessed are allocated in their place.
  
  21: That’s twenty-three words that add nothing to the answer.
  
  22: Doesn’t an unmodified working-set algorithm already use this information?
  
  23: Which list?
10. Working set algorithm needs to be changed to see which pages have been used least recently and also hopefully not modified.²⁴ This helps the OS to get as close as possible to an LRU algorithm.²⁵ It can of course not take this approach,²⁶ but this is the most ideal algorithm.
  
  24: Is it possible to make such changes to the working-set algorithm? If it is, how are the changes made?
  
  25: Why does the OS want to get as close as possible to an LRU algorithm? Does that even make sense?
  
  26: By “it” do you mean the working-set algorithm? Or the OS? In either, or some other, case, then what can be done to solve the problem given in the question?
11. Keep tack of each process working set and make sure the pages are in memory before letting the process run.²⁷ This will put on the page faults when new processes are executed.
  
  27: Which pages should be store? How should the working-set algorithm be modified to check the pages?
12. A useful working set algorithm would be to use a used-based replacement where toss pages not recently used. Periodically clear reference bits to find old unreferenced pages.²⁸ Toss not referenced before referenced pages, and not modified before modified pages.²⁹
  
  28: Would the working-set algorithm be doing this, or something else (such as the MMU)?
  
  29: Ok, but can the working-set algorithm be made to do that? How?
13. If the working set size exceeds the number of frames,³⁰ the OS selects a process to suspend and it is able to restart later.³¹ This prevents thrashing and keeps rate of multiprogramming as high as possible,³² implementing LRU.³³ If page fault occurs you can use a working set model with a fixed-interval timer interrupt and reference bit, and you can examine the reference bit and 2 in-memory its to find out if the page was […]³⁴
  
  30: Which number of frames? The total number of frames in the system? The number of frames allocated to a process?
  
  31: That seems excessive. And what does it have to with the working-set algorithm?
  
  32: How does ejecting processes keep the multiprogramming rate high?
  
  33: Implementing LRU over what?
  
  34: … used within last 10,000-15,000 references. (If delta equals 10,000 references with an interrupt every 5,000) if it was used, one of them will be on , and will be in the working set. If not, it can be suspended or ejected.
14. When a page fault occurs record the time,³⁵ then when the next page fault occurs we compute the time since the previous fault. If the time (t) is small, add the page to the set.³⁶ If it is large we eject all pages from the set that have not been reference since the last fault, then add the new page to the set.³⁷
  
  35: Is the working-set algorithm recording the page-fault time? Is that how the working-set algorithm operates, or is this the modification? If it’s the modification, is it possible to modify the working-set algorithm to have such behavior?
  
  36: Which set? The working set, or some new set added to the working-set algorithm?
  
  37: That seems excessively violent, and not at all in the spirit of the working-set algorithm. How does the scheme solve the problem?
15. By using a fixed timer set to roughly half the size of the working set window (delta), we can cause a timer interrupt and copy and clear reference bit values for each page.³⁸ By doing this, when a page fault occurs, examine³⁹ the current reference-bit and two bits in memory, we can determine whenever a page was used within 3/2 (delta) references. If it was used, at least one bit checked in memory will be […]⁴⁰
  
  38: True, but the unmodified working-set algorithm does the same thing. What is the advantage of using a half delta?
  
  39: Is the working-set algorithm doing this examining? If so, then the working-set algorithm would also have to be invoked on every page fault; is that a suggested modification?
  
  40: … on. If it has not been referenced in that interval the bits will be off. If the bits are off it would be safe to eject that page, and if a bit is on it should be left alone.
16. Need to set a boundary[?] limit for the number of page faults.⁴¹ If the page fault frequency goes over limit then the process needs more frames and if it low then the process has too many frames.⁴² So the strategy is to suspend a process once the limit is crossed and then the free frame will be redistributed to the process that would need then this will be useful since it creates balance among processes⁴³ […]⁴⁴
  
  41: How is this possible? Limiting page faults seems to depend on process behavior, which is beyond the scope of any page manager.
  
  42: True, but how does that have anything to do with determining which page should be ejected.
  
  43: So this is a recommendation to punt: whenever a process is paging too much, swap it out? How would the working-set algorithm be modified to implement this scheme?
  
  44: … and decrease frequency of page faults.
17. the working set algorithm should check for the time since the page was last used while it is working.⁴⁵ if it checks the pages within[?] its set, it will be able to determine which page to eject next,⁴⁶, therefore satisfying the page fault that is thrown. as the sets change, it will be able to check more pages and be able to flag more pages for ejection if another page fault is thrown. this would […]⁴⁷
  
  45: is checking last-use time something the working-set algorithm can do?
  
  46: by what mechanism can the working-set algorithm determine these pages?
  
  47: … make it useful and efficient in determining the page ejects.
18. A modification to the working set algorithm that could be made to determine candidacy for ejection could be a counter that keeps track of the amount of pages accessed by a process over a set parameter of time. If the number of pages in the working set falls below a specified threshold, then eject the pages⁴⁸ that were least recently accessed⁴⁹ this would obviously also require the implementation of an access bit. And perhaps a […]⁵⁰
  
  48: Is this backwards? The threshold is undefined, and so is the relation between the working set and the threshold, but it seems likely that if the working set falls below a threshold, there are too many page frames allocated to the process, rather than too few.
  
  49: And this is determined how? Presumably something to do with the counter added, but what?
  
  50: … modification bit as an additional fail safe.
19. The modifications that should be made to the working set algorithm is to eject the page that is least in demand.⁵¹ In a working set algorithm a process accesses a set of pages within a certain amount of time. Pages that are in not in demand should not be stored in the cache for long.⁵² A page that is not accessed should not be stored in the cache and should be skipped the next time […]⁵³
  
  51: Right, but how is that done?
  
  52: Indeed not. But which pages are those?
  
  53: … the algorithm loads pages into the cache.
A colleague of yours is designing a new file system for an old operating system and comes to you for advice about deciding the representation for file-block allocation metadata. A) Suggest some data your colleague could gather by studying existing file systems. B) Describe how the data collected from other file systems can be used to decide among possible file-block metadata representations.
Keep in mind that: 1) A good answer to this question will make clear some of the possible choices for metadata representation. 2) Your answer should give an approach, with examples, to solving your colleague’s problem; it doesn’t have to solve your colleague’s problem. 3) The only problem your colleague is concerned with is file-block metadata representation; all other file-system aspects are not relevant to your colleague’s concern or your answer.

Under the principle that small data can be efficiently handled in practically any way, recommend that your colleague gather file sizes in existing file systems. If the vast majority of files are small, for some definition of “vast” and “small” then go with simplicity and use a linked-list representation. If a vast majority are large, then go with a tilted n-ary tree and indirection blocks.
The answers, approximately verbatim, and in no particular order:
1. Because there are several methods that are good but with draw backs like contiguous allocation linked-list allocation, link-list analysis, access tree a good allocation in the end would be a hybrid allocation.¹ This combines all the good stuff into one approach. Hybrid allocation file block runs for efficiency and link them for flexibility.
  
  1: What kind of data could be collected from existing systems to justify this claim?
2. He should check what[?] is stored[?] in metadata in other systems.² He should also check how the blocks are allocated in other systems.³ Also note the use of the file system what is it designed to do. How are the files accessed, and for what purpose. He should then analyze his file system and compare to see how it is used, and compared to other file systems what similarities there are.⁴ A good example is […]⁵
  
  2: What in particular should be checked?
  
  3: How would such information be used?
  
  4: How would the result of this comparison be used?
  
  5: … if the system is using linked list allocation the metadata should obviously precede[?] the locations of each block in the store. It should also reference where to start and where to end and the links in between or in the case of a tree the metadata should reference its parent and its children.
3. [ unanswered ]
4. The colleague can learn from the existing structures what data structures are used, size of files stored, the algorithms used to fetch and store the files, how the files are buffered, and when it beneficial to use indirect or direct blocks.⁶ The data collection can show the colleague what representation of metablocks work for what types of systems. Systems with larger files should use indirect blocks. Extent maps avoids into on individual blocks.⁷ Block trees […]⁸
  
  6: That’s a lot of information to extract; how might it be done?
  
  7: How would the information gathered from other file systems help make these choices?
  
  8: … provides efficient access to extent maps. By seeing how these representations work the colleague can see what will work best on his system.
5. He could look into linked-list allocation for file blocks.⁹ This will help with understanding the background of file block allocation. From there he could implement an external link table that holds the pointers to the separate parts of the file.¹⁰ Using file blocks for the data and other blocks for the links. This is a simple way to represent file-block allocation for metadata. Below is an example [diagram].
  
  9: Assuming the existing file systems used a linked-list allocation.
  
  10: And what in the existing file-system data would justify this choice?
6. The colleague could look at the is the most common data stored by other operating system.¹¹ This will give them an idea of what data is regarded to be most important by those systems, well as how it can be represented.¹²
  
  11: How would your colleague study existing file systems to determine this information?
  
  12: How would this information influence the way file-block allocations are represented in the new file system?
7. The best approach would be to examine the metadata from the old files although this cannot be found in the files themselves.¹³ By taking a look at this old data you can observe how the other file systems have dealt with the data and improve upon the things the old systems lacked.¹⁴ This metadata, for instance, can tell you how files were kept in the system.
  
  13: Any particular part of the metadata, or all the metadata?
  
  14: In what ways might this be done?
8. Keep the metadata in an array with the file itself.¹⁵ Track properties such as protection, length, temporary, access rights, time last changed, time last accessed, size, ascii/binary/log[?].¹⁶ Utilizing of block size storage can be used to come up with a mean block size for the OS.
  
  15: What justifies this choice?
  
  16: What are the relations between this information and file-block allocation representations?
9. Some data this colleague could collect is the history of the OS in order to get an understanding of how they work.¹⁷ Then gather numerous existing file systems that would work properly of[?] the OS he/she is going to use. Some choices is the disk arrangements of the data stripping of the file system to alter to work on the OS.¹⁸ The size and storage management also plays a significant factor in this case.¹⁹
  
  17: That seems a little expansive, given that the question is about file systems. Why is it necessary?
  
  18: How would these choices be made?
  
  19: How is this significance manifested?
10. I would suggest that my colleague study virtual store, particularly paging allocation.²⁰ This would give him a clear understanding of what his options are for representing clearly related to a piece of data but not contained in the data itself.²¹ An array of metadata would probably be ineffective for his purposes²² so I would suggest a linked list structure. This could easily be created to link metadata to its appropriate file-blocks to allow for easy […]²³
  
  20: What do virtual store and paging allocation have to do with implementing file-block allocation?
  
  21: What does this sentence mean?
  
  22: Why so?
  
  23: … access to the contents of each node. The only issue with this implementation is the performance hostile results that would occur as greater number of file blocks are allocated in addition to the problem of constantly having to go through the list to update nodes.
11. I would suggest focusing on a few areas for representing metadata. The first of which would be utilizing a naming convention associated with the file type much like any standard OS utilities today.²⁴ This is the easiest way to sort files based on the type of content they contain.²⁵ Then I would focus on basic file protections (read, write, and execute).²⁶ The last area of importance is storing time artifacts about the file (creating date, […]²⁷
  
  24: How does this metadata information relate to file-block allocation?
  
  25: Maybe, but why is sorting based on content-type relevant to the problem at hand?
  
  26: The relation of this information to file-block allocation representations is unclear.
  
  27: … access date, modification data, etc) By showing concern for protection and data data, this information could be used to keep better tack of when blocks have been accessed, and to ensure that only the current processes and users are accessing them.
12. We can use a bout[?] centered[?] block and value before block to gather all the information to gather all the information about block size and its FCB provides.²⁸ Once is love all this information LP can create a table with all the block information and he can arrange the file allocation table based on the block priority and can use all empty space in the table. It will cache[?] file block metadata problem but may²⁹ […]³⁰
  
  28: What does this sentence mean?
  
  29: What does this answer mean?
  
  30: … not fully solve the problem.
13. Data that my colleague can gather from studying other file systems is what metadata the file is contained with.³¹ He can see how fast the system runs with the amount of metadata is in a file. My colleague can see how these systems perform and can add or remove metadata to his choosing.³² Information about ownership and size will be included, but other information like date created that is not as important can be excluded.³³
  
  31: What kind of data is “metadata the file is contained with”?
  
  32: How would the metadata studied influence choosing?
  
  33: Why is ownership important?
14. Average size of the files, average number of files, a user uses, the various types of files a user uses,³⁴ and the type of data stored in those files.³⁵ Some of this data is fixed in size and some is variable length. The metadata representation will need to be a mix of fixed size and variable length records.³⁶ Size, average number of flies are fixed integer values, but data such as the type of data […]³⁷
  
  34: File times defined how?
  
  35: File data characterized how?
  
  36: How is this determined?
  
  37: … in a file could be visible. Use a linked structure to represent such data. Hybrid records is a good implementation of this. Older OS may not support some of the modern enhancements to file metadata, such as long file names.
15. First, he should study other file systems to see other implementations.³⁸ If he observes many different implementation, this could better aid him in deciding his approach.³⁹ I would suggest external link-blocks,⁴⁰ since this is the only representation I have any knowledge of. Simply have link blocks that correspond to specific files which can be logged together in a journal.
  
  38: Yes, as the question states.
  
  39: How?
  
  40: As something to study in existing file systems, or something to implement in the new file system?
16. A) Data my colleague could gather from existing file systems would e information on what strategies they utilize concerning metadata, as well as what hardware is available to them.
  B) With this data we can determine how to approach the old operating system. It may be wise to first strengthen buffer coherence, to assure there aren’t any problems with the metadata representation.⁴¹ Another suggestion would be to singly link metadata to the file itself through⁴² […]⁴³
  
  41: It may indeed, but what factors would suggest the wisdom of strengthening buffer coherence? And what does buffer coherence have to do with representing file-block allocation metadata?
  
  42: What metadata information would justify this suggestion?
  
  43: … careful organization.
17. Metadata can be represented in file systems in directory entries and can be split or shared with the file system superstructure.⁴⁴ The approach to this would be to make your directories into a tree structure by using directories in each other and keep the metadata in its directory and not allow access to it from elsewhere.⁴⁵
  
  44: True, but how is this significant to your colleague?
  
  45: What is the justification for this recommendation?
18. [ unanswered ]
19. There are various forms of allocation used: contiguous, linked list, and i-nodes.⁴⁶ By using i-nodes, this is the most efficient and is least taxing on the memory.⁴⁷ Therefore with this being said, i-node allocation should be used to implement a file system.⁴⁸ According to Hailperin, i-nodes are the same as metadata.
  
  46: How are i-nodes similar to the contiguous and linked-list allocations?
  
  47: What existing file-system metadata should my colleague look at to determine this?
  
  48: On what data is this decision based?

This page last modified on 2012 April 16.