Does anyone have the answers for Fall 2016 midterm?
Some of this is for the final, be sure to focus on the midterm chapters
you may bring to the midterm ONE 8.5×11-inch page of notes (double sided)
you may bring to the final TWO 8.5×11-inch pages of notes (double sided)
You can print double-sided at the library.
⅓ of the final will be material from the midterm.
READ BELOW FIRST
Alright guys, I know we all need this google doc big time… We can all help each
other out so if you know something that is missing or an answer is
incorrect/incomplete please help by adding to the googledoc. Top half is the old
midterm material, bottom half will be new, final material. Like before, the first
section of the final material is going to be all the exercise questions from his
lecture notes, next section is all the problems from the book he told us to study
(not in his notes), next section will be topics mentioned but not in any of the
problems or exercises. Below, we also would like to have all the correct answers
for the midterm so if you got a question correct please fill in that area. If you have
any questions about something, write underneath the specific topic/exercise you
are asking about in a DIFFERENT FONT so that someone can answer your
question and not get mixed up. Also, please leave notes if you believe a problem
may be wrong!!
EX:
(random exercise question here)
Type your question here like this
Someone can respond underneath like this.
~~~Final advice from email as of 12/9/2015~~~
Approximately 1/3 of the final will draw from pre-midterm material, so the advice on
rohan in ~cs570/midterm_advice is still relevant. You will likely be asked to deal with
code that needs critical regions, semaphores, etc., and have to do some calculations
to compute things like page frame size, address sizes, virtual to physical address
translation, etc.
Most of the relevant material is in the xeroxed notes, which matches Tanenbaum’s
exposition EXCEPT for flash memory, the GPT and UEFI lecture material, and the
explanation about how rohan uses the log-structured filesystem to create efficient
hourly backups (in my Chapter 4 notes). These ‘EXCEPTional’ topics are in my notes,
but not in Tanenbaum — so study my notes carefully.
Approximately 2/3 of the final will be ‘new’ material that was not covered on the
midterm. Here is a summary of the relevant pages in Tanenbaum that correspond to
our lectures:
Chapter 1: pages 1-59 Midterm 1
Chapter 2: pages 83-158, 169-170 Midterm 1
Chapter 6: page 462 Midterm 1 Midterm 1
Chapter 3: pages 175-216, plus some highlights from the remaining sections
Midterm1
Chapter 4: pages 255-268, 273-286, 311-317
Chapter 5: pages 329-343, 360-363, 367-373, 376-379, 382-384, 388-406
Chapter 10: p 731-802 (you can ignore the stuff that the lecture notes skip; Midterm1
for example, we did not discuss ZONES on page 763, the diagram on page 765, etc.)
CS570 Midterm1 Exercises
Dr. Carroll Ch.1 ——————————
1.
Interrupt:Signal to processor emitted by hardware indicating an event that needs
immediate attention
Interrupt Handler: Function that deals with the specific event
Interrupt Vector: Look up table that associates specific interrupt handler.
Interrupt – The alert to the processor that a high priority condition has been met and the current
code being processed is to be interrupted. The interrupt handler is the callback function
executed after an interrupt. The memory location of the interrupt handler is called the interrupt
vector. Depending on what specific location on the interrupt vector is specified, different handler
functions are called.
2. Privileged Instructions:
Privileged machine instructions – instructions that can only be ran on kernel mode (not user
mode) which deal with important things such as state vectors, load/save protected memory, and
initiating i/o
.
3. What is a system call?
How a program requests a service from the operating system’s kernel. Accessing
hardware space and creation/execution of new processes.
4. pwd -> /home/ma/570.01/masc00XX
5. A disk contains 2 surfaces, 48 tracks each, with 16 sectors. Each sector contains 512
bytes. How many bytes can be on the disk?
2 * 48 * 16 * 512 = 786432b = 786Kb
6. Speed of light in a vacuum is almost exactly 300,000 kilometers/second. How far can
light travel in 1 nanosecond?
300,000 * (1×10^-9) * 1000 = .3m = 30cm
7. Where is the tr command? (not sure what he means ‘where’)
copies stdin to stdout with the substitution or deletion of selected characters.
ex: echo “the geek stuff” | tr -d ‘t’
he geek suff
/usr/bin/tr is where it is located
tr is a shell commands, therefore it must be executed from within the shell
the compiler is NOT a shell command
(think trim – translate??)
I believe that tr is a binary, so it would be found in the /usr/bin/ folder (similar to where vi
and echo are)
8. When you log onto your student account, which shell are you using?
Tcsh
9. Determine the full path of the gcc?
which gcc -> /opt/local/bin/gcc; usr/bin/gcc for me
10. How do you arrange for your normal human-readable name to be associated with
your student account?
passwd -f
11. p1: getword.o p1.o
gcc -o p1 getword.o p1.o
What does this do?
-checks date of p1 and getword file and if it’s older than any of the files listed, it runs the
command on the next line (more precisely, all the tab-indented lines that follow, up until
the next un-indented line)
12. What does gcc -o p1 getword.o p1.o do?
gcc is front end of the processor, compiler, and linker. Linker is called to form executable
a.out file from the provided object files.
13. What files does p1.o depend on? p1.o: getword.h
Explicitly, if the contents of getword.h changes, contents on left side of colon get
remade.
Implicitly, dependency of p1.o on p1.c
15. p1.c uses the constant named STORAGE, but this is not mentioned in any of the c
files. Where does this value come from?
Value is defined in header file as a macro (single instruction that automatically expands
into a set of instructions)
Dr. Carroll Chapter 2———————-
1. Which process or processes does a Context switch?–
A context switch is changing states of a process or thread which can only be done when a
process in kernel mode is exiting.
2. What happens if kernel is handling a System Call and another system call occurs?
System calls cannot be made in kernel mode so there can never be an instance where there is
a system call on top of another with one processor.
3. a) Why any code below execvp call is often never reached?
Once execvp is performed, the child process’ data and code is replaces what was in the calling
process unless execvp fails. In other words, if execvp doesn’t fail, any code written underneath
the execvp call never gets run.
b) Why is it important to have an exit() call?
Using exit is desired because all buffers are flushed and all open streams are closed.
4) Why does “before fork” get printed twice even though it is written before the fork()
takes place (seems like child process should not print that)?
If buffer is not full for the parent process (which it definitely won’t in this case), text will be stored
in the buffer unless fflush() is used or program exits. So in this case, the child process still
carries a buffer with the words “before fork” in it from its parent.
5. a)What are the exact steps a shell interpreter does when using pipes?
1. Create a pipe
2. Fork a child
3. Child then redirect stdin/out as needed to adjacent pipe end. Then close pipe file
descriptors, then execute given command for the child.
4. Fork a child and repeat steps from step 3.
5. Repeat steps 3 & 4 for each additional pipe (2 or more pipes)
6. After, close pipe file descriptors for parent.
b) What would happen if children did not close its access to the pipe?
If pipes are not closed, EOF would never be reached, therefore would not terminate, unless the
shell interpreter was terminated.
Not 100% sure about my answer for the question below, but I think its right.
6. How does the interrupt handler determine what type of interrupt has brought it to life?
The memory location of the interrupt handler is called the interrupt vector. Depending on what
specific location on the interrupt vector is specified, different handler functions are called.
7. a) How would the average turnaround time compare from First Come First Serve to a
Round Robin algorithm of scheduling?
n = number of jobs
t = turnaround time for 1 job
Average Turnaround Time: FCFS = (n+1)*t/2 vs. RR = n*t
b) How would their average waiting time compare?
Waiting time is twice for RR than FCFS.
Not sure about this one below
8. a) In UNIX CPU scheduling environment, what things cause a process to be promoted
to a higher priority? Priority – Context switches can make it slow. The following 3 times are
considered: Throughput (jobs/hour),Turnaround time(average time for job to finish), Response
time(time from issuing a command and getting a result. Relatively low recent activities cause a
ps to be promoted and vice versa.
a) process’s history record determines if a process will be given a higher or lower priority .
b) Processes start with an “average” priority, which adjusted based on past behavior. If the
process has recently used a lot of CPU, the priority decreases, else it slowly goes up.
c) The ‘w’ command: w -u
”
FOR 11-12 Refer to figure 2-28 page 130/131 tanenbaum “Consumer Producer”
11. What if the 2 down(&mutex) and down (& empty) calls are interchanged in producer,
that is down mutex is move in front of down empty?
Switching the order of the 2 downs in the consumer-producer does make a difference in the
scenario where the buffers are all full. This is because if the producer is now waiting for access
to the critical region in order to produce something, however the consumer might be
waiting for the producer to produce something creating deadlock.
12. What if the two up(&mutex) and up(& empty) calls are switched in consumer?
Switching these can still cause problems because you must ensure no other thread is in the
critical area at the same time. down(mutex) must be done first.
j13. What the fuck is a futex?
Fast User Space Mutex
this is like a mutex but implements a wait queue in the kernel for multiple processes. This helps
not have to switch to kernel mode unless necessary and also getting rid of spin lock and
unnecessary cpu cycles. No switches are required if there is no contention for the mutex being
addressed.
15. Whats wrong with the code?
I dont know if there are additional errors, but definitely a call to down(mutex) before the
up(chopstick) calls and an up(mutex) must be called right after.
eating() isn’t called inside the critical region, which means that everyone can show eating even if
they don’t have chopsticks, right?
Refere to figure 2.46 page 166/177
17. Switching down(s[i]) and up(mutex)?
This causes problems because the mutex for the chopsticks is blocked so no one can ever put
their chopsticks back, creating deadlock.bn
Deadlock – If a process needs both resources to continue, if one process has one resource and
another process has the second resource, this will create a deadlock.
Dr. Carroll CH. 3———————–
Can someone please post how to get the answers to #2 from page 82
from the lecture notes.
2. Suppose our logical addreses are 48 bits with the low end dedicated to a 12 bit page offset
a. page size is 4KB cause 2^12
b. 64G pages needed to map the entire virtual space cause 2^(48-12)
c. 8Kframes is the number of page frames if only bought 32MB of physical memory
d. 512GBytes of table is needed to map all virtual memory if page entries are 64 bits long
*NOTE: Size of each pages from VA or page frames from PA depends by the offset bit. The
number of either pages or frames is depend on the address bit which can be found by
subtracting by the total bits of VA or PA by the number of offset bits as seen in 2b.
3. Ok watch out everyone, this one’s going to be a big one. We did iiiiiiiit. Pat yourself on the
back. Teamwork! ♥ Good job Camel proud of you ♥
Page trace: 2,3,2,1,5,2,4,5,3,2,5,2
Pages in red are the ones that caused the page fault.
● For FIFO, you need to put the new arrival at the tail, and the least recently used at the
head. On a page fault, you take the head off, and plop in a new tail. (NOW) I don’t know
where you’re getting this head tail stuff see:
https://stackoverflow.com/questions/13834802/how-does-fifo-page-replacement-work
● Page 204. Chapter 3.4.3: “The operating system maintains a list of all pages currently in
memory, with the most recent arrival at the tail and the least recent arrival at the head.
https://stackoverflow.com/questions/13834802/how-does-fifo-page-replacement-work
On a page fault, the page at the head is removed and the new page is added to the tail
of the list.”
● For LRU, you replace the page that hasn’t been used the longest amount of time. (past)
● For Optimal, you replace the page that won’t be used the longest amount of time.
(future)
Here’s another example of FIFO:
Page Optimal LRU FIFO
2 2 2 2
3 23 23 23
2 23 23 23
1 231 231 231
5 235 251 315
2 235 251 152
4
435 254 524
5 435 254 524
3 435 354 243
2 235 352 243
5 235 352 435
2 235 352 352
4. 125 revolutions/s and 500,000bps. I have no idea why this is here.
a) Avg seek time in microseconds: 0
b) Avg rotational latency: 4000 microseconds = 0.5rev*(1s/125rev)*(106microsec/1s)
c) (a) + (b) * ((500b/page)/(500000b/s))*(106microsec/1s) = 5000 microseconds
6. a) What are the disadvantages to an extremely small page size?
b) What are the disadvantages to an extremely large page size?
7. a) What is the precise hardware situation that triggers a page fault?
Type of interrupt called a trap, raised by the hardware when a running program access a
memory page that is mapped to the virtual address space, but not actually loaded into memory.
b) What is the difference between the Present bit and the Modify Bit?
Present bit – Indicate which pages are currently present in physical memory or on
disk, and how to treat these pages.
Modify Bit – If the page was written to after it was paged in, the modify (or dirty)
bit will be changed, indicating the page must be written back to
c.) What is the Translation Lookaside Buffer, and what problem is it designed to solve?
The TLB is a small hardware device for mapping virtual address to physical
addresses without going through a page table (reduces the amount of page referencing)
8.)
a.) FIFO page replacement - OS maintains list of pages in memory with most recent
arrival at tail, and least recent at head. on a page fault, the page at the head is removed and the
new page is added to the tail. This paging algorithm is rarely used.
b.) LRU(Least Recently Used) - When a page fault occurs, throw out the page that has
been unused for the longest time. Needs special hardware for implementation.
Answers for Carroll’s recomended problems from tanenmbaum 3rd edition (not from lecture
notes):
http://www.comsizo.com.br/resolucoes/SistemasOperacionais_-_Tanenbaum_-_3Ed_Solution.p
df
^^^ links is broken……..
Hey boo, I found a new one:
http://download1.pearsoned.de/download/download.aspx?FileID=%7B0F3CA1CC-D955-483E-
AA0B-6D841CCEF85B%7D
Tanenbaum CHAPTER 1 ——————–
1.- What is Multiprogramming?
Multiprogramming is the rapid switching of the CPU between multiple processes in
memory. It is commonly used to keep the CPU busy while one or more processes are doing I/O.
2.- What is spooling? Do you think that advanced personal computers will have spooling
as a standard feature?
1. Input spooling is the technique of reading in jobs, for example, from cards, onto
the disk, so that when the currently executing processes are finished, there will
http://www.comsizo.com.br/resolucoes/SistemasOperacionais_-_Tanenbaum_-_3Ed_Solution.pdf
http://www.comsizo.com.br/resolucoes/SistemasOperacionais_-_Tanenbaum_-_3Ed_Solution.pdf
http://download1.pearsoned.de/download/download.aspx?FileID=%7B0F3CA1CC-D955-483E-AA0B-6D841CCEF85B%7D
http://download1.pearsoned.de/download/download.aspx?FileID=%7B0F3CA1CC-D955-483E-AA0B-6D841CCEF85B%7D
be work waiting for the CPU. Output spooling consists of first copying printable
files to disk before printing them, rather than printing directly as the output is
generated. Input spooling on a personal computer is not very likely, but output
spooling is.
Better Answer:
SPOOLING is a type of buffering that is used to compensate for the speed mismatch
between a device and a processor. Spooling means putting jobs in a buffer ( a special area in
memory) or on a disk where a device can access them when it is ready.
A good example of spooling is printing spooling – documents are loaded into a buffer,
and then the printer pulls them off the buffer at its own rate. Since the documents are already
loaded into the buffer, now the CPU can perform other operations while the printing takes place
in the background.
Advanced personal computers still have spooling as a standard feature. As an example:
spooling is currently used as temporary storage area to which email is delivered by a Mail
Transfer Agent and in which it waits to be picked up by a Mail User Agent. This is called mail
spool.
3.- On 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 to give the CPU something to do while waiting
for I/O to complete. If there is no DMA, the CPU is fully occupied doing I/O, so there is nothing
to be gained (at least in terms of CPU utilization) by multiprogramming. No matter how much I/O
a program does, the CPU will be 100% busy. This of course assumes the major delay is the wait
while data are copied. A CPU could do other work if the I/O were slow for other reasons (arriving
on a serial line, for instance).
4.- The family of computers idea was introduced in the 1960s with the IBM System/360
mainframes. Is this idea now dead as a doornail or does it live on?
It is still alive. For example, Intel makes Pentium I, II, and III, and 4 CPUs with a variety
of different properties including speed and power consumption. All of these machines are
architecturally compatible. They differ only in price and performance, which is the essence of
the family idea
8.- Consider a system that has two CPUs and each CPU has two threads
(hyperthreading). Suppose three programs, P0, P1, and P2, are started with run times of
5, 10 and 20 mses, respectively. How long will it take to complete the execution of these
programs? Assume that all three programs are 100% CPU bound, do not block during
execution, and do not change CPUs once assigned.
It may take 20, 25 or 30 msec to complete the execution of these programs depending
on how the operating system schedules them. If P0 and P1 are scheduled on the same CPU
and P2 is scheduled on the other CPU, it will take 20 mses. If P0 and P2 are scheduled on the
same CPU and P1 is scheduled on the other CPU, it will take 25 msec. If P1 and P2 are
scheduled on the same CPU and P0 is scheduled on the other CPU, it will take 30 msec. If all
three are on the same CPU, it will take 35 msec.
14.- What 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 is run again
and again, the trap will always occur at exactly the same position in the instruction stream. An
interrupt is caused by an external event and its timing is not reproducible.
17.- What is the purpose of a system call in an operating system?
A system call allows a user process to access and execute operating system functions
inside the kernel. User programs use system calls to invoke operating system services.
More details:
A program is limited to its own address space so that it cannot access or modify other
running programs or the OS itself. However, accessing other parts of memory or performing
modifications are often essential for programs (for example a disk defrag software accessing a
hard disk drive). This is when system call comes in place. System calls are made available by
the operating system to provide well defined, safe implementations for such operations.
18.- For 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 (and possibly if there is no
memory or swap space left). 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.
19.- Can the
count = write(fd, buffer, nbytes);
call return any value in count other than nbytes? If so, why?
If the call fails, for example 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 nbytes.
22.- What 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 be read or written
independently of all the other ones. It is possible to seek to any block and start reading or
writing. This is not possible with character special files.
30.- Write a shell that is similar to Fig. 1-19 (Page 54) but contains enough code that it
actually works so you can test it. You might also add some features such as redirection
of input and output, pipes, and background jobs.
Tanenbaum CHAPTER 2
1.- In Fig. 2-2 (Page 90), 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. Suppose that a process is
blocked on I/O and the I/O finishes. If the CPU is otherwise idle, the process could go directly
from blocked to running. The other missing transition, from ready to blocked, is impossible. A
ready process cannot do I/O or anything else that might block it. Only a running process can
block.
3.- On all current computers, at least part of the interrupt handlers are written in
assembly language. Why?
Generally, high-level languages do not allow the kind of access to CPU hardware that is
required. For instance, an interrupt handler may be required to enable and disable the interrupt
servicing a particular device, or to manipulate data within a process’ stack area. Also, interrupt
service routines must execute as rapidly as possible.
10.- In Fig. 2-12 (Page 102) the register set is listed as a per-thread rather than a
per-process item. Why? After all, the machine has only one set of registers.
When a thread is stopped, it has values in the registers. They must be saved, just as
when the process is stopped the registers must be saved. Multiprogramming threads is no
different than multiprogramming processes, so each thread needs its own register save area.
11.-Why would a thread ever voluntarily give up the CPU by calling thread_yield? After
all, since there is no periodic clock interrupt, it may never get the CPU back.
Threads in a process cooperate. They are not hostile to one another. If yielding is
needed for the good of the application, then a thread will yield. After all, it is usually the same
programmer who writes the code for all of them
23.- Does the busy waiting solution using the turn variable (Fig. 2-23) (Page 122) 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.
45 – In the solution to the dining philosophers problem (Fig. 2-46) (Page 166), why is the
state variable set to HUNGRY in the procedure take_forks?
The change would mean that after a philosopher stopped eating, neither of his neighbors
could be chosen next. In fact, they would never be chosen. Suppose that philosopher 2 finished
eating. He would run test for philosophers 1 and 3, and neither would be started, even though
both were hungry and both forks were available. Similarly, if philosopher 4 finished eating,
philosopher 3 would not be started. Nothing would start him.
46.- Consider the procedure put_forks in Fig. 2-20. Suppose that the variable state[i] was
set to THINKING after the two calls to test, rather than before. How would this change
affect the solution?
If a philosopher blocks, neighbors can later see that she is hungry by checking his state,
in test, so he can be awakened when the forks are available.
47.- The readers and writers problem can be formulated in several ways with regard to
which category of processes can be started when. Carefully describe three different
variations of the problem, each one favoring (or not favoring) some category of
processes. For each variation, specify what happens when a reader or a writer becomes
ready to access the database, and what happens when a process is finished using the
database.
Variation 1: readers have priority. No writer may start when a reader is active. When a
new reader appears, it may start immediately unless a writer is currently active. When a writer
finishes, if readers are waiting, they are all started, regardless of the presence of waiting writers.
Variation 2: Writers have priority. No reader may start when a writer is waiting. When the
last active process finishes, a writer is started, if there is one; otherwise, all the readers (if any)
are started.
Variation 3: symmetric version. When a reader is active, new readers may start
immediately. When a writer finishes, a new writer has priority, if one is waiting. In other words,
once we have started reading, we keep reading until there are no readers left. Similarly, once
we have started writing, all pending writers are allowed to run.
Tanenbaum CHAPTER 3 ————————-
4.- Consider a swapping system in which memory consists of the following hole sizes in
memory order: 10 KB, 4 KB, 20 KB, 18 KB, 7 KB, 9 KB, 12 KB, and 15 KB. Which hole is
taken for successive segment requests of
(a) 12 KB
(b) 10 KB
(c) 9 KB
for first fit? Now repeat the question for best fit, worst fit, and next fit.
First fit takes 20 KB, 10 KB, 18 KB.
Best fit takes 12 KB, 10 KB, and 9 KB.
Worst fit takes 20 KB, 18 KB, and 15 KB.
Next fit takes 20 KB, 18 KB, and 9 KB.
12.- A computer with a 32-bit address uses a two-level page table. Virtual addresses are
split into a 9-bit top-level page table field, an 11-bit second-level page table field, and an
offset. How large are the pages and how many are there in the address space?
Twenty bits are used for the virtual page numbers, leaving 12 over for the offset. This
yields a 4-KB page. Twenty bits for the virtual page implies 2^20 pages.
13.- Suppose that a 32-bit virtual address is broken up into four fields, a, b, c, and d. The
first three are used for a three-level page table system. The fourth field, d, is the offset.
Does the number of pages depend on the sizes of all four fields? If not, which ones
matter and which ones do not?
The number of pages depends on the total number of bits in a, b, and c combined. How
they are split among the fields does not matter.
This answer might be more accurate:
The number of pages does not depend on the sizes of all four fields.
Field d (page size) matters the most because it will determine the total number of pages.
If d is large then the number of pages will be less vice versa.
15.- A computer whose processes have 1024 pages in their address spaces keeps its
page tables in memory. The overhead required for reading a word from the page table is
5 nsec. To reduce this overhead, the computer has a TLB, which holds 32 (virtual page,
physical page frame) pairs, and can do a look up in 1 nsec. What hit rate is needed to
reduce the mean overhead to 2 nsec?
The effective instruction time is 1h + 5(1 − h), where h is the hit rate. If we equate this
formula with 2 and solve for h, we find that h must be at least 0.75.
18.- A 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).
19.- A computer with an 8-K.B page, a 256-KB main memory, and a 64-GB virtual address
space uses an inverted page table to implement its virtual memory. How big should the
hash table be to ensure a mean hash chain length of less than 1? Assume that the hash
table size is a power of two.
The main memory has (2^28) /(2^13) = 32,768 pages. A 32K hash table will have a
mean chain length of 1. To get under 1, we have to go to the next size, 65,536 entries.
Spreading 32,768 entries over 65,536 table slots will give a mean chain length of 0.5, which
ensures fast lookup.
20.-A student in a compiler design course proposes to the professor a project of writing a
compiler that will produce a list of page references that can be used to implement the
optimal page replacement algorithm. Is this possible? Why or why not? Is there anything
that could be done to improve paging efficiency at run time?
This is probably not possible except for the unusual and not very useful case of a
program whose course of execution is completely predictable at compilation time. If a compiler
collects information about the locations in the code of calls to procedures, this information might
be used at link time to rearrange the object code so that procedures were located close to the
code that calls them. This would make it more likely that a procedure would be on the same
page as the calling code. Of course this would not help much for procedures called from many
places in the program.
26.- In the WSClock algorithm of Fig. 3-2l(c), the hand points to a page with R = 0. If ‘t =
400, will this page be removed? What about if “t = 1000?
The age of the page is 2204 − 1213 = 991. If τ = 400, it is definitely out of the working set
and was not recently referenced so it will be evicted. The τ = 1000 situation is different. Now the
page falls within the working set (barely), so it is not removed.
32.- Can a page be in two working sets at the same time? Explain.
If pages can be shared, yes. For example, if two users of a timesharing system are
running the same editor at the same time, and the program text is shared rather than copied,
some of those pages may be in each user’s working set at the same time.
Tanenbaum CHAPTER 6————————–
30.- Cinderella and the Prince are getting divorced. To divide their property, they have
agreed on the following algorithm. Every morning, each one may send a letter to the
other’s lawyer requesting one item of property. Since it takes a day for letters to be
delivered, they have agreed that if both discover that they have requested the same item
on the same day, the next day they will send a letter canceling the request. Among their
property is their dog, Woofer, Woofer’s doghouse, their canary, Tweeter, and Tweeter’s
cage. The animals love their houses, so it has been agreed that any division of property
separating an animal from its house is invalid, requiring the whole division to start over
from scratch. Both Cinderella and the Prince desperately want Woofer. So they can go on
(separate) vacations, each spouse has programmed a personal computer to handle the
negotiation. When they come back from vacation, the computers are still negotiating.
Why? Is deadlock possible? Is starvation possible? Discuss.
If both programs ask for Woofer first, the computers will starve with the endless
sequence: request Woofer, cancel request, request Woofer, cancel request, and so on. If one of
them asks for the doghouse and the other asks for the dog, we have a deadlock, which is
detected by both parties and then broken, but it is just repeated on the next cycle. Either way, if
both computers have been programmed to go after the dog or the doghouse first, either
starvation or deadlock ensues. There is not really much difference between the two here. In
most deadlock problems, starvation does not seem serious because introducing random delays
will usually make it very unlikely. That approach does not work here.
Here is what Carroll wants you to know for the exam from Chapter 6
1) The four conditions for DEADLOCK on page 438/440. ALL of these must be
present for DEADLOCK to occur.
a) Mutual exclusion condition. Each resources is either currently assigned
to exactly one process, or is available.
b) Hold and wait condition. Processes currently holding resources that
were granted earlier can request new resources.
c) No preemption available. Resources previously granted cannot be
forcibly taken away from a process. They must be explicitly released by
the process holding them.
d) Circular wait Condition. There must be a circular chain of two or more
processes, each of which is waiting for a resource held by the next
member of the chain.
2) Understand the summary for chapter 6.9 on Page 462/464. Ignore the second
paragraph because it’s not good.
Summary 6.9
Deadlock is a potential problem in any operating system. It occurs when all
the members of a set of processes are blocked waiting for an event that only other
members of the set can cause. This situation causes all the processes to wait forever.
Commonly the event that the processes are waiting for is the release of
some resource held by another member of the set. Another situation in which
deadlock is possible is when a set of communicating processes are all waiting for
a message and the communication channel is empty and no timeouts are pending.
Resource deadlock can be avoided by keeping track of which states are safe
and which are unsafe. A safe state is one in which there exists a sequence of
events that guarantee that all processes can finish. An unsafe state has no such
guarantee. The banker’s algorithm avoids deadlock by not granting a request if
that request will put the system in an unsafe state.
Resource deadlock can be structurally prevented by building the system in
such a way that it can never occur by design. For example, by allowing a process
to hold only one resource at any instant the circular wait condition required for
deadlock is broken. Resource deadlock can also be prevented by numbering all
the resources, and making processes request them in strictly increasing order.
Resource deadlock is not the only kind of deadlock. Communication deadlock
is also a potential problem in some systems although it can often be handled
by setting appropriate timeouts.
SEC. 6.9 SUMMARY 461
Livelock is similar to deadlock in that it can stop all forward progress, but it is
technically different since it involves processes that are not actually blocked.
Starvation can be avoided by a first-come, first-served allocation policy.
Questions
Anyone know whats up with chapter 6? Is all we need to study of that chapter the
review at the end referring to deadlocks and starvation? That along with problem 30?
Hey boo, see above!
QUESTIONS: FROM MIDTERM1
Would someone be able to answer the question on number 3 and 6 from midterm1
3. In every process entry in the task structure, the PID of the parent is stored why?
When SIGCHILD is returned by a dead child, it can be returned to the correct parent.
6. If the read() call on the next line is successful can
count = read(fd,buffer,nbytes);
return any value in count other than nbytes? Explain
(Note that this is read(), not write().)
(p. 265) When buffer contains less than nbytes it will return fewer than the maximum possible nbytes.
YouTube
Page replacement algorithms
*LRU(least recently used) – https://www.youtube.com/watch?v=I9_BpSXBodU
*FCFS(first come first serve) – https://www.youtube.com/watch?v=4KK0MVFSHeE
*Optimal – https://www.youtube.com/watch?v=XmdgDHhx0fg
*Compilation process –
http://www.tenouk.com/ModuleW_files/ccompilerlinker001.png
1FINAL STUDY GUIDE STARTS HERE
Anyone have the answers to the Exercise problems in
Carroll’s book?
Does anybody have the answers to the midterm?
LECTURE NOTES:
IF YOU ARE MAKING CONTRIBUTIONS PLEASE REFERENCE PAGE OF
LECTURE NOTES OR TANNEBAUM THAT YOU FOUND THE ANSWER SO THAT
USERS CAN GO BACK AND READ MORE IF THEY DON’T UNDERSTAND!!!!!!
Chapter 4 Problems: Exercises 4 (p84)
1. we know that unix systems often partition a physical disk into logical disks,
each with its own file system. When these file systems are mounted we
have a file system hierarchy in which the identity of the individual drives is
essentially invisible. This sounds an awful lot like digging holes in order to
fill them again. Why go to all this trouble (instead of just making one big
partition on the disk)?
(Page 51 Notes) This new little program is then responsible for loading the
operating system associated with this partition. Because they are independent,
different partitions may well have very different file system on them (linux on one
and Windows on another)
http://www.howtogeek.com/184659/beginner-geek-hard-disk-partitions-explained/
http://www.howtogeek.com/184659/beginner-geek-hard-disk-partitions-explained/
Also partitions can hold data which can be unaffected by the other partitions,
therefore creating a safeguard for any corruption or restores on other partitions
Allows multiple OS’s on the computer; reduces chance of losing data due to
partition corruption, since you would lose the whole partition; reduces read/write
time since the heads will need to move and reposition less often.
2. Assume you are logged on to your UNIX account for this class, in which
your home directory and all your subdirectories are on the same disk
partition. Consider what happens when you (successfully) issue the
following UNIX command, which renames a file and simultaneously moves
it to your subdirectory [named save]:
mv ~/.login ~/save/moved.login
a) What (if anything) gets changed in the inode for your home directory ~ ?
(Page 263 Tanenbaum 3rd ed) Time of last access, Time of last change, and
Current size were definitely changed in the inode. Not sure about Record length, Key
position, and Key length but my guess is no to all of them.
If file name is changed(more letters), does the datas length increase?
No, each (filename, inode) pair has a set size.
Times – Figure 10.33 in Tanenbaum Chapter 10. I don’t think size is changed. Mv simply
renames the file and moves it to the new location.
b) What (if anything) gets changed in the data pointed to by inode for your
home directory ~?
Not sure about this answer but my guess is: time of last access is changed to time when
you moved the file, time of last change is changed to time when you moved the file, and
currentsize
Data pointed to is not changed. (Xeroxed note pg. 51, 4.1.6)
c) What (if anything) gets changed in the inode for your .login file?
(Page 263 Tanenbaum 3rd ed) Time of last access and Time of last change.
I thought in class he said that nothing happens in this inode??
d) Does the data pointed to by the inode for your .login file have to be copied
to a new set of blocks?
No, the file gets moved but the inode points to the same data blocks, just the file
itself is at a new location.
e) Suppose, instead, you were to move the file to a directory on a different
disk drive (or a different partition), e.g.
mv ~/.login /tmp/moved.login
Discuss how the answers you gave above would be different.
Not 100% about this answer but seems right…
The answers would be the same as above except the actual inode value could
be different. Each partition holds its own set of inodes and therefore inode
values.
Intro to inodes: http://www.grymoire.com/Unix/Inodes.html
When mv to a different file system partition, a new inode is created.
3. As you know, UNIX maintains a block buffer cache in RAM. However, writes
to blocks that contain directory information are immediately written back to
disks. Why is the efficiency of having a buffer cache forsaken in this
instance?
(Bottom right page 55- top left 56 Notes) Allows multiple OS’s on the computer; reduces
chance of losing data due to partition corruption, since you would lose the whole
partition; reduces read/write time since the heads will need to move and reposition less
often.
I disagree…doesn’t answer the question. The answer is that file system changes
are critical and could corrupt the whole file system if the machine crashes before
a writeback occurs. From Tanenbaum (4th ed) p316
I agree with what you are saying, but I think we are just interpreting differently. I
still think my answer is right because from what I understand, the question is why
is the EFFICIENCY of the cache nullified. This is due to the fact that writes to disk
are very slow and each write which has directory information is going to have to
do this therefore the efficiency of the cache doesn’t even matter. Thoughts?
I think im write and ur rong and i dont care wat u say becuz im rite
If the block is essential to the file-system consistency (basically, everything except data
blocks), and it has been modified, it should be written to disk immediately, regardless of
which end of the LRU list it is put on. By writing critical blocks quickly, we greatly reduce
the probability that a crash will wreck the file system. While a user may be unhappy if
one of his files is ruined in a crash, he is likely to be far more unhappy if the whole file
system is lost.
Carrolls answer …
We write the directory stuff out right away, because this is crucial to
maintaining a consistent filesystem. Having a power failure while there
were some changes that were not already preserved on disk can mean a loss
of data. (E.g., we created a new file, put some info in it, and closed
the file. But if we haven’t written the name/inode pair in the directory
out to disk, then we have an ‘orphan file’ that no one knows the name of.)
4. Suppose that someone noticed that disk reads were proceeding faster
than disk writes on your computer system. What would you say if someone
asked you to explain this phenomenon?
http://www.grymoire.com/Unix/Inodes.html
Hint: You might ask your questioner if the computer system used a buffer
cache system for disk blocks. If the answer were yes, there is an obvious
possible explanation
(Bottom right page 55- top left 56 Notes) Similar to the answer above; a buffer cache
stores recently/frequently used read disk blocks to RAM which is much faster than
accessing the disk. Writes have to access the disk regardless making these much
slower than reads.
5. Suppose that someone noticed that disk writes were proceeding faster
than disk reads on your computer system. What would you say if someone
asked you to explain this phenomenon?
Hint 1: You might ask your questioner about what type of filesystem you
are writing to recall that some schemes were designed to maximize this.
Hint 2: Irrespective of the type of filesystem there is another logical
explanation: the writes aren’t really occurring as fast as the OS reports.
Think of a situation that can happen fairly often with writes, but never with
reads.
(Bottom left Page 54 Notes) If the filesystem is a log-structured file, this produces
slower reads than writes. This is due to the fact that the very high number of
writes is drastically reduced by using a log. Instead of doing multiple writes to a
disk and having to access the disk many times, instead, all these writes are
stored in a log before actually carried out. Then, all at once, a log entry called a
“segment” writes all the different writes to the disk at once… “Reads go slower
because the data is all strung out.”
***Can’t find an answer for the second “logical explanation” to this question
6. In windows, when a user double-clicks on a file listed by Windows
Explorer, a program is run and given that file as a parameter. Things are
done differently in UNIX. List two different ways an operating system could
know which program to run.
Disagree. 2 ways are file extension (as windows uses) and the “magic number”
that are in the first two bytes of most files (unix). (lecture notes p49 4.1.1)
Instead of relying on extensions, UNIX files tend to have a ‘magic number’ in the first
two bytes of most files (postscript files, for example, begin with the ASCII codes for the
characters “!#”……………………)
^^^^^^^^^^^^^^^^^^^^^^I am going to have to agree with purple^^^^^^^^^^^^^^^^^^^^^
I second that… erasing old shit
7. Pits and lands on a mass-produced commercial CD are equally reflective,
and yet your CD-player detects differences in reflected intensity. Explain.
(Page 57 Right-mid Notes ) Pits are about 20 microns closer, which turns out to be ¼ of
the wavelength of infrared laser beam. Laser light is coherent light (all move in lockstep)
so waves that hit pits travel ½ wavelength further. This makes the crest of some waves
coming back to the photosensor match up with the trough of some of the other reflected
waves, causing destructive interference. As a result, less light is seen. The key is the
photosensor detecting the difference in light between the pits and lands that is coming
back to it.rr
8. Discuss the differences between mass-produced commercial CDs, CD-Rs,
and CD-RWs.
pg58(carroll)
CD’s had to be mastered on hugely expensive equipment
CDR’s have a thin chemical layer (near the label, below the reflective coating)
which is transparent until heated by a laser strong enough to “write” on the disk,
the heated dye then becomes permanently dark(write once medium).
CDRW’s fancy alloy is used for reflective surface and no dye is involved. In its
natural state the alloy reflects very well. However if you blast it with a high
powered laser you can heat it up enough so that it reflects poorly. So the
untouched light spot areas are the lands and the amorphous dark spots are the
pits. Cool thing about this alloy is that if you heat it up less violently the structure
will reform and become highly reflective again allowing multiple writes.
9. What is the motivation for using a log-based filesystem?
pg 54(carroll)speed at which you can read data from a disk doesn’t matter very
much, so related data can be spread all over the place without much performance
penalty.
On the other hand, we frequently do a lot of tiny writes in unrelated places. If we make a
new file we have to update things like the list of free inodes, update the disk of free data
blocks, file name inserted into directory and updating inode for directory itself, and the
last modified timestamp of the directory also must be updated.
With a log-structured file system we simply save up these 5 changes along with lots of
other changes into a log. A log entry called a “segment” can execute these writes
contiguously at 100% write efficiency onto the disk.
10. Why is GPT replacing the older IDE partitioning scheme?*
(pg 51 lower-right Notes) MBR partitioning tables can only accommodate drives up to
about 2TB in size using Logical Block Addressing (LBA). New standard can handle
drives in the ZB range (2^73 bytes). Which is a lot of space for dank memes.
11. Describe a few of the capabilities that UEFI(Unified Extensible Firmware
Interface) has that the old BIOS(Basic Input/Output System)does not.
(pg 52 Left-mid Notes) Additional capabilities of UEFI:
a) includes fancy graphics support and other device drivers that awakening OS can
use until it loads its own device drivers.
b) ‘Secure Boot’ capability which can ensure that only ‘acceptable’ OS loaders are
allowed to function.
c) Can be queried over the network after power-on, even if the system has not had
an OS installed on it, allowing remote diagnostics and recovery services.
12. What is meant by ‘virtual layer’ on a flash drive, what is it’s purpose?
pg53(carroll)To get the effect of wear-leveling a virtual layer is added on top of
the flash devices physical layer that tries to even out the wear on the set of blocks. If
you ask to read block #45 you get back what was previously stored in block #45.
However if you write new stuff onto block #45 the on-drive electronics will pick a new
physical page to put the data into and will now remember where this new location is
when you next ask for data block 45. The new block is chosen from a list of “free queue”
and the physical page that held the old data that used to designated for block #45 goes
to the end of the “free queue” list to eventually be used again.
13. What is wear-leveling?
Wear leveling is a technique for prolonging the service life of some kinds of
erasable computer storage media, such as flash memory used in solid-state drives
(SSDs) and USB flash drives. (https://en.wikipedia.org/wiki/Wear_leveling)
When the software attempts to write to a certain block, it is automatically forced
to write somewhere else. The next write is likely to be mapped somewhere yet again.
This is done in a way that is completely invisible to the rest of the world, and results in
all of the blocks in the flash chip receiving roughly the same amount of
Wear.(http://thessdguy.com/how-controllers-maximize-ssd-life-better-wear-leveling/)
14. What is the difference between nand-based and nor-based flash
technology?
pg53(carroll)Nor is used for things like BIOS since only small amounts are
required and is byte addressable meaning you can write a single byte w/o affecting any
other bytes
Nand is page addressable and is therefore a natural fit for file systems. Can
easily turn any particular 1-bit into 0-bit, but only way to turn a 0 into 1 is to erase an
entire page of memory, which turns the entire page into 1’s. So writing a page consists
of first ‘blanking’ it to all 1’s, and then writing individual zeros where you want them.
https://en.wikipedia.org/wiki/Computer_storage
https://en.wikipedia.org/wiki/Computer_storage
15. A flash drive is much faster than an IDE drive; swapping processes in and
out when the CPU is overcrowded can drastically slow down a system. This
would seem to make a flash drive ideal for hosting a swap partition.
However, this is never done (except as perhaps a perverse experiment).
Why is it a bad idea to use a flash drive as a swap partition?
pg53(carroll) flash technology typically stops being reliable after 100,000
erasures. This is a problem for normal file systems where some blocks get used over
and over such as when doing swap partitions. This would tend to “wear” out parts of the
flash drive earlier than other parts. This would be due to the fact that some pages which
contain system binaries and libraries stored might not ever change; rendering the rest of
the blocks of memory used a lot more.
16. a) consider what happens when we make a hard link, in particular,
ln p2.c hard.c
What fields [if any] in the inode for the original p2.c are changed? (Be
specific)
I think he meant to say hard.c since ln by default makes hard links
The number of links (link count) in the inode is incremented by one.
b) Consider what happens when we take a soft link, in particular,
ln -s p2.c soft.c
What fields [if any] in the inode for the original p2.c are changed? (Be
specific)
(Page 50 Notes) No Fields are changed because you simply just create another
Inode containing the same data, not modifying or copying anything.
c) Was an additional new inode needed to create either hard.c or soft.c?
Yes when you make a soft link a new inode is created containing all
the original data. For hard links no, inodes are not created.
d) CARROLL ADDED THIS ON HIS EMAIL why it is impossible to create a
hard link between files on different partitions (you have to use soft links for such
‘shortcuts’ across filesystems). Hint: =each partition has its own set of inodes, so
inode #12345 means something completely different on a different partition.
Here is a really good set of diagrams for x inks and softlinks:
http://linuxgazette.net/105/pitcher.html
http://stackoverflow.com/questions/185899/what-is-the-difference-between-a-sym
bolic-link-and-a-hard-link
Exercises 5 (p85)
http://linuxgazette.net/105/pitcher.html
http://stackoverflow.com/questions/185899/what-is-the-difference-between-a-symbolic-link-and-a-hard-link
http://stackoverflow.com/questions/185899/what-is-the-difference-between-a-symbolic-link-and-a-hard-link
1. For a hard disk that spins at 7200 RPM, what is the average rotational
latency?
7200 RPM / 60 = 120 RPSecond
1/120 = .008333 Sec/Revolution
On average the disk will need to half a rotation to encounter the data we are
looking for average rotational latency = .008333 / 2 = .00417 sec = 4.17ms
2. Explain the problems an ‘old’ CD-ROM drive (one that doesn’t know about
the CD-R format) might have when reading a CD-R disk.
(p58 lower/right) When a CD-R is written a directory for the disk is burned at the
beginning (inner) of the disk. If the CD-R is appended later a new directory will
be created following the original data. Older CD (not R) drives don’t know to look
for a “new” directory after all data contained in the first directory and as such
won’t be able to read any data on the CD-R that was appended after the original
write.
3. What is a soft timer?
(p64 right) A soft timer allows a compromise between the extremes of polling and
interrupts. Essentially, a time ordered list of scheduled event times is
maintained, but the kernel does not rely on clock interrupts to examine this list.
Instead, as part of the ‘cleanup’ duties each time the kernel is about to exit kernel
mode and re-enter user mode, it checks to see if any of these scheduled events
at the top of the list are now ripe, and if so, the event is handled (without the
added /…/.overhead of a switch to kernel mode, since we are already in kernel
mode).
4. How does pipelining and superscalar architecture complicate the
processing of interrupts?
(p61 left-middle) The real complications in handling interrupts comes from the
confusing effects of hardware pipelining, which is doing multiple things
simultaneously…………(see Carroll p61 for details)………once an interrupt finishes
the operating system has a to do a lot of analysis of the state of the machine to
figure out how to begin refilling the pipeline so that the interrupted process restarts
in the correct place. Superscalar architecture makes things infinitely worse.
5. (a) What is memory-mapped I/O
(p59 right-middle) Part of the address space does not refer to bytes of RAM in
the usual way, but instead is mapped to various controller-card registers. In this
scheme writing to some “high” RAM memory address effectively routes data to a
register on some controller.
(Page 59, right side and page 334 3rd ed) Introduced with the PDP11 godlike computer, each
control register is assigned a unique memory address to which no memory is assigned. These
addresses are usually at the top of the address space.These registers are just variables in
memory and can be addressed in C, thus requiring no assembly code to do reads and writes. ♥
(b) How does today’s advanced bus architecture complicate
memory-mapped I/O
(p59 right-middle) On modern systems the CPU and memory have their own high
speed bus and I/O devices cannot ‘see’ the memory references whizzing by on
the high-bandwidth bus, and would be left in the dark unless extra hardware [a
bridge] allows them to ‘see’ the relevant part of memory.
6. What is the difference between scan codes and ASCII codes?
(p65 upper-left) [keyboard signals] …..the byte of information that is
communicated across the port is NOT an ASCII code, but rather a different code
(called a scan code) that specifies a physical key. For example, on the standard
102-key US keyboard, 7 bits are used to encode which of the keys changed
state, and the eighth bit specifies whether is was a key press or a key release.
7. What is the difference between raw and cooked modes?
(p65 lower-left) Many applications do not really want to see every character
typed; for example, you shell would rather wait until a full line is assembled, and
then receive an entire command once
part of a line, erase some characters, type some more, and the shell will never
know of your indecisiveness; it will only see the ‘corrected’ line, after the entire
line is assembled. This is sometimes called ‘cooked’ mode. Raw mode does not
wait for entire lines, but sends each character to the process as they occur.
8. What use is /etc/termcap?
(p66 lower-left) The appropriate codes for clearing the screen, deleting a
character, moving the insertion point, opening up a line in the middle of the
screen, doing a non-destructive backspace, and so on are stored in a huge
database, with different command sequences for different styles of terminals.
This is the ‘terminal capabilities’ database, typically stored in /etc/termcap:
9. Name and define the three main components that make up the X window
GUI.
(P66 lower-right)
SERVER–The ‘server’ is responsible for driving the hardware — it decides what
actually gets ‘drawn’ on the screen………..
APPLICATIONS–Various applications, such as ‘xbiff’, create windows. There is
a temptation to think of these utilities as servers, since they ‘serve up’ information
from various remote locations. However they are essentially ‘clients’ of the
server that drives the display hardware………
(p67 top-left)
WINDOW MANAGERS–……………… The window manager is responsible for the
window ‘decorations’ that allow the windows to be moved, resized, iconified, etc.
……………………
10. What is the defining difference between block- and character-oriented
devices?
(p59, top left) Devices come in many flavors, but most of them can be lumped
into two general categories. Once category is block-oriented, which handles data
in fixed-size ‘chunks’, and the chunks can be accessed (read or written)
independently. These types of devices, which are called ‘block devices’ include
things like disk drives.
The other main category consists of ‘character devices’, which input or output a
stream of data. For these, you cannot seek to an individual position. (For
example a mouse is a character device………….
Exercises 10 (p86)
Aren’t only questions 2, 4,6,7,8,10 are relevant for the final?
AGREED^^^^
1. how is dynamic linking different from static linking? what are the
advantages of using dynamic linking.
(Could not find clear answer in book…turned to:
http://cs-fundamentals.com/tech-interview/c/difference-between-static-and-dynamic-linki
ng.php)
Static linking takes all library modules used in a program and loads them into the
final executable. Linking is the last step of compilation.
Dynamically linked libraries just take the name of the external modules and links
the associated files at runtime. One copy of the shared library is kept in memory, thus
reducing the size of the executable and saving memory and disk space.
ALSO Dynamicaly linked libraries could be 10 to 100 times smaller and probably
load faster than statically fucking since much of what you need is already in
memory. In dynamic fucking files we only need one set of page frames to hold ie:
printf.o objects(Like everybody share a bitch, much cheaper right?) VS static
fucking files would need its own copy of printf.o in memory which is a huge
waste of RAM like a little selfish bitch.
Another thing about this stupid shit is that even though dynamically link looks
so fucking cool, it’s not. Check this out! In dynamic linking, every single shitty
binaries depend on that shared dynamic libraries right…What if that shared
libraries gets Fucked in the ASS.. All binaries that depend on that shit is pretty
much fucked! as Dr. Carroll would described on his notes pg 70 “…now has a
GAPING HOLE!” ( ͡° ͜ʖ ͡°) ̂ You’re my hero!
^Hang in there buddy
^One of the reasons video games are statically linked, and also to prevent
security flaws. 🙂
2. Name a system call that will cause the [non-writable] text area of a
process to suddenly be different. Hint: your shell made extensive use of
this fundamental magic.
fflush(stdout) should this be execvp()?
+1 for exec(). When you execvp() all the code from the parent is
dumped and replaced with whatever program is execed. The text area is
obviously changed because it must contain the executable for the new process.
I think you are right purple. I was 50/50 on this one. thanks for the
confirmation 🙂
3. What [and how] is uninitialized data treated differently from initialized data
in the a.out file?
http://cs-fundamentals.com/tech-interview/c/difference-between-static-and-dynamic-linking.php
http://cs-fundamentals.com/tech-interview/c/difference-between-static-and-dynamic-linking.php
Uninitialized is not actually copied from the disk because by default uninitialized data is
all null. There is no point in storing a bunch of nulls. Therefore, the linker just allocates
the amount of data which will ultimately be needed for these uninitialized variable but
does not actually copy these nulls from the disk.
4. When there is a lot of swapping activity, computer efficiency drops
because writing to disk is much, MUCH slower than writing to RAM. We
sometimes simulate file systems [and thereby make them very fast] by
holding them in RAM. Why not put the swap area in RAM as well?
(Please double check this) Because that would be redundant. We swap into the
HDD to free up room in RAM.
That answer makes sense for me, minus the “compelling, forbidding”
reasons. Assuming “swap area” is the same as “swap space”, then it makes no
sense at all (by definition) to put swap space in RAM. see:
https://www.centos.org/docs/5/html/5.2/Deployment_Guide/s1-swap-what-is.html
agreed.
5. Why do text/data/stack segments have different writable/executable
permissions?
(Page 70 Notes) **Add onto this if you have any additional information**
This is for protection. One would not want the stack to have executable permissions
because a hacker could use their own input, which can be machine code, to redirect the
return address of a system function to instead jump to some other (harmful) instructions.
The text segment is the opposite, it can execute but not write. This is because once it is
executing, you do not want the code in this to be modified.
6. How does the Linux Page Frame Reclaiming Algorithm (PFRA) differ from
our original Clock algorithm
The PFRA first distinguishes pages by 3 categories: discardable, syncable, and
swappable. It first checks if any pages are discardable and puts them on the free list
immediately. After that, with the two remaining “harder” categories (syncable and
swappable), the PFRA then using a clock algorithm to figure out which pages among
them to free up.
7. Describe the UNIX virtual file system, and explain why it is useful.
The purpose of the VFS is to allow client applications to access different concrete
file systems in a uniform way. For example VFS can be used to access network and
local storage devices transparently without client application noticing the difference. Or
it can be used to bridge differences between Windows, Unix, and Mac OS file systems.
(Abstraction Layer)
__________________________________________________________________________
https://www.centos.org/docs/5/html/5.2/Deployment_Guide/s1-swap-what-is.html
TANENMBAUM:
Answers for Carroll’s recomended problems from tanenmbaum 3rd edition (not from lecture
notes):
http://www.comsizo.com.br/resolucoes/SistemasOperacionais_-_Tanenbaum_-_3Ed_Solution.p
df
^^^^^ link is broken! <Hey bae, I got a new one for you:
http://download1.pearsoned.de/download/download.aspx?FileID=%7B0F3CA1CC-D955-483E-
AA0B-6D841CCEF85B%7D
Chapters 1,2,3,6 are in the previous midterm 1 section.
Chapter 4 (Page 325): 1, 4, 15, 17, 21, 33, 34
Chapter 5 (Page 429): 13, 22, 30 (consider seek time, latency, transfer rate).
Chapter 10 (Page 808): 4, 9, 14, 17, 20, 22-25, 27, 31, 33, 37
Tanenbaum Chapter 4
1. In early UNIX systems, executable files (a. out files) began with a very specific
magic number, not one chosen at random. These files began with a header,
followed by the text and data segments. Why do you think a very specific number
was chosen for executable files, whereas other file types had a more-or-less
random magic number as the first word?
These systems loaded the program directly in memory and began executing at
word 0, which was the magic number. To avoid trying to execute the header
as code, the magic number was a BRANCH instruction with a target address
just above the header. In this way it was possible to read the binary file directly
into the new process’ address space and run it at 0, without even knowing
how big the header was.
4. Systems that support sequential files always have an operation to rewind files.
Do systems that support random access files need this too?
No. If you want to read the file again, just randomly access byte 0.
5. (not in study guide but suggested in lecture notes p53) Some 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.
http://www.comsizo.com.br/resolucoes/SistemasOperacionais_-_Tanenbaum_-_3Ed_Solution.pdf
http://www.comsizo.com.br/resolucoes/SistemasOperacionais_-_Tanenbaum_-_3Ed_Solution.pdf
http://download1.pearsoned.de/download/download.aspx?FileID=%7B0F3CA1CC-D955-483E-AA0B-6D841CCEF85B%7D
http://download1.pearsoned.de/download/download.aspx?FileID=%7B0F3CA1CC-D955-483E-AA0B-6D841CCEF85B%7D
15. Consider the i-node shown in Fig. 4-13. If it contains 10 direct addresses of 4
bytes each and all disk blocks are 1 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.
I had to think a bit to figure this out. So think about it this way. You have 10 direct addresses to 1KB disk
blocks, so thats 10KB to start with. Then your indirect block points to a 1024B disk block filled with 4byte
pointers, (1025/4) giving a 256 additional blocks. Add them together and badabing badaboom. 266KB.
17. Two computer science students, Carolyn and Elinor, are having a discussion
about inodes. Carolyn maintains that memories have gotten so large and so
cheap that when a file is opened, it is simpler and faster just to fetch a new copy
of the i-node into the inode table, rather than search the entire table to see if it is
already there. Elinor disagrees. Who is right?
Elinor is right. Having two copies of the i-node in the table at the same time
is a disaster, unless both are read only. The worst case is when both are being
updated simultaneously. When the i-nodes are written back to the disk,
whichever one gets written last will erase the changes made by the other one,
and disk blocks will be lost.
21. What would happen if the bitmap or free list containing the information about
free disk blocks was completely lost due to a crash? Is there any way to recover
from this disaster, or is it bye-bye disk? Discuss your answers for UNIX and the
FAT-1 6 file system separately.
It is not a serious problem at all. Repair is straightforward; it just takes time.
The recovery algorithm is to make a list of all the blocks in all the files and
take the complement as the new free list. In UNIX this can be done by scanning
all the i-nodes. In the FAT file system, the problem cannot occur because
there is no free list. But even if there were, all that would have to be
done to recover it is to scan the FAT looking for free entries.
33. How 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 the root directory is in
memory, but nothing else along the path is in memory. Also assume that all
directories fit in one disk block.
The following disk reads are needed:
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.
34. In many UNIX systems, the i-nodes are kept at the start of the disk. An
alternative design is to allocate an i-node when a file is created and put the i-node
at the start of the first block of the file. Discuss the pros and cons of this
alternative.
**Carrol’s answer for the Cons against this: Knowing the size of inodes, one can easily
find which every node in memory by looking at the address calculated by (inode
number* size of inodes). If the inodes are scattered it becomes difficult to search for
them.
Some pros are as follows. First, no disk space is wasted on unused i-nodes. Second, it
is not possible to run out of i-nodes. Third, less disk movement is needed since the
i-node and the initial data can be read in one operation. Some cons are as follows. First,
directory entries will now need a 32-bit disk address instead of a 16-bit i-node number.
Second, an entire disk will be used even for files which contain no data (empty files,
device files). Third, file system integrity checks will be slower because of the need to
read an entire block for each i-node and because i-nodes will be scattered all over the
disk. Fourth, les whose size has been carefully designed to t the block size will
no longer t the block size due to the i-node, messing up performance.
the biggest objection to the proposed scheme is surely that you lose the concept of
an 'index' for the inodes ('inode' is short for 'index node'). If the nodes take up 100
bytes, and we want inode 12345, we immediately calculate the location of the data as
100*12345 and we're there. The proposed scheme instead scatters the inodes all over
the place, essentially forming a complex linked list, and it's Hell On Wheels to try to
search for anything.
Tanenbaum Chapter 5
13.-Why are output files for the printer normally spooled on disk before being
printed?
If the printer were assigned as soon as the output appeared, a process could tie up the
printer by printing a few characters and then going to sleep for a year.
22.-A 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.
30.- A system simulates multiple clocks by chaining all pending clock requests
together as shown in Fig. 5-34. Suppose the current time is 5000 and there are
pending clock requests for time 5008, 5012, 5015, 5029, and 5037. Show the
values of 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 → 3 → 4 → 3 → 14 → 8.
At time 5013:
Current time = 5013; Next Signal = 2; Header 2 → 14 → 8.
At time 5023:
Current time = 5023; Next Signal = 6; Header → 6 → 4 → 4.
CHAPTER 10
4.- Why does Linux distinguish between standard output and standard error, when
both default to the terminal?
They are separate, so standard output can be redirected without affecting standard
error. In a pipeline, standard output may go to another process, but standard error still
writes on the terminal
9.- Does it make sense to take away a process' memory when it enters zombie state?
Why or why not?
Yes. It cannot run any more, so the earlier its memory goes back on the free list, the
better.
14.- In every process' entry in the task structure, the PID of the parent is stored. Why?
When the process exits, the parent will be given the exit status of its child. The PID is
needed to be able to identify the parent so the exit status can be transferred to the correct
process.
17.- When booting Linux (or most other operating systems for that matter), the bootstrap
loader in sector 0 of the disk first loads a boot program which then loads the operating
system. Why is this extra step necessary? Surely it would be simpler to have the
bootstrap loader in sector 0 just load the operating system directly.
The program loaded from block 0 is a maximum of 512 bytes long, so it cannot be very
complicated. Loading the operating system requires understanding the file system layout in
order to find and load the operating system. Different operating systems have very different file
systems; it is asking too much to expect a 512-byte program to sort all this out. Instead, the
block 0 loader just fetches another loader from a fixed location on the disk partition. This
program can be much longer and system specific so that it can find and load the OS.
20.- In Linux, the data and stack segments are paged and swapped to a scratch copy kept
on a special paging disk or partition, but the text segment uses the executable binary file
instead. Why?
The text segment cannot change, so it never has to be paged out. If its frames are
needed, they can just be abandoned. The pages can always be retrieved from the file system.
The data segment must not be paged back to the executable file, because it is likely that it has
changed since being brought in. Paging it back would ruin the executable file. The stack
segment is not even present in the executable file.
22.- A file is mapped in using the following mmap system call:
mmap(65536, 32768, READ, FLAGS, fd, 0)
Pages are 8 KB. Which byte in the file is accessed by reading a byte at memory
address 72,000?
Memory address 65,536 is file byte 0, so memory address 72,000 is file byte 6464.
23. After the system call of the previous problem has been executed, the call
munmap(65536, 8192) 8193
is carried out. Does it succeed? If so, which bytes of the file remain mapped? If not, why
does it fail?
Originally, four pages worth of the file were mapped: 0, 1, 2, and 3. The call succeeds
and after it is done, only pages 2 and 3 are still mapped, that is, bytes 16,384 though 32,767
24. Can a page fault ever lead to the faulting process being terminated? If so, give an
example. If not, why not?
It is possible. For example, when the stack grows beyond the bottom page, a page fault
occurs and the operating system normally assigns the next- lowest page to it. However, it the
stack has bumped into the data segment, the next page cannot be allocated to the stack, so the
process must be terminated because it has run out of virtual address space. Also, even if there
is another page available in virtual memory, the paging area of the disk might be full, making it
impossible to allocate backing store for the new page, which would also terminate the process.
A simpler reason would also be if there is a pointer pointing to an address in the kernel,
this would cause a page fault because the user does not have access to the kernel’s data.
if you attempt to follow a pointer to an address in the kernel's virtual address space
[while in user mode], this will generate a page fault (since you don't have access to the
kernel data) and you will be summarily terminated with extreme prejudice (since you're not
allowed to look at this privileged data).
25. Is it possible that with the buddy system of memory management it ever occurs that
two adjacent blocks of free memory of the same size co-exist without being merged into
one block? If so, explain how. If not, show that it is impossible.
It is possible if the two blocks are not buddies. Consider the situation of Fig. 10-17(e). Two new
requests come in for eight pages each. At this point the bottom 32 pages of memory are owned
by four different users, each with eight pages. Now users 1 and 2 release their pages, but users
0 and 3 hold theirs. This yields a situation with eight pages used, eight pages free, eight pages
free, and eight pages used. We have two adjacent blocks of equal size that cannot be merged
because they are not buddies.
27.- Give two examples of the advantages of relative path names over absolute
ones.
Opening a file by a path relative to the working directory is usually more convenient for
the programmer or user, since a shorter path name is needed. It is also usually much
simpler and requires fewer disk accesses.
31. If a Linux file has protection mode 755 (octal), what can the owner, the
owner's group, and everyone else do to the file?
The owner can read, write, and execute it, and everyone else (including the owner’s
group) can just read and execute it, but not write it
33. In Fig. 10-24, both Fred and Lisa have access to the file x in their respective
directories after linking. Is this access completely symmetrical in the sense that
anything one of them can do with it the other one can too?
No. The file still has only one owner. If, for example, only the owner can write on the file,
the other party cannot do so. Linking a file into your directory does not suddenly give
you any rights you did not have before. It just creates a new path for accessing the file.
37. When an i-node is read in from the disk during the process of opening a file, it
is put into an i-node table in memory. This table has some fields that are not
present on the disk. One of them is a counter that keeps track of the number of
times the i-node has been opened. Why is this field needed?
When a file is closed, the counter of its i-node in memory is decremented. If it is greater
than zero, the i-node cannot be removed from the table because the file is still open in
some process. Only when the counter hits zero can the i-node be removed. Without the
reference count, the system would not know when to remove the i-node from the table.
Making a separate copy of the inode each time the file was opened would not work
because changes made in one copy would not be visible in the others.
Midterm Answers
1. 1 * h + 11(1-h) < 3 answer: h > 0.8
2. (a) first=3
second = 2
second = 6
third = 1
third = 1
third = 5
third = 5
(b) Yes. Depending on what parent or child is being processed our output
may vary in its order.
3. When the process exits, the parent will be given the exit status of its child. The PID is
needed to be able to identify the parent so the exit status can be transferred to the
correct process.
4. A trap is caused by the program and is synchronous with it. If the program is run again
and again, the trap will always occur at exactly the same position in the instruction
stream. An interrupt is caused by an external event and its timing is not reproducible.
5. (A)Since this is a [one-CPU] scenario the processes will have to take turns. The
use of a turn variable helps ensure only one of them will have access to the
critical region at a time.
(B)
1. No assumptions may be made about speeds or the number of CPUs.
2. No process should have to wait forever to enter its critical region.
6. read(fd, buffer, nbytes) can return less than nbytes if it reaches an EOF earlier
than nbytes
7. (A) [0] = s, [1] = -, [2] = NULL, [3] = ??, [4] = ??,
(B)for(;;){
pid_t pid;
pid=wait(NULL);
if(pid==childPid){
break;
}
}
(C)It would run fine in a child; we would just have to have the parent wait() for it.
But there is no real point in forking a whole new process, when the parent can just do it
quite easily
(D)
8. up(S); //S = 3
x=0; //S = 3, x =0
for(;;) { //first loop //second loop
down(S) //S = 2, x =0 S = 0, x =1
x++; //S = 2, x =1 S = 0, x =2
down(S) //S = 1, x =1 S = [block], x =2
}
9. 256KB = 2^18 4KB = 2^12
2^18/2^12 = 2^6 table slots → hash chain length = 1
2^7 table slots then hash chain length = 0.5
10. (A) 145124356425
optimal lru fifo
1 *1 *1 *1
4 *14 *14 *14
5 *145 *145 *145
1 145 145 145
2 *245 *125 *245
4 245 *124 245
3 *345 *324 *235
5 345 *354 235
6 *645 *356 *236
(B) FiFO
11. A machine has 28-bit virtual addresses and 16-bit physical
addresses. Page frame size is 2KB.
(A) 2^10 * 2^1 = 11bits
Shouldn’t the answer below be just 64 pages, not 64k?
2^17 bits / 2kb pages = 2^6 = 64 pages
This is incorrect. 228/211 = 217 = 27 * 210 = 27kpages = 128kpages
(B) 2^28 / 2^11 = 2^17 = 2^10 * 2^5 * 2^2 = 64k page
(C) 2^16 / 2^11 = 2^5 = 32 page frames
(D)2050=2048+2=[(2^10) * 2] +2
2K = (2^10) *2
Physical address = 2
Midterm Spring 2016
Please add the questions!!!!
1. this is like a mutex but implements a wait queue in the kernel for multiple processes.
This helps not have to switch to kernel mode unless necessary and also getting rid of
spin lock and unnecessary cpu cycles. No switches are required if there is no contention
for the mutex being addressed.
2. Aging (page brought into memory the R bit is set to one)
3. Start up pages for vi were not in the page frames or TLB after reboot
4. 4 GB | 1024 | 1024 | 1 mb
5. Yes, pages can be shared between parent and child | Yes, both can use the same
program (like vi)
6. Large page table size | Internal fragmentation
7. Deadlock – because the consumer and producer share &mutex, if consumer runs first
while empty, it will got blocked at &full, then when producer tries to produce but the
mutex is still blocked so it creates a deadlock
8. FIFC | LRU | Optimal algos (See below for quick answer)
9. Shortest job first problem – you don’t know how long they take to complete
10. “Parent = Bonjour, Adios | Child = Bonjour, Sayanorar” , fflush before the fork()
11. A. only the command arguments (pipe – null between arguments) B. readdir, opendir,
stat, lstat, closedir C. the next wait call will reap the zombies D. error, create a file named
&
4) 32-bit virtual addressing scheme uses an inverted page table. Want 2^22 virtual pages. Do it.
a) # of Distinct virtual addresses with 32 bits? 2^32 = 4G
b) Have 2^22 pages, what must be the page size? 2^32/2^22 = 2^10 = 1k
c) How many page frames? The answer is 1k. I guessed.
d) How many entries does the inverted page table need? The answer is 1k. I guessed.
8a) Here’s what I got:
# FIFO LRU Optimal
0 *0 *0 *0
3 *03 *03 *03
4 *034 *034 *034
0 034 034 x
5 *534 *054 x
3 534 *053k x
Nailed it…
8b) Not possible because we would run into a situation where something that needs to never
again occur also need to occur next. (There’s probably a nicer way of putting that.)