- 10.2
Given m frames, p references, n distinct page numbers
- What
is the lower bound on the number of page faults
n – these are compulsory misses.
This could occur if page replacement is perfect, or there is more memory
than needed (m > n)
- What
is the upper bound on the number of page faults
p – you could potentially miss on
every page. This could occur if there is very little memory (m = 1) or if
page replacement is particularly bad.
- 10.3
Explain how the system establishes the physical location of a virtual
address in the given computer system. Distinguish between hardware and
software operations
The
virtual address in binary form is
0001 0001 0001 0010 0011 0100 0101 0110
Since the page size is 212, the page table size is 220.
Therefore the low-order 12 bits “0100
0101 0110” are used as the displacement into the page, while the remaining
20 bits “0001
0001 0001 0010 0011” are used as the displacement in the page table. This
displacement is looked up in hardware in the TLB. If there is a miss in
the TLB, than either the hardware may walk the page table for the entry,
or it may raise an exception, and the operating system can check the page
table.
If the entry in the page table is valid, then either hardware or the OS
puts it in the TLB and the process continues executing.
If the entry is invalid, the OS decides what to do next – either signal
the process that it accessed an invalid address, or bring in the page from
somewhere else. If it brings in the page, it must find a free frame (which
may cause paging out another page), and then read in the missing page from
the disk. Once the page is in, the OS marks the page table entry as valid,
possibly sticks the entry in the TLB, and lets the process continue.
- 10.7
List the costs and benefits of virtual memory. What measures can you take
to ensure the costs don’t exceed the benefits?
The costs
are additional hardware, additional complexity in the OS, additional
memory usage for virtual memory data structures, and slower access time.
The benefits are good utilization of memory, protection, and larger
logical address space than physical address space.
You can make sure for that programs that fit in memory, there are no
unnecessary overheads –e.g. extra accesses to memory, page faults. Also,
you can use good page replacement algorithms, to minimize the number of
page faults.
- 10.11
How many page faults are generated using LRU replacement with 5 frames?
LRU: 8
FIFO: 10
Optimal: 7
- 10.12
How can you simulate a reference bit if it is not provided by hardware?
Calculate the cost of doing so.
You can
use the valid/invalid bit supported in hardware to simulate the reference
bit. Initially set the bit to invalid. On first reference a trap to the
operating system is generated. The operating system will set a software
bit to 1 and reset the valid/invalid bit to valid.
The cost is that of doing a page fault (e.g. 100s of cycles) to set the
reference bit.
- 11.3
Why do some systems keep track of the type of file, while others leave it
to the user? Which system is better?
Some
systems allow different file operations based on the type of the file (for
instance, an ASCII file can be read as a stream while a database file can
be read via a index to a block). Other systems leave such interpretation
of a file’s data to the process and provide no help in accessing the data.
The method that is “better” depends on the needs of the processes on the
system, and the demands the users place on the operating system. If a
system runs mostly database applications, it may be more efficient for the
operating system to implement a database-type file and provide operations,
rather than making each program implement the same thing (possibly in
different ways). For general-purpose systems it may be better to only
implement basic file types to keep the operating system size smaller and
allow maximum freedom to the processes on the system.
- 11.5
What are the advantages / disadvantages of recording the name of the
creating program with the file’s attributes?
By
recording the name of the creating program, the operating system is able
to implement features (such as automatic program invocation when the file
is accessed) based on this information. It does add overhead in the
operating system and require space in the file descriptor, however.
- 11.11
Subdirectories as files
a.
Describe protection problems that could arise
One piece of
information kept in a directory entry is file location. If a user could modify
this location, then he could access other files defeating the access-protection
scheme.
b.
Suggest a scheme for dealing with each of the protection
problems
Do not allow
the user to directly write onto the subdirectory. Rather, provide system
operations to do so.
- 11.12
Sharing a file among 4990 of 5000 users
a.
Unix
Create a group with 4990 users and give the group access to the file
Put 4990 users on the file with the appropriate access
b.
What other scheme could be more effective?
Create a group with the 10 users that
cannot access the file. Set the ACL on the file to deny access to the group of
10 users.
Put the 10 users on the file with no access, and grant everyone access.