CSC 330 - Exam Two

Question 1

Describe race conditions

Answer 1

Race conditions: when two or more processes attempt to share the same resource simultaneously. The process that writes to the resource last will succeed.

Example:
• Process A reads variable X and stores it in variable Y
• Process B reads variable X and stores it in variable Z
• Process A updates Y and stores it back into X
• Process B updates Z and stores it back into X
• Process B wins

Question 2

Describe critical sections

Answer 2

Critical sections: the code in a process that accesses and uses a shared resource. Every process that needs to access a shared resource has its own critical section. It is a technique to avoid race conditions. There are four conditions for a proper solution:
• Only one process can be executing its critical section at a time (mutual exclusion)
• No assumptions can be made about speed or number of CPUs for the entire system
• No process outside a critical section can block another process
• No process should have to wait indefinitely to enter its critical section

Question 3

Describe semaphores

Answer 3

Semaphores are integer variables; they can be binary semaphores (which have a value of 0 or 1) or counting semaphores (which can have any integer value). They are manipulated with two atomic operations – Wait (P) and Signal (V).

• Wait – If the semaphore value is greater than 0, decrement it and continue. If the semaphore value is 0, wait until it becomes 1, decrement it and continue.
• Signal – Add 1 to the value of the semaphore.

Question 4

Describe mutexes

Answer 4

Mutexes are simplified semaphores; they are equivalent to the binary semaphore. They can be locked or unlocked.

Question 5

Describe monitors

Answer 5

Monitors are programming language constructs that implement mutual exclusion; they are an encapsulation of data and methods that manipulate the data.

Only one process can be executing a monitor method at any time. If a process is in the monitor and another calls one of the methods, the second process will be suspended until the first process completes. Processes inside the monitor must leave the monitor before doing anything that will cause a suspend.

Monitors are more reliable than semaphores because the compiler handles the mutual exclusion.

Question 6

Name and fully explain the four necessary and sufficient conditions for deadlock

Answer 6

• Mutual Exclusion – Each resource is available or allocated to exactly one process
• Hold and wait – A process holding resources can request and wait for additional resources
• Circular wait – A circular chain of processes each holding a resource and waiting for a resource held by the next process in the chain
• No preemption – Resources allocated to a process cannot be forcibly taken away

Deadlock can occur if the four conditions are present simultaneously.

Question 7

Name and fully explain the four ways to prevent deadlock

Answer 7

• Attack mutual exclusion – avoid assigning resources unless absolutely necessary; have few processes that are allowed to request a resource.
• Attack hold and wait – prevent a process from holding one or more resources while requesting other resources at the same time. Require processes to request all of the resources needed at the start. Processes must temporarily release all held resources before requesting new resources.
Problems:
¬ Processes may not know all of the resources needed at the start
¬ Resources will be tied up longer than necessary
• Attack circular wait – allow processes to only have one resource at a time. Globally order the resources and require that a process cannot make a request for a resource that is numbered less than the largest number of a held resource. Processes can request a lower numbered resource if they release higher numbered resources. Typically, there are a lot of resources that would need to be numbered.
• Attack no preemption – taking away some resources can be problematic but daemons can help. Some resources can’t be virtualized in this way.

Deadlock can be prevented if one of the four necessary and sufficient conditions for deadlock are prevented

Question 8

Describe how deadlock can be avoided

Answer 8

Deadlock can be avoided by carefully deciding whether to grant access to an available resource. The idea is to only grant resources that will result in the system staying in a safe state.

• A state is safe if there is a scheduling order that the processes can be run to completion – if the scheduling condition cannot be met, the resource state is unsafe
• The bankers algorithm can be invoked by the OS to check if the current resource-allocation state is a safe state

Question 9

Describe how deadlock can be detected

Answer 9

If there is one resource of each type, you can construct a resource graph, search the graph for cycles and the processes in a cycle are deadlocked

If there are multiple resources of each type, you can use the detection algorithm over the array structures. When the algorithm is done processing, the processes that are unmarked are deadlocked.

Deadlock detection involves maintaining information of the current resource allocation state and invoking an algorithm that uses the information of the resource allocation state to detect if deadlock has occurred.

Question 10

Describe how deadlock can be recovered from

Answer 10

• Preemption – resource is taken away from a process and the process is suspended. When the process that gets the preempted resource completes, the resource is returned to the original process.
• Rollback – The operating system periodically creates a checkpoint for each process; many checkpoints are held per process. When a resource is needed to break a deadlock, one of the processes holding it is rolled back to before it acquired it.
• Killing processes – A process in the deadlock cycle (or not in the deadlock cycle but possessing needed resources) is killed and restarted. Processes killed should be ones that can be restarted without bad effects.

Question 11

Describe what a file system does

Answer 11

Provides users the ability to put data into files and to find and use files that have been previously created. The file management system does not have any knowledge about how the data in a file is organized. The file management system will typically store files in nonvolatile memory.

Files stored will need to be accessed and found again at some later time. A user who wants a file can ask if a file with a certain name exists in a particular folder (directory).

Question 12

Name and describe the file attributes

Answer 12

A file attribute is additional information an operating system keeps about a file

• Size – how much data is stored in a file
• Location – where the file is stored on the computer; which disk it is on
• Type – what kind of data is stored in the file – denoted by the file extension; contents, read-only flag, hidden flag, system flag, archive flag, temporary flag
• Permissions – who can access the file and what they are permitted to do with it
• Creator – who created the file
• Owner – who owns the file
• Time stamps – when the file was created; when it was last modified; when it was last accessed

Question 13

Name and discuss the four ways of implementing files

Answer 13

• Contiguous allocation – files are allocated a contiguous series of blocks on the disk. The last block will typically have waste because files are rarely an even number of blocks long. This is easy to implement – only need to record the size and starting address. it can cause disk fragmentation. Files that increase in size have to be moved to a new and larger space.
• Linked list allocation – the first word of each block of the file contains the address of the next block of the file. The directory only stores the address of the first file block. Sequential access of the file is fine, but random access is slow. Program block reads may need data from multiple disk blocks.
• Linked list allocation with a table – a table in memory with the same number of entries as blocks on the disk. If the first block of a file is stared at location X on the disk, location X in the table stores the location of the second block of the disk. These are called file allocation tables (FAT). Random access is faster because the chain is in memory - not on disk. For large disks, the table is very large.
• I-nodes – an I-node contains file attributes and a list of block addresses (pointers to file blocks). The I-node is a fixed size so the last block address points to a block with more pointers to file blocks.

Question 14

Discuss issues in disk space management

Answer 14

Block size –
•Too small and most files will span multiple blocks.
•Too large and a lot of space will be wasted in the last block of a file.

Free blocks –
•A list of available blocks is kept. While this list can be large, that also means there are a lot of free blocks to hold it.
•Bitmap is kept. One bit per block with one representing a free block.

Disk quotas –
• Limit on how much data a user can store
• Quota table keeps track of hard and soft limits and current usage

Caching –
• Need to maintain file integrity – blocks modified in cache need to be written out to disk.
• Blocks read ahead

Fragmented disks –
• Free space becomes distributed around the disk so file blocks get spread out which reduces performance
• Defragmentation programs help to condense the free space and the blocks of a file

Question 15

Discuss the two causes for disk I/O delays

Answer 15

• Seek time – The time it takes to move the read/write head to the correct track
• Rotational latency – The time it takes for the disk to rotate the correct sector under the read/write head

Question 16

Discuss the four disk scheduling methods and show how they would process a set of disk requests. (Diagrams are in 11.12.15 slides)

Answer 16

These algorithms are needed to minimize seek time

First Come First Served (FCFS)
• Services I/O requests in the order in which they arrive
•Simplest scheduling algorithm

Shortest Seek Time First (SSTF)
•Selects the request closest to the current head position; may cause starvation of some requests

SCAN
• Disk arm starts at one end of the disk and moves toward the other end servicing requests. When there are no more requests in a direction, the head movement is reversed
• Sometimes called the elevator algorithm

Circular SCAN (C-SCAN)
•Requests are always services in one direction.  When there are no more requests in that direction, the read/write head returns to the first track with no requests are serviced in this pass.

Question 17

Discuss the purpose of device controllers

Answer 17

Each physical device has a device controller. The device controllers directly control the devices for the main CPU. All device controllers are able to operate the devices at the same time the main CPU is carrying out some other task. Their purpose is to provide part of the interface between devices and the processor, or function as a bridge between the device and the operating system.

Question 18

Discuss the purpose of device driver software

Answer 18

A device driver is a computer program that operates or controls a particular type of device that is attached to a computer. It provides a software interface to hardware devices, enabling operating systems and other computer programs to access hardware functions without needing to know precise details of the hardware being used. The device specific driver is responsible for translating generic commands from the device driver to manufacturer specific commands for the specific make and model of the device that is in use.

Question 19

Describe the purpose and use of the MPI Send function

Answer 19

MPI Send is a communication routine. It provides the transfer of information. It will send messages to other processes.

It has 5 parameters – MPI::COMM_WORLD.Send(data, amount, type, destination, tag)
• It’s first parameter is an array or the address of a variable being sent.
• The second parameter is the size of the data being sent.
• The third parameter is the type of data that is being sent.
• The fourth parameter is the destination of the send (the rank of the receiver).
• The fifth parameter is the message tag which is an integer indicating what’s being sent.

Question 20

Describe the purpose and use of the MPI Receive function

Answer 20

MPI Receive is a communication routine. It provides the transfer of information. It will receive messages from other processes.

It has 6 parameters – MPI::COMM_WORLD.Recv(data, amount, type, source, tag, status)
• It’s first parameter is an array or the address of a variable being received.
• The second parameter is the size of the data being received.
• The third parameter is the type of data that is being received.
• The fourth parameter is the rank number of the sending process.
• The fifth parameter is the message tag which is an integer indicating what’s being received
• The sixth parameter is a struct object holding information about the received message.

Question 21

Describe the purpose and use of the MPI Broadcast function

Answer 21

The MPI Broadcast function is used for performing collective data distribution tasks. It will broadcast a message to all other processes.

It has four parameters – MPI::COMM_WORLD.Bcast(data, count, type, root)
• It’s first parameter is an array or the address of a variable being sent
• The second parameter is the number of entries in the buffer
• The third parameter is the type of data being sent.
• The fourth parameter is the rank of the broadcast’s root process (an integer)

Question 22

Describe the use of rank to determine what parts of the code are executed by which processes

Answer 22

When a program is run, it can’t be determined which parts of the code were executed by a particular process. Using MPI rank will assign an integer to each process beginning with zero for the parent process and incrementing each time a new process is created. This rank can be thought of as a process’ ID. Utilizing rank with a print statement can make it clear which process is executing which parts of the code.