24 April

• Practice exam (PDF)

Solutions

1. Terminology
   1. semaphore
   2. deadlock
   3. mount
   4. random access

2. In the metaphor, a process running on the CPU is akin to eating, and so starvation means that the process does not get a chance to run on the CPU. Starvation is not possible in first-come first-served, because it is a fair strategy – every process will eventually get its chance to run.

   On the other hand, starvation is possible using shortest-job first. As long as shorter jobs keep arriving, a longer-running job will have to wait. Without taking other precautions, that job may starve.

3. This was the same as a quiz. First you have to recognize that 23, 24, 25 make up the critical section, because these are the lines that read and write the shared variables: current and frequencies.

   1. You should highlight the lines 23–25 in each group, and if they don’t overlap, then the sequence is valid:

      

   2. The critical section, as stated above, is just 23–25.

   3. Add the semaphore: it must be initialized to 1 (for mutual exclusion), then you put a wait before and a signal after the critical section:

      // Shared variables
      int mutex = Open_Semaphore("mutex", 1);
      
          // Inside the loop
          if(n > 0)
          {
              Wait_Semaphore(mutex);
              frequencies [current].letter = letter;
              frequencies [current].count = n;
              current++;
              Signal_Semaphore(mutex);
          }

4. This question is about page faults.

   1. First, use Least Recently Used (LRU). This means looking backward in time, to see which of the existing pages was used the longest time ago (least recently). I get 10 page faults.

      

   2. Next, we try an optimal strategy by looking forward in time. There are probably other possible choices that can be made, but I got 7 page faults.

      

   3. Finally, try LRU again, but this time with four memory locations. This reduces it to 7 page faults too.

      

5. Inverted index, for a search engine (relates to assignment 7).

   1. To match “colorless green ideas,” you would take the intersection of these three sets, which is just document numbers 5 and 8.

   2. To rank the results, I would use the distance between the line numbers. For example, in doc 5, all three words appear in lines 2–3, so I would rank that highest. In doc 8, the words appear further apart (line 80 and line 6).

6. About a hypothetical file system. Pointers are two bytes, so an index block can store 128 of them.

   1. Each file has just one direct pointer and one indirect pointer. So the largest possible file would use the direct pointer (to reach 256 bytes), and then the indirect pointer would point to a full index block using all 128 direct pointers to data. So, 256 plus 128*256 = 33,024 bytes.

   2. Maximum number of files that can be stored is determined by the size of the FAT. In this case, there are 32 directory blocks, and each can hold 16 entries (because each entry is 16 bytes, and 256÷16 = 16). So that means there can be 32*16 = 512 files on the disk.

   3. The direct pointer handles the first 256 bytes. We are looking for offset 528, so it’s not there. So, we consult the index block. The first entry in the index is block 720. This block will hold offsets 256-511, so our target is not there. However, it is in block 719, which will hold offsets 512-767.

      So, we’d need to read block 820 (the index) as well as block 719 (where we’d find the data).