OS Quiz Questions and answers

.README.md

Contributing

1. Fork the gist with the button in the top right corner
2. Make your changes (able to do so in browser, using the edit tool)
3. Add a bullet point to changes.md with a note about what you're adding
4. Make a comment on this main gist with a link to your gist.

As soon as I can, I will merge your changes into this main gist!

Understanding the file format

Files are formated using markdown. See here.

Question formating

Each file contains the questions and answers for one quiz. Unanswered questions are bolded. Questions have the following format:

- What is the color of the sky?
  - Blue

Don't include wrong answers, except for choose all that apply, in that case, incorrect and correct answers should be listed, with [ ] for incorrect answers and [X] for correct ones. The question should be followed by (Check all). Example:

- Which classes at UF make me want to die? (Check all)
  - - [X] OS
    - [ ] All other classes
    - [ ] Any other class

For questions with blanks, use _____ to denote blanks. Example:

- In Linux and Unix, the type of disk is determined by the `_____` device number, while the particular volume is identified by the `_____` device number.
  - major, minor

For questions with matching, make a list of answers, with their matches being in italics. Example:

- What type of deadlock handling method is each of the following?
  - Banker's Algorithm: *Deadlock avoidance*
  - Total ordering of resource types: *Deadlock prevention*
  - Preemption, rollback, or killing blocked process(es): *Deadlock detection and recovery*
  - Full speed ahead an hope for the best: *Ostrich algorithm*

Adding Explanations

To avoid getting the files too cluttered, add you explanation as a collabsable section after the answer for the question you want to explain. Example:

- What is the color of the sky?
  - Blue
  <details>
    <summary>6XAM's Explanation</summary>
    This is due to the properties of light. Checkout this wikepedia article: https://en.wikipedia.org/wiki/Diffuse_sky_radiation
  </details>

This will display as below:

• What is the color of the sky?
  • Blue
  6XAM's Explanation

  This is due to the properties of light. Checkout this wikepedia article: https://en.wikipedia.org/wiki/Diffuse_sky_radiation

09 Files Quiz.md

Quiz 9 Files

• When is the reference count in an i-node increased? (Check all)

  • • When a process with the file open forks
    • When a process writes to the file
    • When a process reads from the file
    • When a directory entry is linked to the file
  6XAM's Explanation

  The reference count for an i-node is the number of other directory entries that refer to this specific file (aka this specific i-node). None of the other choices create a new entry refering to this file, so they are not correct. Another example of something that would decrease an i-node's reference count is deleting a directory entry.

• Which of the following types of file is most likely to exhibit strong locality of access? (Check all)

  • • Database
    • Digital Movie
    • Audio File
    • Electronic Novel
    • Spanish-English Dictionary
  6XAM's Explanation

  Locality of access refers to the idea that accesses close to each other in time should be close to each other in location on the disk. The Database and Dictionary have fairly random access, so there is no strong locality of access. With all of the other data, there is some sequence to the data that is generallay followed. Even though you may skip around a video, song, or book, you generally will watch/listen/read in order.

• What are strong arguments for having larger file block size? (Check all)

  • • Desired data are more likely to be in the block cache for localized accesses.
    • Larger blocks are less expensive.
    • The data rate for reading a block into memory is higher.
    • It takes less time to load a block.
  6XAM's Explanation

  Larger file blocks mean that you're file will be chopped up into fewer, larger chunks.
  

  1. This means local accesses, which are going to be close to each other, will likely be in the last-read (chached) block.
     
  2. Larger blocks are more expensive than small ones because you have internal fragmentation (up until you get to super small block sizes, in which case you have to start considering the size of the data structure that stores the list of blocks).
     
  3. The data rate is higher because you can read in a whole block before having to spend reading the FCB
     
  4. Larger blocks obviously take more time to load than smaller blocks.

• How many disk accesses are needed to bring byte i of a file into memory when the file is stored using contiguous allocation? Assume only the file's FCB is in memory, block pointers require 32 bits, and that blocks hold 4096 bytes each.

  • 1 access
  6XAM's Explanation

  Because the FCB is in memory, we don't need to access the disk to read it. In contiguous allocation, the file is stored directly at it's location on the disk in one long segment, so to get byte i of it, we just need to add i to the file's location from the FCB, and can read that byte in one disk access.

• How many disk accesses are needed to bring byte i of a file into memory when the file is stored using double indirect indexed allocation? Assume only the file's FCB is in memory, block pointers require 32 bits, and that blocks hold 4096 bytes each.

  • 3 accesses
  6XAM's Explanation

  Because the FCB is in memory, we don't need to access the disk to read it. In double indirect indexed allocation, the FCB contains a list-of-lists-of-lists of blocks that the file is stored in. So, we need to read the block containing the first list, then from that list we need to read the block containing the second list, and then finally we can read the block that contains our data.

• How many disk accesses are needed to bring byte i of a file into memory when the file is stored using indexed allocation? Assume only the file's FCB is in memory, block pointers require 32 bits, and that blocks hold 4096 bytes each.

  • 2 accesses
  6XAM's Explanation

  Because the FCB is in memory, we don't need to access the disk to read it. In double indirect indexed allocation, the FCB contains a list-of-lists of blocks that the file is stored in. So, we need to read the block containing the list, and then we can read the block that contains our data.

• What is the largest file size that can be allocated if blocks hold 4096 bytes, block pointers are 32 bits, and files are stored using indexed allocation?

  • 4MB
  6XAM's Explanation

  Block pointers are 32 bits, and with indexed allocation, we have 1 block where we store a list of the blocks that this file is made up of. So, that block of 4096 bytes can hold (4096 bytes/32 bits) block pointers. Unit conversions gives us ((4096*8) bits/32 bits) = 1024 block pointers, meaning a file can be made of, at maximum, 1024 blocks, or 1024*4096 bytes = 4194304 bytes. More unit conversion gives 4194304 bytes * (1 mb / 1024^2 bytes) = 4 mb

• What is the largest file size that can be allocated if blocks hold 4096 bytes, block pointers are 32 bits, and files are stored using double indexed allocation?

  • 4GB
  6XAM's Explanation

  Block pointers are 32 bits, and with indexed allocation, we have 1 block where we store a list of the blocks that store the actual pointers to the blocks this file is made up of. So, one block of 4096 bytes can hold (4096 bytes/32 bits) block pointers. Unit conversions gives us ((4096*8) bits/32 bits) = 1024 block pointers. In this case, we have one block that could be potentially full of pointers to blocks that themselves contain the block pointers for this file, so we have 1024 blocks each holding 1024 block pointers, or 1024 * 1024 block pointers, meaning a file can be made of, at maximum, 1024 * 1024 blocks, or 1024 * 1024 * 4096 bytes = 4294967296 bytes. More unit conversion gives 4294967296 bytes * (1 gb / 1024^3 bytes) = 4 gb

• What is the largest file size that can be allocated if blocks hold 4096 bytes, block pointers are 32 bits, and files are stored using linked allocation?

  • 16TB
  6XAM's Explanation

  Block pointers are 32 bits, and with linked allocation the files could theoretically span all the blocks of the system (the linked list for one file goes thru all the blocks). So, to figure out the maximum number of blocks we can have, we simply need to figure out how many unique block pointers we can have; in this case, the pointer is 32 bits, so we have up to 2^32 blocks per file. Multiplying this by the size of the blocks gives us our file size, 2^32 * 4096 bytes = 16TB.

• What is the largest file size that can be allocated if blocks hold 4096 bytes, block pointers are 32 bits, and files are stored using contiguous allocation?

  • 16TB
  6XAM's Explanation

  Block pointers are 32 bits, and with contiguous allocation the files could theoretically span all the blocks of the system (Because with contiguous allocation, the only limit is the hard drive size). So, to figure out the maximum number of blocks we can have, we simply need to figure out how many unique block pointers we can have; in this case, the pointer is 32 bits, so we have up to 2^32 blocks per file. Multiplying this by the size of the blocks gives us our file size, 2^32 * 4096 bytes = 16TB.

10 Disk Quiz.md

Quiz 10 Disk

• A disk takes 1ms per track seek time, and the head is currently on track 70. Assume it takes 5ms to service a request once the head is at the right track. The following set of requests are pending, given as (ID, track) in order of arrival. How much time does it take to service all the requests if the elevator algorithm is used an the current direction is down? Requests: (A,80)(B,75)(C,82)(D,90)(E,45)

  • 95 ms
  TylerMetzger's Explanation

  The elevator algorithm (a.k.a. SCAN algorithm) moves in a given direction, servicing the requests in its path. Once reaching the final request in that direction, it reverses its direction and follows the same pattern.

    Next Served       Distance to Travel        Current Direction
      E - 45                 25                       Down
      B - 75                 30                         Up
      A - 80                  5                         Up
      C - 82                  2                         Up
      D - 90                  8                        N/A
    

  To calculate the total time add the travel distance times the seek time per track plus the total tracks serviced times service time per track:

    (25+30+5+2+8) tracks * 1 ms/track + 5 tracks * 5ms/track = 70ms (seek time) + 25ms (service time) = 95ms
    

• A disk takes 1ms per track seek time, and the head is currently on track 50. Assume it takes 5ms to service a request once the head is at the right track. The following set of requests are pending, given as (ID, track) in order of arrival. What is the order in which requests are serviced if the policy is SSF (aka SSTF)? Requests: (A,55)(B,53)(C,40)(D,48)(E,45)

  • DECBA
  TylerMetzger's Explanation

  The SSTF algorithm (Shortest Seek Time First) prioritizes the shortest distance between the current track and a pending request.

    Current Track       Distance to Travel        Shortest Distance
          50           A-5  B-3 C-10 D-2 E-5             D-2
      D - 48           A-7  B-5 C-8      E-3             E-3
      E - 45           A-10 B-8 C-5                      C-5
      C - 40           A-15 B-13                         B-13
      B - 53           A-2                               A-2
      A - 55                    N/A                      N/A
    

• A disk takes 1ms per track seek time, and the head is currently on track 50. Assume it takes 5ms to service a request once the head is at the right track. The following set of requests are pending, given as (ID, track) in order of arrival. How much time does it take to service all the requests if the policy is SSF (aka SSTF)? Requests: (A,55)(B,53)(C,40)(D,48)(E,45)

  • 50ms
    TylerMetzger's Explanation

    The SSTF algorithm (Shortest Seek Time First) prioritizes the shortest distance between the current track and a pending request.

    Current Track       Distance to Travel        Shortest Distance
          50           A-5  B-3 C-10 D-2 E-5             D-2
      D - 48           A-7  B-5 C-8      E-3             E-3
      E - 45           A-10 B-8 C-5                      C-5
      C - 40           A-15 B-13                         B-13
      B - 53           A-2                               A-2
      A - 55                    N/A                      N/A 
    

    To calculate the total time add the travel distance times the seek time per track plus the total tracks serviced times service time per track:

    (2+3+5+13+2) tracks * 1 ms/track + 5 tracks * 5ms/track = 25ms (seek time) + 25ms (service time) = 50ms
    

• A disk takes 1ms per track seek time, and the head is currently on track 70. Assume it takes 5ms to service a request once the head is at the right track. The following set of requests are pending, given as (ID, track) in order of arrival. What is the order in which the requests are serviced if the Elevator algorithm is used and the current direction is down? Requests: (A,80)(B,75)(C,82)(D,90)(E,45)

  • EBACD
  TylerMetzger's Explanation

  The elevator algorithm (a.k.a. SCAN algorithm) moves in a given direction, servicing the requests in its path. Once reaching the final request in that direction, it reverses its direction and follows the same pattern.

  Next Served       Distance to Travel        Current Direction
    E - 45                 25                       Down
    B - 75                 30                         Up
    A - 80                  5                         Up
    C - 82                  2                         Up
    D - 90                  8                        N/A
  

• A disk takes 1ms per track seek time, and the head is currently on track 50. Assume it takes 5ms to service a request once the head is at the right track. The following set of requests are pending, given as (ID, arrival time in ms, track). When is the last request finished if the policy is SSF (aka SSTF)? Requests: (A,3,55)(B,4,53)(C,8,40)(D,10,48)(E,32,45)

  • 53 ms
  TylerMetzger's Explanation

  The SSTF algorithm (Shortest Seek Time First) prioritizes the shortest distance between the current track and a pending request. The SSTF algorithm is non-preemptive, that is, if a new request appears that is closers to the current track then the current request being seeked, it will not interrupt the current seek, and will have to wait to be serviced after the current request.

    Time Quantumn      Current Action      Current Track       Distance to Travel        Shortest Distance
        0-3               Waiting                50           A-5                               A-5
        3-8            Seek Request A         50-55                   N/A                       N/A
        8-13             Service A               55               B-2 C-15 D-7                  B-2
       13-15           Seek Request B         55-53                   N/A                       N/A
       15-20             Service B               53                   C-13 D-5                  D-5
       20-25           Seek Request D         53-48                   N/A                       N/A
       25-30             Service D               48                   C-8                       C-8
       30-38           Seek Request C         48-40                   N/A                       N/A
       38-43             Service C               40                            E-5              E-5
       43-48           Seek Request E         40-45                   N/A                       N/A
       48-53             Service E               45                   None                      None
     

• A disk takes 1ms per track seek time, and the head is currently on track 50. Assume it takes 5ms to service a request once the head is at the right track. The following set of requests are pending, given as (ID, arrival time in ms, track). What is the order in which the requests are serviced if the policy is SSF (aka SSTF)? Requests: (A,3,55)(B,4,53)(C,8,40)(D,10,48)(E,32,45)

  • ABDCE
  TylerMetzger's Explanation

  The SSTF algorithm (Shortest Seek Time First) prioritizes the shortest distance between the current track and a pending request. The SSTF algorithm is non-preemptive, that is, if a new request appears that is closers to the current track then the current request being seeked, it will not interrupt the current seek, and will have to wait to be serviced after the current request.

    Time Quantumn      Current Action      Current Track       Distance to Travel        Shortest Distance
        0-3               Waiting                50           A-5                               A-5
        3-8            Seek Request A         50-55                   N/A                       N/A
        8-13             Service A               55               B-2 C-15 D-7                  B-2
       13-15           Seek Request B         55-53                   N/A                       N/A
       15-20             Service B               53                   C-13 D-5                  D-5
       20-25           Seek Request D         53-48                   N/A                       N/A
       25-30             Service D               48                   C-8                       C-8
       30-38           Seek Request C         48-40                   N/A                       N/A
       38-43             Service C               40                            E-5              E-5
       43-48           Seek Request E         40-45                   N/A                       N/A
       48-53             Service E               45                   None                      None
     

• A disk takes 1ms per track seek time, and the head is currently on track 70. Assume it takes 5ms to service a request once the head is at the right track. The following set of requests are pending, given as (ID, arrival time in ms, track). What is the order in which the requests are serviced if the Elevator algorithm is used an the current direction is down? Requests: (A,0,80)(B,4,75)(C,12,82)(D,20,90)(E,32,45)

  • ACDBE
  TylerMetzger's Explanation

  The elevator algorithm (a.k.a. SCAN algorithm) moves in a given direction, servicing the requests in its path. Once reaching the final request in that direction, it reverses its direction and follows the same pattern. The elevator algorithm is non-preemptive, that is, if a new request appears that is closers to the current track then the current request being seeked, it will not interrupt the current seek, and will have to wait to be serviced after the current request.

    Time Quantumn      Current Action      Next Served       Distance to Travel        Current Direction
           0                Wait              A-80                   10                       Down 
        0-10           Seek Request A         N/A                    N/A                       Up
       10-15             Service A            C-82                    2                        Up
       15-17           Seek Request C         N/A                    N/A                       Up
       17-22             Service C            D-90                    8                        Up
       22-30           Seek Request D         N/A                    N/A                       Up
       30-35             Service D            B-75                   15                       Down
       35-50           Seek Request B         N/A                    N/A                      Down
       50-55             Service B            E-45                   30                       Down
       55-85           Seek Request E         N/A                    N/A                      Down
       85-90             Service E            None                   None                     Down
    

• A disk takes 1ms per track seek time, and the head is currently on track 70. Assume it takes 5 ms to service a request once the head is at the right track. The following stream of requests arrive, given as (ID, arrival time in ms, track). When is the last request finished if the Elevator algorithm is used and the current direction is down? Requests: (A,0,80)(B,4,75)(C,12,82)(D,20,90)(E,32,45)

  • 90 ms
  nihamaity's Explanation

  To A from current: 80-70 = 10, plus 5 ms to service request: 10 + 5 = 15 ms. To C from A: 82-80 = 2, plus 5 ms to service request: 2 + 5 = 7 ms. To D from C: 90-82 = 8, plus 5 ms to service request: 8 + 5 = 13 ms. To B from D: 90-75 = 15, plus 5 ms to service request: 15 + 5 = 20 ms. To E from B: 75-45 = 30, plus 5 ms to service request: 30 + 5 = 35 ms. Add all times to get the time of when the last request is finished: 15 + 7 + 13 + 20 + 35 = 90 ms.

11 IO Quiz.md

Quiz 11 IO

• Suppose you have a harddrive that spins at 9000 RPM, and has 80 sectors of 512 bytes each on a particular track. If the head is already in position when a request for a single sector of that track is serviced, what is the expected effective data rate to get the data into the controller's buffer? Give the answer in BPS with 3 significant digits.

  • 150,000
  TylerMetzger's Explanation

  The expected data rate in bytes per second can be found by dividing the bytes per sector by the total time allocated to a given sector.

    512 bytes/sector /  ? sec/sector
    

  To find the total seconds per sector you add the average time it takes to find a sector and the time spent on a single sector. Average rotational latency or average seek time averages the best case scenario and worst case scenario for seek time. Best case scenario, the head is in the right place, worst case scenario the head needs to make a full rotation before finding the right place.

    9000 RPM = 150 rotations/sec = 1/150 secs/rotation
    Best Case: 0 rotations = 0 secs/sector
    Worst Case: 1 rotation = 1/150 secs/sector
    Average Seek Time: (0 secs/sector + 1/150 secs/sector) / 2 = 1/300 secs/sector
    

  To find the time spent on a single sector think how 1 rotation covers 1 track. In this case, a single track holds 80 sectors. So 1 sector takes 1/80 of a rotation.

    9000 RPM = 150 rotations/sec = 1/150 secs/rotation
    1 rotation/track * 1/80 tracks/sector = 1/80 rotations/sector
    1/150 secs/rotation * 1/80 rotations/sector = 1/12000 secs/sector
    

  Now that we have our average seek time and our time spent on a sector, we can calculate total time allocated to a sector. Which is as simple as adding them. We can also bring back our original equation and plug in the question mark.

        512 bytes/sector /  ? sec/sector
        512 bytes/sector / (1/300 secs/sector (average seek time) + 1/12000 secs/sector (time spent on a sector))
        512 bytes/sector / 41/12000 sec/sector
        512 bytes/sector * 12000/41 sectors/sec = 149853 bytes/sec ≈ 150000 bytes/sec (3 sig figs)
    

• Suppose you have a hard drive that spins at 9000 RPM, and has 100 sectors of 512 bytes each on a particular track. If the head is already in position when a request for two adjacent sectors of that track is serviced, what is the expected effective data rate to get the data into the controller's buffer? Give the answer in Bps, with 3 significant digits.

  • 301, 000
  TylerMetzger's Explanation

  The expected data rate in bytes per second can be found by dividing the bytes per sector by the total time allocated to a given sector. Since the two sectors are adjacent, it essentially doubles the bytes per sector from 512 to 1024 (technically this isn't true, but this simplification helps calculations. This only works since they are adjacent).

    1024 bytes/sector /  ? sec/sector
    

  To find the total seconds per sector you add the average time it takes to find a sector and the time spent on a single sector. Average rotational latency or average seek time averages the best case scenario and worst case scenario for seek time. Best case scenario, the head is in the right place, worst case scenario the head needs to make a full rotation before finding the right place.

    9000 RPM = 150 rotations/sec = 1/150 secs/rotation
    Best Case: 0 rotations = 0 secs/sector
    Worst Case: 1 rotation = 1/150 secs/sector
    Average Seek Time: (0 secs/sector + 1/150 secs/sector) / 2 = 1/300 secs/sector
    

  To find the time spent on a single sector think how 1 rotation covers 1 track. In this case, a single track holds 100 sectors. So a sector takes 1/100 of a rotation.

    9000 RPM = 150 rotations/sec = 1/150 secs/rotation
    1 rotation/track * 1/100 tracks/sector = 1/100 rotations/sector
    1/150 secs/rotation * 1/100 rotations/sector = 1/15000 secs/sector
    

  Now that we have our average seek time and our time spent on a sector, we can calculate total time allocated to a sector. Which is as simple as adding them. We can also bring back our original equation and plug in the question mark.

        1024 bytes/sector /  ? sec/sector
        1024 bytes/sector / (1/300 secs/sector (average seek time) + 1/15000 secs/sector (time spent on a sector))
        1024 bytes/sector / 51/15000 sec/sector
        1024 bytes/sector * 15000/51 sectors/sec = 301176 bytes/sec ≈ 301000 bytes/sec (3 sig figs)
    

• The IBM 1402 Card Reader could read 800 cards per minute. Each card had 80 columns, each of which could hold one byte in EBCDIC. What was the approximate data rate of this machine in bytes/second (round to the nearest integer)

  • 1,067
  TylerMetzger's Explanation

  To get the machine's data rate measure how many cards it can read and how much data there is per card. A helpful tip to do these kind of problems if you're stuck is to look at the units and try to envision going from the given units (i.e. cards/min) to the end units (i.e. bytes/sec).

      800 cards/min * 1/60 min/sec = 13.333... cards/sec
      80 columns/card * 1 byte/column = 80 bytes/card
      13.333... cards/sec * 80 bytes/card ≈ 1067 bytes/second
    

• A typical US Keyboard has a total of 104 keys. If CTL, ALT, ALT2, and SHIFT may be used in any combination to modify any of the remaining keys, how many character codes can be generated, asssuming there is no distinction between left and right versions of these four modifier keys (they all have two versions) but there is a distinction between all other keys (e.g., the key labeled 1 above the Q key and the 1 key on the numeric keypad are different)?

  • 1,536
  TylerMetzger's Explanation

  To find total number of character codes multiply the number of key combinations (i.e. holding CTL, ALT, and ALT2) and the number of character keys (i.e. the 'H' key). First let's find the number of character keys. Subtract the number of modifier keys (CTL, ALT, ALT2, and SHIFT) from the total number of keys. Remember, we're told that there are two versions of each modifier key.

    104 total keys -  4 left modifier keys - 4 right modifier keys = 96 character keys
    

  Next, we should calculate how many modifiers there, that is, how many modifier key combinations can there be. Combinations can be found by taking 2 to the power of the number of modifiers. Since the left and right modifiers are not distinct, we only have 4 different unique modifiers.

    2^4 modifier keys = 16 different modifications (including holding no keys at all)
    

  Finally, multiply the number of character keys by the number of modifications to find the total number of character codes.

    96 character keys * 16 modifications = 1,536 character codes
    

• In Linux and Unix, the type of disk is determined by the _____ device number, while the particular volume is identified by the _____ device number.

  • major, minor
  TylerMetzger's Explanation

  All block and character drivers registered with the kernel have an associated major number that tells the kernel what kind of device it is. The major number is an offset in a kernel device driver table so a major number of say 36 will tell the kernel that device is the same as whatever is in entry 36 of the table. The minor number is not used by the kernel, it is only used to define special characteristics of the device to its driver.

• The _____ codes passed from the keyboard to the driver are converted to character codes using a _____.

  • scan
  • keymap

• The IBM nine-track tapes that became the industry standard for storage for three decades had several sizes , the most common being 2400 feet. The high density version stored data at 1600 bits/inch/track. If the whole tape (not including the parity track) could be used for data storage , how much raw data could one of these tapes hold?(Round to the nearest MB using decimal MB not binary MB)

  • 46
  TylerMetzger's Explanation

  Let's look at the information give, the IBM tapes hold 9 track, each track is 2400 feet, and data is stored at a rate of 1600 bits per inch for each track (this piece is worded awkwardly in the question). We're also told that the tape has a parity track, thus the number of tracks that can actually hold data is 8. Putting all this information in an equation we get:

      8 tracks * 1600 bits/inch / track = 12800 bits/inch
      2400 feet * 12 inch/foot = 28800 inches
      28800 inches * 12800 bits/inch = 368640000 bits
      368640000 bits = 46080000 bytes ≈ 46 MB
    

12 Deadlock Quiz.md

Quiz 12 Deadlock

• In the following resource allocation scenario, which process(es) can be marked in the third iteration of the loop (but not the first or second iteration) in the Safe State Checking algorithm? (Check all)
  Exist = (5,4,5,3,2)
  Max:

  Proc	Res 1	Res 2	Res 3	Res 4	Res 5
  A	2	3	2	1	0
  B	2	1	1	0	1
  C	1	2	2	1	1
  D	2	1	1	1	1
  E	1	3	3	2	1

  Has:

  Proc	Res 1	Res 2	Res 3	Res 4	Res 5
  A	1	0	1	0	0
  B	1	1	0	0	1
  C	1	2	0	1	0
  D	0	1	1	0	1
  E	1	0	1	2	0

  • • A
    • B
    • C
    • D
    • E
    TylerMetzger's Explanation

    The Safe State Checking algorithm (a.k.a. Banker's Algorithm) is a deadlock avoidance algorithm. We are given a max allocation matrix, a current allocation matrix (has), and the total existing resources. We first want to find our needed allocation matrix. To find the needed allocation matrix you must first use matrix subtraction using the formula: Max - Has = Needed.

    Need:

    Proc	Res 1	Res 2	Res 3	Res 4	Res 5
    A	1	3	1	1	0
    B	1	0	1	0	0
    C	0	0	2	0	1
    D	2	0	0	1	0
    E	0	3	2	0	1

    We then need to find our available resources. First find the sum total of each column in our 'has' matrix. I'll put that in an array so we get (4,4,3,3,2). Use the formula Exist - Allocated = Available to find the array of available resources.

      Exists - Allocated = Available
      (5,4,5,3,2) - (4,4,3,3,2) = (1,0,2,0,0)
      

    Using our need matrix and our available resources we can mark processes. Set the available resources array next to each row in the need matrix. If every entry in the need array row is less than or equal to the following entry in the available resources array, then that process can be marked. For example, let's say process X in the need matrix is (1,0,0,0,0) and the available resources are (1,0,2,0,0) then process X can be marked. If process Y in the need matrix is (1,0,0,1,0), then it cannot be marked since the 4th entry in process Y (1) is greater than the 4th entry in the available array (0).

    Need:

    Proc	Res 1	Res 2	Res 3	Res 4	Res 5	Available
    A	1	3	1	1	0	(1,0,2,0,0)
    B	1	0	1	0	0	(1,0,2,0,0)
    C	0	0	2	0	1	(1,0,2,0,0)
    D	2	0	0	1	0	(1,0,2,0,0)
    E	0	3	2	0	1	(1,0,2,0,0)

    In this case, the only process that can be marked in the first iteration is process B. After marking a process, you must recalculate the new available resources. We do this by adding the marked process' array to the available array. (1,0,1,0,0) + (1,0,2,0,0) = (2,1,2,0,1). Now that we have our new available array, we can check if any more process' can be marked

    Need:

    Proc	Res 1	Res 2	Res 3	Res 4	Res 5	Available
    A	1	3	1	1	0	(2,1,2,0,1)
    -	-	-	-	-	-	-
    C	0	0	2	0	1	(2,1,2,0,1)
    D	2	0	0	1	0	(2,1,2,0,1)
    E	0	3	2	0	1	(2,1,2,0,1)

    Now we could mark process C. Follow the same steps to find the new available `(0,0,2,0,1) + (2,1,2,0,1) = (3,3,2,1,1)` Repeat the process and check if any new processes can be marked.

    Need:

    Proc	Res 1	Res 2	Res 3	Res 4	Res 5	Available
    A	1	3	1	1	0	(3,3,2,1,1)
    -	-	-	-	-	-	-
    -	-	-	-	-	-	-
    D	2	0	0	1	0	(3,3,2,1,1)
    E	0	3	2	0	1	(3,3,2,1,1)

    At this point, we can now mark all other processes. This is now our third iteration, and as we saw, we could not mark these processes until this point. Some things to note for dealing with this question in the future is that if multiple processes can be marked in the same iteration, that means you must account for different possible values of the available array. In our case (and probably most if the exam is nice), each iteration until the last one will have only one possible process to mark, but if not, following some process order may force say process X to be marked only until the 3rd iteration, while following another process order may allow it to be marked on the 2nd iteration due to higher values in the available array.

• Consider the following scenario in a system with 5 resource types. Which process(es) can be marked on the first iteration of the Safe State Checking Algorithm? (Check all)
  Exist = (5,4,5,3,2)
  Max:

  Proc	Res 1	Res 2	Res 3	Res 4	Res 5
  A	2	3	2	1	0
  B	2	1	1	0	1
  C	1	2	2	1	1
  D	2	1	1	1	1
  E	1	3	3	2	1

  Has:

  Proc	Res 1	Res 2	Res 3	Res 4	Res 5
  A	1	0	1	0	0
  B	1	1	0	0	1
  C	1	2	0	1	0
  D	0	1	1	0	1
  E	1	0	1	2	0

  • • A
    • B
    • C
    • D
    • E
    TylerMetzger's Explanation

    The Safe State Checking algorithm (a.k.a. Banker's Algorithm) is a deadlock avoidance algorithm. We are given a max allocation matrix, a current allocation matrix (has), and the total existing resources. We first want to find our needed allocation matrix. To find the needed allocation matrix you must first use matrix subtraction using the formula `Max - Has = Needed`.

    Need:

    Proc	Res 1	Res 2	Res 3	Res 4	Res 5
    A	1	3	1	1	0
    B	1	0	1	0	0
    C	0	0	2	0	1
    D	2	0	0	1	0
    E	0	3	2	0	1

    We then need to find our available resources. First find the sum total of each column in our 'has' matrix. I'll put that in an array so we get (4,4,3,3,2). Use the formula Exist - Allocated = Available to find the array of available resources.

      Exists - Allocated = Available
      (5,4,5,3,2) - (4,4,3,3,2) = (1,0,2,0,0)
      

    Using our need matrix and our available resources we can mark processes. Set the available resources array next to each row in the need matrix. If every entry in the need array row is less than or equal to the following entry in the available resources array, then that process can be marked. For example, let's say process X in the need matrix is (1,0,0,0,0) and the available resources are (1,0,2,0,0) then process X can be marked. If process Y in the need matrix is (1,0,0,1,0), then it cannot be marked since the 4th entry in process Y (1) is greater than the 4th entry in the available array (0).

    Need:

    Proc	Res 1	Res 2	Res 3	Res 4	Res 5	Available
    A	1	3	1	1	0	(1,0,2,0,0)
    B	1	0	1	0	0	(1,0,2,0,0)
    C	0	0	2	0	1	(1,0,2,0,0)
    D	2	0	0	1	0	(1,0,2,0,0)
    E	0	3	2	0	1	(1,0,2,0,0)

• The following system state is a _____ state.
  Exist = (5,4,5,3,2)
  Max:

  Proc	Res 1	Res 2	Res 3	Res 4	Res 5
  A	2	3	2	1	0
  B	2	1	1	0	1
  C	1	2	2	1	1
  D	2	1	1	1	1
  E	1	3	3	2	1

  Has:

  Proc	Res 1	Res 2	Res 3	Res 4	Res 5
  A	1	0	1	0	0
  B	1	1	0	0	1
  C	1	2	0	1	0
  D	0	1	1	0	1
  E	1	0	1	2	0

  • safe
  TylerMetzger's Explanation

  This system is considered safe because there is an existing order in which you can mark the processes so that each one gets properly allocated resources. An example of a possible order would be BCADE, the other questions go more in depth on actually working out the above system. If a system were unsafe, then no such order would exist, which would mean that the existing resources are not enough for a process' needed resources at any point.

• In the following resource allocation scenario, which process(es) can be marked the second iteration through the loop (but not the first iteration) in the Safe State Checking algorithm? (Check all) Exist = (5,4,5,3,2)
  Max:

  Proc	Res 1	Res 2	Res 3	Res 4	Res 5
  A	2	3	2	1	0
  B	2	1	1	0	1
  C	1	2	2	1	1
  D	2	1	1	1	1
  E	1	3	3	2	1

  Has:

  Proc	Res 1	Res 2	Res 3	Res 4	Res 5
  A	1	0	1	0	0
  B	1	1	0	0	1
  C	1	2	0	1	0
  D	0	1	1	0	1
  E	1	0	1	2	0

  • • A
    • B
    • C
    • D
    • E
    TylerMetzger's Explanation

    The Safe State Checking algorithm (a.k.a. Banker's Algorithm) is a deadlock avoidance algorithm. We are given a max allocation matrix, a current allocation matrix (has), and the total existing resources. We first want to find our needed allocation matrix. To find the needed allocation matrix you must first use matrix subtraction using the formula Max - Has = Needed.

    Need:

    Proc	Res 1	Res 2	Res 3	Res 4	Res 5
    A	1	3	1	1	0
    B	1	0	1	0	0
    C	0	0	2	0	1
    D	2	0	0	1	0
    E	0	3	2	0	1

    We then need to find our available resources. First find the sum total of each column in our 'has' matrix. I'll put that in an array so we get (4,4,3,3,2). Use the formula Exist - Allocated = Available to find the array of available resources.

      Exists - Allocated = Available
      (5,4,5,3,2) - (4,4,3,3,2) = (1,0,2,0,0)
      

    Using our need matrix and our available resources we can mark processes. Set the available resources array next to each row in the need matrix. If every entry in the need array row is less than or equal to the following entry in the available resources array, then that process can be marked. For example, let's say process X in the need matrix is (1,0,0,0,0) and the available resources are (1,0,2,0,0) then process X can be marked. If process Y in the need matrix is (1,0,0,1,0), then it cannot be marked since the 4th entry in process Y (1) is greater than the 4th entry in the available array (0).

    Need:

    Proc	Res 1	Res 2	Res 3	Res 4	Res 5	Available
    A	1	3	1	1	0	(1,0,2,0,0)
    B	1	0	1	0	0	(1,0,2,0,0)
    C	0	0	2	0	1	(1,0,2,0,0)
    D	2	0	0	1	0	(1,0,2,0,0)
    E	0	3	2	0	1	(1,0,2,0,0)

    In this case, the only process that can be marked in the first iteration is process B. After marking a process, you must recalculate the new available resources. We do this by adding the marked process' array to the available array. (1,0,1,0,0) + (1,0,2,0,0) = (2,1,2,0,1). Now that we have our new available array, we can check if any more process' can be marked

    Need:

    Proc	Res 1	Res 2	Res 3	Res 4	Res 5	Available
    A	1	3	1	1	0	(2,1,2,0,1)
    -	-	-	-	-	-	-
    C	0	0	2	0	1	(2,1,2,0,1)
    D	2	0	0	1	0	(2,1,2,0,1)
    E	0	3	2	0	1	(2,1,2,0,1)

• What type of deadlock handling method is each of the following?

  • Banker's Algorithm: Deadlock avoidance
  • Total ordering of resource types: Deadlock prevention
  • Preemption, rollback, or killing blocked process(es): Deadlock detection and recovery
  • Full speed ahead an hope for the best: Ostrich algorithm
  TylerMetzger's Explanation

  • Banker's Algorithm avoids deadlock by testing a possible allocation of resources and determining if it will cause deadlock. It accomplishes this by using the above explained methods of testing resource allocation.
  • By ordering resource types, you limit the number of ways a process can request a resource. In the deadlock condition of circular wait, a chain of processes are waiting for a previous process to finish using a resource, by strictly ordering them you completely avoid this process, but at the cost of flexibility. Some systems become impossible to strictly order, but this method completely avoids the possibility of deadlock altogether.
  • If deadlock occurs, you may block the process, put it back to a state pre-deadlock, or just kill it altogether. This may only occur after deadlock.
  • Much like an ostrich sticking its head in the ground, you just ignore all possible deadlock vulnerabilties.

13 Security Quiz.md

Quiz 13 Security

• If a process in a MAC system has label <Secret, {Homeland Security}> files with which labels is it able to read, assuming the usual label meanings? (Check all)

  • • <Top Secret, {Homeland Security}>
    • <Confidential, {Homeland Security, Submarines}>
    • <Confidential, {}>
    • <Secret, {Homeland Security}>

• Which of the following are strengths of capability lists? (Check all)

  • • They make it easy to determine which domains can access an object and how.
    • They make it easy to revoke access rights to an object.
    • They make it easy to determine which objects a domain can access and how.
    • They store the ACM efficiently.

• Which of the following are strengths of ACLs?

  • • They make it easy to determine which domains can access an object and how.
    • They make it easy to revoke access rights to an object.
    • They make it easy to determine which objects a domain can access and how.
    • They store the ACM efficiently.

• What causes the greatest amount of loss to data?

  • User Errors

• What is the primary drawback of the Access Control Matrix as an implementation?

  • It is too large

• In what type of access control system are labels on objects and subjects used determine who can access it and how?

  • MAC

• In what type of access control system does the owner of an object determine who can access it and how?

  • DAC

14 Security2 Quiz.md

Quiz 14 Security2

• With a good symmetric cyptosystem (Check all)

  • • given only ciphertext C=E(K,P) it is difficult to obtain the corresponding plaintext P
    • given only ciphertext C=E(K,P) it is difficult to obtain the key K
    • given only plaintext P it is difficult to obtain the ciphertext C=E(K,P)
    • given the encryption key K it is difficult to obtain the plaintext P from ciphertext C=E(K,P)

• With a good asymmetric cryptosystem used in the normal way, for a member of the public (Check all)

  • • given ciphertext C it is difficult to obtain the corresponding plaintext P
    • given plaintext P it is difficult to obtain the ciphertext C
    • given the encryption key K it is difficult to obtain the plaintext P from ciphertext C
    • given only ciphertext C it is difficult to obtain the decryption key K'

• If you are using biometric authentication to restrict access to extremely dangerous pathogens in a biomedical research facility, what modification to the default settings of the authentication system would be wise?

  • Modify the acceptance threshold to make the FAR as near to zero as possible

• The key difference between a virus and a worm is:

  • a virus must be attached to another file

• Which of the following are drawbacks to password-based authentication? (Check all)

  • • Not all users may be able to enroll.
    • Passwords may change with physical condition.
    • Passwords may be misplaced or lost
    • Passwords may be forgotten.
    • Passwords may be guessed.
    • Passwords may be observed.
    • Users may be reluctant to use a password.
    • Passwords may be used for purposes other than authentication.

• Which of the following are drawbacks to biometric authentication (under normal circumstances)? (Check all)

  • • Not all users may be able to enroll.
    • Biometrics may change with physical condition.
    • Biometric keys may be lost.
    • Biometrics may be forgotten.
    • Users may not want to submit to biometric evaluation.
    • Biometrics may be used for purposes other than authentication.

changes.md

Contribution log

• Initialized Repo
• Initial Contributions from LukaAntoljak, nihamaity, and qingyuan.1016
• Quiz 9 explanations adde by 6XAM
• Quiz 14 added by qingyuan.1016
• Quiz 10, 11, & 12 explanations added by TylerMetzger
• Quiz 11 question added by qingyuan.1016
• Quiz 11 added a question by sudeep
• Quiz 10 question added by nihamaity

Modified

https://gist.github.com/LukaAntoljak/93b48b96241f8556a18ffa69168655d2
Added missing answers to quiz 10/11

Added 2 questions along with their correct answers that were on my version of quiz 9

https://gist.github.com/595456852/0b674f78bc219d6590086cd1b109e779
Added Quiz 14 and its answers

https://gist.github.com/TylerMetzger/81884f1b77403b2d8de1f6ff031e33ed
Added explanations for all answers to quiz 10.

https://gist.github.com/595456852/0b674f78bc219d6590086cd1b109e779
Added missing question to Quiz 11

https://gist.github.com/sudeepsubedi/5a5db46e391aec9f0bcaa0f05eb813f7
Added a question to Quiz 11

https://gist.github.com/nihamaity/17b84dff9c56f45347030baa1738d616
Added a question and explanation (feel free to improve) to Quiz 10

https://gist.github.com/TylerMetzger/59e935403d3c5bdf4f4c3b4e8ea30484
Added explanations for quiz 11, not sure how accurate the first two are so let me know if they're wrong. The rest should be good.

Also added explanations for quiz 12 in the above link as well.