Flashcards
3046
Flashcards do conjunto (76)
- 1On early computers, every byte of data read or written was handled by the CPU (i.e., there was no DMA). What implications does this have for multiprogramming?the prime reason for multiprogramming is give the CPU something to do while waiting for I/O to complete.
If there is no DMA, the CPU will be fully occupied doing I/O, so there is nothing to gain. - 2Which of the following instructions should be allowed only in kernel mode? a) Disable all interrupts b) Read the time-of-day clock c) Set the time-of-day clock d) Change the memory mapa, c, d
- 3What is the key difference between a trap and an interrupt?- a trap is caused by the program and is synchronous with it. If the program runs again and again, the trap will always occur at the exactly the same position in the instruction steam.
- an interrupt is caused by the external event and its timing is not reproducible. - 4For each of the following system calls, give a condition that causes it to fail: fork, exec and unlink- Fork can fail if there are no free slots left in the process table.
- Exec can fail if the file name given does not exist or is not a valid executable file.
- Unlink can fail if the file to be unlinked does not exist or the calling process does not have the authority to unlink it. - 5A file whose descriptor is fd contains the following sequence of bytes: 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5. The following system calls are made: lseek(fd, 3, SEEK_SET) Read(fd, &buffer, 4) Where the lseek call makes a seek to byte 3 of the file. What does buffer contain after the read has completed?- if the call fails because fd is incorrect, it can return -1. it can also fail because the disk is full and it is not possible to write the number of bytes requested. on a correct termination, it always returns N bytes.
- 6What is the essential difference between a block special file and a character special file?-block special files consist of numbered blocks, each of which can read or written independently. it is possible to seek to any block and start reading or writing. this is not possible with character special files.
- 7The client-server model is popular in distributed systems. Can it also be used in a single- computer system?Yes, it can, especially if the kernel is a message-passing system
- 8In Fig. 2-2, three process states are shown. In theory, with three states, there could be six transitions, two out of each state. However, only four transitions are shown. Are there any circumstances in which either or both of the missing transitions might occur?The transition from blocked to running is conceivable. if a process is blocked on I/O and I/O finishes. if the CPU is idle, the process could go directly from block to running. but it is not possible for a ready process to be blocked, because a ready process cannot do anything, it is not running, only a running process can be blocked.
- 9On all current computers, at least part of the interrupt handler is written in assembly language. Why?- high level languages do not allow access to CPU hardware that is required. eg: disable interrupt service.
- 10When an interrupt or a system call transfers control to the operating system, a kernel stack area separate from the stack of the interrupted process is generally used. Why?first , you do not want operating system to crash because a poorly written user program does not allow for enough stack space. second if the kernel leave stack data in a user program's memory space, a malicious user might be able to use this data to find out information about other processes.
- 11If a multithreaded process forks, a problem occurs if the child gets copies of all the parent’s threads. Suppose that one of the original threads was waiting for keyboard input. Now two threads are waiting for keyboard input, one in each process. Does this problem ever occur in single-threaded processes?no, if a single-threaded process is blocked on the keyboard, it cannot fork.
- 12In this problem you are to compare reading a file using a single-threaded file server and a multithreaded server. It takes 15 msec to get a request for work, dispatch it, and do the rest of the necessary processing, assuming that the data needed are in the block cache. If a disk operation is needed, as is the case one-third of the time, an additional 75 msec is required, during which time the thread sleeps. How many requests/sec can the server handle if it is single threaded? If it is multithreaded?15+75=90
15*2/3+90*1/3=40
1000/40=25
1000/15=66 - 13The CDC 6600 computers could handle up to 10 I/O processes simultaneously using an interesting form of round-robin scheduling called processor sharing. A process switch occurred after each instruction, so instruction 1 came from process 1, instruction 2 came from process 2, etc. The process switching was done by special hardware, and the overhead was zero. If a process needed T sec to complete in the absence of competition, how much time would it need if processor sharing was used with n processes?It will need nT sec
- 14Measurements of a certain system have shown that the average process runs for a time T before blocking on I/O. A process switch requires a time S, which is effectively wasted (overhead). For round-robin scheduling with quantum Q, give a formula for the CPU efficiency for each of the following: (a) Q = ∞ (b) Q > T (c) S < Q < T (d) Q = S (e) Q nearly 0a) T/(Ｔ＋S) *100%
b) T/(Ｔ＋S) *100%
c) Q/(Q+S) * 100%
d) S/(S+S) *100% = 50%
e) utilization nearly 0 - 15The aging algorithm with a = 1/2 is being used to predict run times. The previous four runs, from oldest to most recent, are 40, 20, 40, and 15 msec. What is the prediction of the next time?S n = aT n – 1 + (1 – a)S n – 1
Let a = 1⁄2. Assume S 1 = T 1 .
S 2 = aT 1 + (1 – a)S 1 = 1⁄2T 1 + 1⁄2S 1 = T1 = 40
S 3 = aT 2 + (1 – a)S 2 = 1⁄2T 2 + 1⁄2S 2 = 1⁄220 + 1⁄240 = 30
S 4 = aT 3 + (1 – a)S 3 = 1⁄2T 3 + 1⁄2S 3 = 1⁄240 + 1⁄230 = 35
S 5 = aT 4 + (1 – a)S 4 = 1⁄2T 4 + 1⁄2S 4 = 1⁄215 + 1⁄235 = 25 - 16Does the busy waiting solution using the turn variable (Fig. 2-20 – Strict Alternation Code Block) work when the two processes are running on a shared-memory multiprocessor, that is, two CPUs sharing a common memory?Yes, it still works, but it still is busy waiting, of course.
- 17Does Peterson’s solution to the mutual exclusion problem shown in Fig. 2-21 work when process scheduling is preemptive? How about when it is nonpreemptive?it will certainly work with preemptive scheduling.
it may fail it is non-preemptive, because if turn is 0 and process 1 is running, then it will loop forever. - 18Give a sketch of how an operating system that can disable interrupts could implement semaphores.public class Semaphore {
private int count;
private process_list queue;
Semaphore( int n ) {
count = n;
}
void public down() {
disable_interrupt();
count = count – 1;
if (count < 0) {
queue.push(this process);
enable_interrupt();
sleep();
}
else enable_interrupt();
}
void public up() {
disable_interrupt();
count = count + 1;
if (count <= 0) {
P = queue.pop();
wakeup(P);
}
enable_interrupt();
}
} - 19Show how counting semaphores (i.e., semaphores that can hold an arbitrary value) can be implemented using only binary semaphores and ordinary machine instructions.public class countingSemaphore {
private int count;
private binarySemaphore M, B ;
countingSemaphore( int n ) {
count = n;
M = new binarySemaphore(1);
B = new binarySemaphore(0); }
public void down() {
M.down();
count = count – 1;
if (count < 0) {
M.up();
B.down();
}
else M.up();
}
public void up() {
M.down();
count = count + 1;
if (count <= 0) {
B.up();
}
M.up();
}
} - 20Students working at individual PCs in a computer laboratory send their files to be printed by a server which spools the files on its hard disk. Under what conditions may a deadlock occur if the disk space for the print spool is limited? How may the deadlock be avoided?if jobs cannot start printing until they are fully spooled, deadlock is possible.
solution is that the printer should start printing before it is fully spooled and reserving the space thus released for the rest of that job. - 21Fig. 3-3 shows the concept of a resource graph. Do illegal graphs exist, that is graphs that structurally violate the model we have used of resource image? If so, give an example of one.a square with arcs
going from it to two or more processes means that all those processes
hold the resource, which violates the rules
Arcs from squares
to squares or from circles to circles also violate the rules - 22Suppose that in Fig, 3-6 C ij + R ij > E j for some i. What implications does this have for all the processes finishing without deadlock?the process is asking for more resources than the system has, so it can never finish.
- 23Can the resource trajectory scheme of Fig. 3-8 also be used to illustrate the problem of deadlocks with three processes and three resources? If so, how can this be done? If not, why not?Yes. Do the whole thing in three dimensions. The z-axis measures the
number of instructions executed by the third process. - 24A system has two processes and three identical resources. Each process needs a maximum of two resources. Is deadlock possible? Explain your answer.The system is deadlock free. Suppose that each process has one
resource. There is one resource free. Either process can ask for it and get
it, in which case it can finish and release both resources. Consequently
deadlock is impossible. - 25Consider the previous problem again, but how with p processes each needing a maximum of m resources and a total of r resources available. What condition must hold to make the system deadlock free?r ≥ p(m − 1) + 1.
- 26A computer has six tape drives, with n processes competing for them. Each process may need two drives. For which values of n is the system deadlock free?n < 6
- 27In an electronic funds transfer system, there are hundreds of identical processes that work as follows. Each process reads an input line specifying an amount of money, the account to be credited, and the account to be debited. Then it locks both accounts and transfers the money, releasing the locks when done. With many processes running in parallel, there is a very real danger that having locked account x it will be unable to lock y because y has been locked by a process now waiting for x. Devise a scheme that avoids deadlocks. Do not release an account record until you have completed the transactions. (In other words, solutions that lock one account and then release it immediately if the other is locked are not allowed.)number the resources (the accounts) with their
account numbers,
After reading an input line, a process locks the lower-
numbered account first, then when it gets the lock,
, it locks the other one. Since no process ever waits for an account
lower than what it already has, there is never a circular wait, hence never
a deadlock. - 28In this problem you are to compare the storage needed to keep track of free memory using a bitmap versus using a linked list. The 128-MB memory is allocated in units of n bytes. For the linked list, assume that memory consists of an alternating sequence of segments and holes, each 64 KB. Also assume that each node in the linked list needs a 32-bit memory address, a 16-bit length, and a 16-bit next-node field. How many bytes of storage is required for each method? Which one is better?for small n linked list is better. for big n bitmap is better.
- 29The Intel 8086 processor does not support virtual memory. Nevertheless, some companies previously sold systems that contained an unmodified 8086 CPU and do paging. Make an educated guess as to how they did it. Hint: Think about the logical location of the MMU.They built an MMU and inserted it between the 8086 and the bus.
Thus all
8086 physical addresses went into the MMU as virtual addresses.
The
MMU then mapped them onto physical.
Remember that MMU are supposed to be transparent to users and in this
case, it is transparent even to CPU!addresses, which went to the bus. - 30The amount of disk space that must be available for page storage is related to the maximum number of processes, n, the number of bytes in the virtual address space, v, and the number ofbytes of RAM, r. Give an expression for the worst case disk space requirements. How realistic is this amount?total virtual address space for all the processes combined is nv.
an amount r can be in RAM, so the amount of disk storage
required is only nv − r. - 31Suppose that a machine has 38-bit virtual addresses and 32-bit physical addresses. (a) What is the main advantage of a multilevel page table over a single-level one? (b) With a two-level page table, 16-KB pages, and 4-byte entries, how many bits should be allocated for the top-level page table field and how many for the next-level page table field? Explain.(a) A multilevel page table reduces the number of actual pages of the page
table that need to be in memory because of its hierarchic structure. In fact,
in a program with lots of instruction and data locality, we only need the
top-level page table (one page), one instruction page and one data page.
(b) The offset field requires 14 bits to address 16 KB. That leaves 24 bits for
the page fields. Since each entry is 4 bytes, one page can hold 16 KB / 4
bytes = 2 14 / 2 2 = 2 12 page table entries and therefore requires 12 bits to
index one page. So allocating 12 bits for each of the page fields will
address all 2 38 bytes. - 32A computer has 32-bit virtual addresses and 4KB pages. The program and data together fit in the lowest page (0–4095) The stack fits in the highest page. How many entries are needed in the page table if traditional (one-level) paging is used? How many page table entries are needed for two-level paging, with 10 bits in each part?For a one-level page table, there are 2 32 /2 12 or 1 M pages needed. Thus
the page table must have 1 M entries and only two of these entries, the
first and the last, are needed.
For two-level paging, the main page table has 1 K entries, each of which
points to a second page table. Only two of these are used. Thus in total
only four page table entries are needed, two in the top-level table and one
in each of the lower-level tables. - 33A machine has 48-bit virtual addresses and 32-bit physical addresses. Pages are 8 KB. How many entries are needed for the page table?With 8 KB pages and a 48-bit virtual address space, the number of virtual
pages is 2 48 /2 13 , which is 2 35 (about 34 billion) - 34A small computer has four page frames. At the first clock tick, the R bits are 0111 (page 0 is 0, the rest are 1). At subsequent clock ticks, the values are 1011, 1010, 1101, 0010, 1010, 1100, and 0001. If the aging algorithm is used with an 8-bit counter, give the values of the four counters after the last tick.The counters are
Frame 0: 01101110
Frame 1: 01001001
Frame 2: 00110111
Frame 3: 10001011 - 35In the WSClock algorithm of Fig. 4-22(c), the hand points to a page with R = 0. If τ = 400, will this page be removed? What about if τ = 1000?The age of the page is 2204 − 1213 = 991. If τ = 400, it is definitely out of
the working set and it was not recently referenced so it will be evicted.
The τ = 1000 the situation is different. Now the page falls within the
working set (barely), so it is not removed. - 36How long does it take to load a 64-KB program from a disk whose average seek time is 10 msec, whose rotation time is 10 msec, and whose tracks hold 32 KB (a) for a 2-KB page size? (b) for a 4-KB page size? The pages are spread randomly around the disk and the number of cylinders is so large that the chance of two pages being on the same cylinder is negligible.(a) Page transfer time = (20 msec / 32 KB) × 2 KB = 1.25 msec
So, average page read time = average seek time + average rotational
latency + page transfer time = 10 + 10 + 1.25 msec = 21.25 msec
64-KB program has 64 KB / 2 KB = 32 pages. So, program loading
time = average page read time × 32 = 21.25 × 32 msec = 680 msec
(b) Page transfer time = (20 msec / 32 KB) × 4 KB = 2.5 msec
So, average page read time = average seek time + average rotational
latency + page transfer time = 10 + 10 + 2.5 msec = 22.5 msec
64-KB program has 64 KB / 4 KB = 16 pages. So, program loading
time = average page read time × 16 = 22.5 × 16 msec = 360 msec - 37A computer provides each process with 65,536 bytes of address space divided into pages of 4096 bytes. A particular program has a text size of 32,768 bytes, a data size of 16,386 bytes, and a stack size of 15,870 bytes. Will this program fit in the address space? If the page size were 512 bytes, would it fit? Remember that a page may not contain parts of two different segments.There are 16 4096-byte pages per process. The text is eight pages, the
data are five pages, and the stack is four pages. The program does not fit
because it needs 17 4096-byte pages.
With a 512-byte page, the situation is different. There are now 128 512-
byte pages per process. Here the text is 64 pages, the data are 33 pages,
and the stack is 31 pages, for a total of 128 512-byte pages, which fits.
With the small page size it is ok, but not with the large one. - 38(a) (b) (c) (d) Fetch from segment 1, page 1, offset 3 Store into segment 0, page 0, offset 16 Fetch from segment 1, page 4, offset 28 Jump to location in segment 1, page 3, offset 32.(a) The page can be fetched from page frame 14 at offset 3.
(b) Protection fault; write operation is not allowed for segment 0.
(c) Page fault; page 4 has not yet been loaded from the disk.
(d) Protection fault; execute operation is not allowed for segment 1. - 39Can you think of any situations where supporting virtual memory would be a bad idea, and what would be gained by not having to support virtual memory? Explain.Generally virtual memory support is not needed when the memory
requirements of all applications are well known and controlled. Some
examples are special-purpose processors (e.g., network processors),
embedded processors, and super-computers (e.g., airplane wing design).
In these situations, we should always consider the possibility of using
more real memory. If the operating system did not have to support virtual
memory, the code would be much simpler and smaller. - 40Figure 5-3(b) shows one way of having memory-mapped I/O even in the presence of separate buses for memory and I/O devices, namely, to first try the memory bus and if that fails try the I/O bus. A clever computer science student has thought of an improvement on this idea: try both in parallel, to speed up the process of accessing I/O devices. What do you think of this idea?It is not a good idea. The memory bus is surely faster than the I/O bus.
Consider what happens with a normal memory request. The memory bus
finishes first, but the I/O bus is still busy. If the CPU waits until the I/O bus
finishes, it has reduced memory performance to that of the I/O bus.
If there were some way to instantaneously abort the previous I/O bus
reference to try the second one, the improvement might work, but there is
never such an option. All in all, it is a bad idea. - 41Suppose that a computer can read or write a memory word in 10 nsec. Also suppose that when an interrupt occurs, all 32 CPU registers, plus the program counter and PSW are pushed onto the stack. What is the maximum number of interrupts per second this machine can process?An interrupt requires pushing 34 words onto the stack. Returning from the
interrupt requires fetching 34 words from the stack. This overhead alone is
68 × 10 = 680 nsec.
Thus the maximum number of interrupts per second is 10 9 / 680 = about
1.47 million, assuming no work for each interrupt. - 42A typical printed page of text contains 50 lines of 80 characters each. Imagine that a certain printer can print 6 pages per minute and that the time to write a character to the printer’s output register is so short it can be ignored. Does it make sense to run this printer using interrupt-driven I/O if each character printed requires an interrupt that takes 50 μsec all-in to service?The printer prints 50 × 80 × 6 = 24,000 characters/min = 400
characters/sec.
Each character uses 50 μsec of CPU time for the interrupt, so collectively
in each second the interrupt overhead is 400 × 50 μsec = 20 msec.
Using interrupt-driven I/O, the remaining 980 msec of time in each second
is available for other work. In other words, the interrupt overhead costs
only 20 msec/1000 msec = 2% of the CPU, which will hardly affect the
running program at all. - 43In which of the four I/O software layers is each of the following done.(a) Computing the track, sector, and head for a disk read. (b) Writing commands to the device registers. (c) Checking to see if the user is permitted to use the device. (d) Converting binary integers to ASCII for printing.(a) Device driver; (b) Device driver; (c) Device-independent software;
(d) User-level software. - 44RAID level 3 is able to correct single-bit errors using only one parity drive. What is the point of RAID level 2? After all, it also can only correct one error and takes more drives to do so.RAID level 2 can not only recover from crashed drives, but also from
undetected transient errors. If one drive delivers a single bad bit, RAID
level 2 will correct this, but RAID level 3 will not. - 45f a disk controller writes the bytes it receives from the disk to memory as fast as it receives them, with no internal buffering, is interleaving conceivably useful? Discuss.Possibly. If most files are stored in logically consecutive sectors, it might
be worthwhile interleaving the sectors to give programs time to process
the data just received, so that when the next request is issued, the disk
would be in the right place. Whether this is worth the trouble depends
strongly on the kind of programs run and how uniform their behavior is. - 46A disk manufacturer has two 5.25-inch disks that each have 10,000 cylinders. The newer one has double the linear recording density of the older one. Which disk properties are better on the newer drive and which are the same?The drive capacity and transfer rates are doubled. The seek time and
average rotational delay are the same. - 47Disk requests come in to the disk driver for cylinders 10, 22, 20, 2, 40, 6, and 38, in that order. A seek takes 6 msec per cylinder moved. How much seek time is needed for (a) First-Come, first served. (b) Closest cylinder next. (c) Elevator algorithm (initially moving upward). In all cases, the arm is initially at cylinder 20.(a) 10 + 12 + 2 + 18 + 38 + 34 + 32 = 146 cylinders = 876 msec.
(b) 0 + 2 + 12 + 4 + 4 + 36 +2 = 60 cylinders = 360 msec.
(c) 0 + 2 + 16 + 2 + 30 + 4 + 4 = 58 cylinders = 348 msec. - 48A slight modification of the elevator algorithm is to always scan in the same direction, In what respect is this modified algorithm better than the elevator algorithm?In the worst case, a read/write request is not serviced for almost two full
disk scans in the elevator algorithm, while it is at most one full disk scan in
the modified algorithm. - 49In the discussion of stable storage using nonvolatile RAM, the following point was glossed over. What happens if the stable write completes but a crash occurs before the operating system can write an invalid block number in the nonvolatile RAM? Does this race condition ruin the abstraction of stable storage? Explain your answer.There is a race but it does not matter. Since the stable write itself has
already completed, the fact that the nonvolatile RAM has not been
updated just means that the recovery program will know which block was
being written. It will read both copies. Finding them identical, it will change
neither, which is the correct action. The effect of the crash just before the
nonvolatile RAM was updated just means the recovery program will have
to make two disk reads more than it should. - 50The clock interrupt handler on a certain computer requires 2 msec (including process switching overhead) per clock tick. The clock runs at 60 Hz. What fraction of the CPU is devoted to the clock?The interrupt occurs 60 times/sec, taking 120 msec/sec = 120/1000 =
12% of the CPU. - 51A system simulates multiple clocks by chaining all pending clock requests together as shown in Fig. 5.33. Suppose the current time is 5000 and there are pending clock requests for time 5008, 5012, 5015, 5029 and 5037. Show the values of the clock header, current time and next signal at times 5000, 5005, and 5013. Suppose a new (pending) signal arrives at time 5017 for 5033. Show the values of clock header, current time and next signal at time 5023.At time 5000:
Current time = 5000; Next Signal = 8; Header → 8 → 4 → 3 → 14 → 8.
At time 5005:
Current time = 5005; Next Signal = 3; Header → 8 → 4 → 3 → 14 → 8.
At time 5013:
Current time = 5013; Next Signal = 2; Header 3 → 14 → 8.
At time 5023:
Current time = 5023; Next Signal = 6; Header → 14 → 4 → 4. - 52Assuming that it takes 10 nsec to copy a byte, how much time does it take to completely rewrite the screen of an 80 character × 25 line text mode memory-mapped screen? What about a 1024 × 768 pixel graphics screen with 24-bit color?Rewriting the text screen requires copying 2,000 bytes, which can be
done in 20 μsec.
Rewriting the graphics screen requires copying 1024×768×3 = 2,359,296
bytes, or about 23.6 msec. - 53A SLIM terminal is used to display a Web page containing an animated cartoon of size 400 pixels × 160 pixels running at 10 frames/sec. What fraction of a 100-Mbps Fast Ethernet is consumed by displaying the cartoon?Each pixel is represented by 24-bits = 3 bytes. So, the display size is 400
× 160 × 3 bytes = 192,000 bytes. At 10 fps this is 1,920,000 bytes/sec or
15,360,000 bits/sec. This consumes 15,360,000/100,000,000 = 15%
(approx.) of the Fast Ethernet. - 54It has been observed that the SLIM system works well with a 1-Mbps network in a test. Are any problems likely in a multiuser situation? Hint: Consider a large number of users watching a scheduled TV show and the same number of users browsing the World Wide Web.The bandwidth on a network segment is shared, so 100 users requesting
different data simultaneously on a 1-Mbps network will each see a 10-
Kbps effective speed.
With a shared network, a TV program can be multicast, so the video
packets are only broadcast once, no matter how many users there are
and it should work well. With 100 users browsing the Web, each user will
get 1/100 of the bandwidth, so performance may degrade very quickly. - 55Systems that support sequential files always have an operation to rewind files. Do systems that support random access files need this too?No. We can access any part of a random access file within a constant
time no matter where the part is located. So, we can simply request to
access byte 0 of the file. - 56Some operating systems provide a system call rename to give a file a new name. Is there any difference at all between using this call to rename a file, and just copying the file to a new file with the new name, followed by deleting the old one?Yes. The rename call does not change the creation time or the time of
last modification, but creating a new file causes it to get the current time
as both the creation time and the time of last modification. Also, if the disk
is full, the copy might fail. - 57A simple operating system only supports a single directory but allows that directory to have arbitrarily many files with arbitrarily long file names. Can something approximating a hierarchical file system be simulated? How?Use file names such as /usr/ast/file. While it looks like a hierarchical path
name, it is really just a single name containing embedded slashes. - 58Consider the directory tree of Fig 6-10. If /usr/jim is the working directory, what is the absolute path name for the file whose relative path name is ../ast/x?The dotdot component moves the search to /usr, so ../ast puts it in
/usr/ast. Thus ../ast/x is the same as /usr/ast/x. - 59Contiguous allocation of files leads to disk fragmentation, as mentioned in the text, because some space in the last disk block will be wasted in files whose length is not an integral number of blocks. Is this internal fragmentation or external fragmentation? Make an analogy with something discussed in the previous chapter.Since the wasted storage is between the allocation units (files), not inside
them, this is external fragmentation. It is precisely analogous to the
external fragmentation of main memory that occurs with a swapping
system or a system using pure segmentation. - 60One way to use contiguous allocation of the disk and not suffer from holes is to compact the disk every time a file is removed. Since all files are contiguous, copying a file requires a seek and rotational delay to read the file, followed by the transfer at full speed. Writing the file back requires the same work. Assuming a seek time of 5 msec, a rotational delay of 4 msec, a transfer rate of 8 MB/sec, and an average file size of 8 KB, how long does it take to read a file into mainmemory then write it hack to the disk at a new location? Using these numbers, how long would it take to compact half of a 16-GB disk?It takes 9 msec to start the transfer. To read 8 KB = 2 13 bytes at a transfer
rate of 8 MB/sec = 2 23 bytes/sec requires 2 −10 sec = 0.977 msec, for a
total of 9.977 msec. Writing it back takes another 9.977 msec. Thus
copying a file takes 19.954 msec.
To compact half of a 16-GB disk would involve copying 8 GB of storage,
which is 8 GB / 8 KB = 2 20 files. At 19.954 msec per file, this takes 20,923
sec = 5.8 hours.
Clearly, compacting the disk after every file removal is not a great idea. - 61In light of the answer to the previous question, does compacting the disk ever make any sense?If done right, yes. While compacting, each file should be organized so that
all of its blocks are consecutive, for fast access. Windows has a program
that defragments and reorganizes the disk. Users are encouraged to run it
periodically to improve system performance. But given how long it takes,
running once a week or even month might be a good frequency. - 62Some digital consumer devices need to store data, for example as files. Name a modern device that requires file storage and for which contiguous allocation would be a fine idea.A digital still camera records some number of photographs in sequence
on a nonvolatile storage medium (e.g., flash memory). When the camera
is reset, the medium is emptied. Thereafter, pictures are recorded one at
a time in sequence until the medium is full, at which time they are
uploaded to a hard disk. For this application, a contiguous file system
inside the camera (e.g., on the picture storage medium) is ideal. - 63Consider the i-node shown in Fig. 6-15. If it contains 10 direct addresses of 4 bytes each and all disk blocks are 1024 KB, what is the largest possible file?The indirect block can hold 256 disk addresses. Together with the 10
direct disk addresses, the maximum file has 266 blocks. Since each block
is 1 KB, the largest file is 266 KB. - 64Free disk space can be kept track of using a free list or a bitmap. Disk addresses require D bits. For a disk with B blocks, F of which are free, state the condition under which the free list usesless space than the bitmap. For D having the value 16 bits, express your answer as a percentage of the disk space that must be free.The bitmap requires B bits. The free list requires DF bits. The free list
requires fewer bits if DF < B. Alternatively, the free list is shorter if F/B <
1/D, where F/B is the fraction of blocks free. For 16-bit disk addresses, the
free list is shorter if 6 percent or less of the disk is free. - 65Consider Fig. 6-26. Is it possible that for some particular block number the counter in both lists have the value 2? How should this problem be corrected?It should not happen, but due to a bug somewhere it could happen. It
means that some block occurs in two files and also twice in the free list.
The first step in repairing the error is to remove both copies from the free
list. Next a free block has to be acquired and the contents of the sick block
copied there. Finally, the occurrence of the block in one of the files should
be changed to refer to the newly acquired copy of the block. At this point
the system is once again consistent. - 66Consider the idea behind Fig. 6-20, but now for a disk with a mean seek time of 8 msec, a rotational rate of 15,000 rpm, and 262,144 bytes per track. What are the data rates for block sizes of 1 KB, 2 KB, and 4 KB, respectively?At 15,000 rpm, the disk takes 4 msec to go around once. The average
access time (in msec) to read k bytes is then 8 + 4/2 + (k /262144) × 4.
For blocks of 1 KB, 2 KB, and 4 KB, the access times are 10.015625
msec, 10.03125 msec, and 10.0625 msec, respectively (hardly any
different).
These give rates of about 102,240 KB/sec, 204,162 KB/sec, and 407,056
KB/sec, respectively. - 67How many disk operations are needed to fetch the i-node for the file /usr/ast/courses/os/handout.t? Assume that the i-node for this root directory is in memory, but nothing else along the path is in memory. Also assume that all directories fit in one disk block.directory for /
i-node for /usr
directory for /usr
i-node for /usr/ast
directory for /usr/ast
i-node for /usr/ast/courses
directory for /usr/ast/courses
i-node for /usr/ast/courses/os
directory for /usr/ast/courses/os
i-node for /usr/ast/courses/os/handout.t
In total, 10 disk reads are required. - 68Secret-key cryptography is more efficient than public-key cryptography, but requires the sender and receiver to agree on a key in advance. Suppose that the sender and receiver have never met, but there exists a trusted third party that shares a secret key with the sender and also shares a (different) secret key with the receiver. How can the sender and receiver establish a new shared secret key under these circumstances?The sender picks a random key and sends it to the trusted third party
encrypted with the secret key that they share. The trusted third party then
decrypts the random key and re-encrypts it with the secret key it shares
with the receiver. This message is then sent to the receiver. - 69Two different protection mechanisms that we have discussed are capabilities and access control lists. For each of the following protection problems, tell which of these mechanisms can be used. (a) Ken wants his files readable by everyone except his office mate. (b) Mitch and Steve want to share some secret files. (c) Linda wants some of her files to be public.To make a file readable by everyone except one person, access control
lists are the only possibility. For sharing private files, access control lists
or capabilities can be used. To make files public, access control lists are
easiest but it may also be possible to put a capability for the file or files in
a well-known place in a capability system. - 70Represent the ownerships and permissions shown in this UNIX directory listing as a protection matrix. Note: asw is a member of two groups: users and devel; gmw is a member of only users. Treat each of the two users and two groups as a domain, so the matrix has four rows (one per domain) and four columns (one per file). -rw-r—r-- 2 gmw users 908 May 26 16:45 PPP-Notes -rwxr-xr-x 1 asw devel 432 May 13 12:35 prog1 -rw-rw---- 1 asw users 50094 May 30 17:51 project.t-rw-r----- 1 asw devel 13124 May 31 14:30 splash.gifDomains
Objects
PPP-notes prog1
project.t splash.gif
gmw Read
Write Read
Execute Read
Write
asw Read Read
Write
Execute Read
Write
users Read Read
Execute Read
Write
devel Read Read
Execute
Read
Write
Read - 71Not having the computer echo the password is safer than having it echo an asterisk for each character typed since the latter discloses the password length to anyone nearby who can see the screen. Assuming that passwords consist of upper and lower case letters and digits only, and that passwords must be a minimum of five characters and a maximum of eight characters, how much safer is not displaying anything?It depends on how long the password is. The alphabet from which
passwords is built has 26 (uppercase letters) + 26 (lowercase letters) + 10
(digits) = 62 symbols. The total search space is 62 5 (5-character long) +
62 6 (6-character long) + 62 7 (7-character long) + 62 8 (8-character long),
which is about 2 × 10 14 .
If the password is known to be k characters, the search space is reduced
to only 62 k . The ratio of these is thus 2 × 10 14 / 62 k . For k from 5 to 8,
these values are 242235, 3907, 63, and 1. In other words, learning that
the password is only five characters reduces the search space by a factor
of 242235 because all the long passwords do not have to be tried.
This is a big win. However, learning that it is eight characters does not
help much because it means that all the short (easy) passwords can be
skipped. - 72The Morris-Thompson protection scheme with the n-bit random numbers (salt) was designed to make it difficult for an intruder to discover a large number of passwords by encrypting common strings in advance. Does the scheme also offer protection against a student user who is trying to guess the superuser password on his machine? Assume the password file is available for reading.No, it does not. The student can easily find out what the random number
for his superuser is. This information is in the password file unencrypted. If
it is 0003, for example, then he just tries encrypting potential passwords
as Susan0003, Boston0003, IBMPC0003, and so on. If another user has
password Boston0004, he will not discover it, however. - 73Suppose the password file of a system is available to a cracker. How much extra time does the cracker need to crack all passwords if the system is using the Morris-Thompson protection scheme with n-bit salt versus if the system is not using this scheme?Suppose there are m users in the systems. The cracker can then collect
the m salt values, assumed all different here. The cracker will have to try
encrypting each guessed password m times, once with each of the m
salts used by the system. Thus the cracker’s time to crack all passwords
is increased m-fold. - 74Can the Trojan horse attack work in a system protected by capabilities?If the capabilities are used to make it possible to have small protection
domains, no; otherwise yes.
If an editor, for example, is started up with only the capabilities for the file
to be edited and its scratch file, then no matter what tricks are lurking
inside the editor, all it can do is read those two files.
On the other hand, if the editor can access all of the user’s objects, then
Trojan horses can do their dirty work, capabilities or not. - 75Often one sees the following in instructions for recovering from a virus attack: 1. Boot the infected system. 2. Back up all files to an external medium. 3. Run fdisk to format the disk. 4. Reinstall the operating system from the original CD-ROM. 5. Reload the files from the external medium. Name two serious errors in these instructions.First, running the fdisk program from the hard disk is a mistake. It may be
infected and it may infect the boot sector. It has to be run from the original
CD-ROM or a write-protected floppy disk. Second, the restored files may
be infected. Putting them back without cleaning them may just reinstall the
virus. - 76—
Informações
- Descrição
- FlashCards sobre 3046, criado por 280742332 em 22-06-2015.
- Criado por
- 280742332
- Visualizações
- 2
- Avaliação