5210 Final Exam

The final exam is scheduled for Wednesday, December 11, 4-6pm.

Sample Questions
Study Guide
Q and A


Sample Questions:

1.    We said that operating systems can be viewed in two different ways.  (For a hint, the initials of these two ways are “R.M.” and “E.M.”)  List these two ways, and give a very brief, one-sentence description of each.

2.    Draw a diagram showing the three states that a process can be in and the possible transitions between those states.

3.    What is the “process table?” List three pieces of important information stored therein.

4.    Explain, briefly, the difference between a process and a thread.

5.    For each of the following, answer either “User Threads” or “Kernel Threads.”
    a.    Which implementation requires more overhead on a context switch?
    b.    Which implementation is more allows for quicker thread-switching?
    c.    Which implementation would be better for a process doing lots of I/O?
    d.    Which implementation could be provided by a library on top of a non-threading OS?

6.    Give a quick, one-line definition of each of these terms:
    a.    race condition
    b.    interprocess communication
    c.    interprocess synchronization
    d.    pipe

7.    Barnes and Noble maintains a database containing the account balance for each B&N CafeCard holder.  Unfortunately, this database does not implement any method to guarantee protected access to its data.  Let B be the variable which contains the balance (initially $30) in some account, and suppose that two people use their cards at the same time, to purchase drinks costing $5 and $3 respectively:
    a.    Give an example of a sequence of events which could result in the wrong value being saved back to the database.
    b.    What are all possible final values that could occur following these two transactions?

8.    We described two operations P(s) and V(s) on a semaphore s.
    a.    What does P do?
    b.    What does V do?
    c.    What is special about the way P and V are performed that enable them to solve the “race conditions” problem?.   

9.    What is meant by a “binary semaphore?”

10.    We discussed monitors and how they can be used for interprocess synchronization
    a.    Briefly describe what a monitor looks like in a program
    b.    Which of the following is most responsible for making sure monitors guarantee mutual exclusion:  The programmer, the OS, the kernel, the compiler or the user?

11.    What is meant by a “test and set lock” (TSL) instruction?  In particular, mention what the return value of a TSL instruction is, and mention what is special about the way TSL instructions are executed. 

12.    Below is a bit of code which attempts to solve the producer-consumer problem with semaphores.  It doesn’t work.  Make appropriate corrections in the initialization, Producer and Consumer code.

Initialization:
full  = 0;    //initialize semaphore
empty = 0;    //initialize semaphore
mutex = 0;    //initialize a mutual exclusion semaphore
Producer:

while(1){
  Produce_item(thing);
  P(empty);
  V(mutex);
  Insert_item(thing);
  P(mutex);
  V(empty)
}   
Consumer:

while(1){
  P(full);
  V(mutex);
  Remove_item(thing);
  P(mutex);
  V(full)
  Consume_item(thing);
}


13.    The solution below attemts to solve the producer/consumer problem using message passing.  It almost works.  All that is missing is some sort of initialization to “get the ball rolling.”
    a.    What would happen if the code was run as written?
    b.    Add a snippet of code to fix this problem.
Producer:

while(1){
  message m;

  while (TRUE) {
    make_item(thing);
    receive(consumer, &m);
    build_message(&m, thing);
    send(consumer, &m);
  }
}
Consumer:

while(1){
  message m;
 
  while (TRUE) {
    receive(producer, &m)
    extract_item(&m, thing);
    send(producer, &m);
    consume_item(thing);
  }
}


14.    Define each of the following terms in one succinct sentence: 
    a.    Context switch
    b.    Scheduler
    c.    quantum

15.    Suppose that a quantum is 80ms and that a context switch takes 20ms.  What fraction of the time is the CPU doing work on processes?

16.    What are meant by the terms CPU-bound and I/O-bound?

17.    How long is a “jiffy” in Linux scheduling?

18    What is the arithmetical relationship between goodness, priority and quantum in the Linux schduling algorithm?

19.    A certain operating system maintains 4 priority levels for its processes:  I/O, short quantum, Terminal,  and long quantum. 
    a.    Arrange them in order from highest to lowest priority
    b.    Suppose I tell you that a process had spent several minutes classified as a long quantum process, and then suddenly switched to another priority level, gradually working its way back to the long quantum priority level, passing through the other two levels as well, spending a brief time in each.  Do you suppose that this process was I/O-bound or CPU-bound?  And what event could have happened to cause this priority-hopping to take place?

20.    A certain operating system uses “ageing” to estimate how long a process will spend on the CPU on its next timeslice.  Let t be the estimated value and let d be the amount of time the process last spent on the CPU.  The formula it uses to update its estimate is:   t ← ½ t + ½ d.  If t has the value “10” and the next three times it spends on the CPU are 8, 7 and 12, what will the final value of t be?

21.    Draw the trajectory diagram for the two processes shown below, which request the resources in the order shown.  (As a polite reminder, I’ve drawn a sample trajectory diagram to the right.)
Process 1 Process 2
Request A
Request B
Release A
Release B		 Request B
Request A
Release B
Request B
Release B
Release A


22.    For the processes and resource requests given above, is it possible for deadlock to occur?  Explain your answer, referring to your diagram.

23.    Suppose that each of k processes that run on a certain system will be using the CPU at any given time with probability p, independently of one another.  What is the probability that at any given time, all k processes will be blocked — that is, will not be able to use the CPU. 

24.    Some questions about Linux scheduling:
    a.    Process A has a priority of 32 and a quantum of 16. Suppose it uses none of its quantum for each of the next two "epochs," that is, each of the next two times that quantum values are re-computed. What will its final priority and quantum be?
    b.    Process B has priority 18. What is the largest its quantum could become? Explain.

25.    What are the 4 conditions necessary for deadlocks to occur? Give a brief description of each

26.    One way of avoiding deadlocks is to linearly order the resources. Explain in one sentence what this means.

27.    To the right is a resource / process diagram showing processes that have locked, or are waiting for, various resources.
    a.    Has deadlock occurred?
    b.    Suppose an algorithm does depth-first-search from vertex A:
        -    List an order in which vertices might be visited for the first time. That is, list the vertices in the order in which they become "gray", as described in class.
    c.    Say at what point in the algorithm, following your list above, we would have discovered whether or not there was a deadlock

28.    Suppose a bitmap is used to keep track of which blocks of memory are used and which are free. How large, in bytes, would such a bitmap be if a computer had 64MB of memory and used blocks of size 32 bytes?

29.    Here is a linked list showing memory usage. Process P was just placed into the queue, and now process Q, of size 10, enters the scene. Into which hole would this process be placed if we use a) best fit, b) first fit, c) next fit, d) worst fit.


30.    One of the advantages of having many processes in memory at the same time is that we can increase CPU utilization.
    a.    What is meant by CPU utilization?
    b.    How does having more processes in memory increase CPU utilization?
    c.    Suppose n processes are in memory, and each is ready to run (not blocked) at any given time independently with probability p. What will the CPU utilization be, on average?

31.    Suppose a certain computer uses 24-bit addresses and virtual memory with pages of size 2048.
    a.    How many pages comprise a process's virtual address space?
    b.    How many entries would be in that process's page table?
    c.    How large would the page frames be?
    d.    If each page table entry was 8 bytes, how much memory would be required to store the page tables for 20 processes?
    e.    If the computer has 256MB of RAM, then how many frames would it have?
    f.    How many frames would be needed to hold one process's page table?

32.    We continue the example above: 24-bit addresses and virtual memory with pages of size 2048.
Page Frame
0 21
1 9
2 18
3 12
4 1
5 17
6 11
... ...
    a.    Here is a portion of the page table for a certain process: Translate the virtual address 8197 into a real address, using this table.
    b.    Show how that calculation would happen inside the TLB within the MMU, using bits.

33.    The Not Recently Used page-replacement algorithm uses an "R" bit and an "M" bit.
    a.    What do "R" and "M" stand for?
    b.    When is the "R" bit set?
    c.    When is the "R" bit reset?
    d.    When is the "M" bit set?
    e.    When is the "M" bit reset?
    f.    The NRU algorithm divides pages into 4 classes: Class 0 through Class 3. When a decision is made to evict some page, a page from the lowest possible class is selected. What characterizes pages in each of these classes:
            Class 0
            Class 1
            Class 2
            Class 3

34.    We saw 3 different implementations of the "Least Recently Used" algorithm. Fill in the blanks below to describe each of them:
In one implementation we kept a ___-bit counter which was incremented on every ____________________________. Each page's entry in the page table was stamped with this counter each time that page was referenced.

35.    In another implementation we kept an n×n matrix, where n is the number of pages. This matrix started out as all 0s, and each time page i was referenced, we every bit in ________ i to ___ and then every bit in ________ i to ___. Then when we needed to evict a page, we selected the page whose ________, interpreted as a binary number, was ________.

36.    Finish this description of the second chance algorithm: In the second-chance algorithm, we keep a queue of pages together with their "R" bits. When we have to decide which page to evict, we first consider the page at the front of the queue. If that page's "R" bit is 0, then...   But if the "R" bit is 1, then...

37.   What is the basic difference between the "second chance" and "clock" algorithms?

38.    How large can a file be without having to use that file's inode's double or triple redirect blocks? Assume block size of 1024 bytes and addresses of size 4 bytes.

39.    What information is stored in a directory file? (Include only that information stored in the directory file.)

40.    For the two snippest of code below, assume you are in a directory with exactly one entry, "file1," (aside from the usual "." and "..").
What will be printed out when the following code is executed:  Explain your answer briefly:
Snippet 1
 Snippet 2
void main(){
   cout << “Place 1\n”;
   execlp(“ls”, “ls”);
   cout << “Place 2\n”;
   execlp(“ls”, “ls”, “-i”);
   cout << “Place 3\n”;
}
 void main(){
   if(fork() == 0);
      execlp(“ls”, “ls”);
   else{
      fork();
      cout << “Greetings\n”;
   }
}


41.   The program shown below uses threads.
    a.    What should be there where the “****” are?
    b.    What header file would need to be included in order for this program to compile?
    c.    What is one possible output  if this program is compiled to a.out, and the user types:  a.out 4?
    d.    Why is there more than one possible output?

int main(int argc, char *argv[])
{
   pthread_t cow[10];
   int numcows = argc;

   int i, k;

   for(i=0; i < numcows; i++){
        pthread_create(&cow[i], NULL, moo, i);
   }
   for(k=0;k<i+1;k++){
        pthread_****(cow[k], NULL);
   }
}


void *moo(void *n)
{
   int m = (int) n;
   cout << “Moo from cow number “ << n << endl;
   pthread_exit(0);
}

42.    A husband and wife have a joint checking account, and at the same time (but at different locations) he makes a $30 withdrawal from the account and she makes a $50 deposit to the account. If the account started with $100 in it, then what are all possible final amounts if we assume no provision was made to avoid race conditions?  Use as many slots as necessary.
Possible value:_______ How it could happen:
Possible value:_______ How it could happen:
Possible value:_______ How it could hapen:
Possible value:_______ How it could hapen:

43.    One way to avoid race conditions is to protect certain "critical sections" of code by placing them within blocks of code that restrict entry to those critical sections. Consider the following two "solutions" to the critical section problem:
Solution 1

Shared variable: turn
Solution 2

Shared variables: flag[0] and flag[1]
Process 0 Process 1
Process 0 Process 1

...

while(turn != 0);
// do nothing

[Critical Section]

turn = 1;

...
...

while(turn != 1);
// do nothing

[Critical Section]

turn = 0;

...

...

flag[0] = true;

while(flag[1]);
// do nothing

[Critical Section]

flag[0] = false;

...
...

flag[1] = true;

while(flag[0]);
// do nothing

[Critical Section]

flag[1] = false;

...
    a.    Both of these "solutions" employ busy waiting. Explain what is meant by that term.
    b.    One of these solutions requires "strict alternation" of the processes involved. Explain briefly what is meant by that term, and then explain how it happens in one of these solutions.
    c.    In one of these solutions deadlock can occur. Explain briefly what is meant by that term, and then explain how it can happen in one of these solutions.

44.    Give a bit of code (or pseudocode) for the P and V operations:
void P(semaphore &s){











}		 void V(semaphore &s){











}


45.    Below are 4 lines of code dealing with semaphores. I have explained what the first line does. Please do the same for the remaining three lines.
sem_t s;

Declares s to be a semaphore
sem_init(&s, 0, 8);



sem_post(&s);



sem_wait(&s);




46.    We mentioned in class the problem of "relocation," that is, the situation in which on older operating systems, the destination address of machine language "JUMP" commands could not be hard-coded because it might not be known in advance where the program would be loaded into memory.
    a.    How did the loader solve this problem on these older systems?
    b.    Why is this not an issue with today's operating systems?

47.    What is the relationship between pages and frames? In particular, give the relationship between their sizes and their physical locations (if any) inside the computer.

48.    What is meant by a "page replacement" algorithm?


49.    What is the relationship between files and inodes in UNIX?  Give three pieces of information that can be found in an inode.

50.    For each part of this problem, suppose we have a filesystem that uses 16-bit addresses and blocks of size 256 bytes:
    a.    How many addresses can be stored in one disk block?
    b.    What is the largest a file can be so that it's addresses can be stored in an inode without using any of that inode's indirect blocks.?
    c.    What is the largest a file can be using all levels of address information (the direct and single, double and triple indirect blocks)?
    d.    How large could the disk in the problem above be so that all its blocks can be addressed?

51.    By default, file descriptors 0, 1 and 2 are allocated to certain "standard" I/O streams. What are they?
        0 is allocated to: ________________________
        1 is allocated to: ________________________
        2 is allocated to: ________________________

52.    What is special about the file descriptors that are returned by the dup() and open() system calls?



Study Guide


Q and A