OS Revision

• Lecture 6 discusses deadlock, starvation, and race conditions in operating systems.

Deadlock

• Deadlock is a situation where two or more threads are blocked indefinitely, each waiting for a resource that is held by another.
• Circular waiting on resources causes deadlock.
• Threads become stuck indefinitely as a result of deadlock.
• An example includes thread T1 holding resource A, and thread T2 holding resource B, with each needing the other's resource.
• Deadlock can be avoided by preventing circular dependencies and using resource allocation protocols.
• Deadlock can be resolved through prevention, detection, or recovery mechanisms.

Starvation

• Starvation occurs when a thread is denied access to resources by the scheduler, often due to higher-priority threads.
• Resource scheduling that prioritizes certain threads over others can cause starvation.
• A thread becomes unable to proceed, leading to delays or failure in operation if it is starved.
• Example: A low-priority thread is never scheduled due to continuously running high-priority threads.
• Fair scheduling policies help ensure all threads are eventually granted resources, resolving starvation.

Race Condition

• Race condition is a situation where the interaction of threads produces buggy results depending on the order instructions are executed.
• Concurrent access to shared resources without proper synchronization causes race conditions.
• Race conditions result in data corruption or unexpected behavior.
• Two threads modifying and reading a shared variable simultaneously without proper synchronization leads to unexpected results.
• Proper synchronization mechanisms, like locks, mutexes, or atomic operations coordinate thread actions and resolve the race conditions.

Seven Cases of Deadlock

• Deadlocks commonly occur when non-sharable and non-preemptable resources are allocated to jobs using the same types of resources.

Deadlocks on File Requests

• Jobs request and hold files during execution, leading to deadlock.
• Example: Two programs, P1 and P2, require two files, F1 and F2.
• A deadlock sequence occurs when P1 accesses and holds F1 and requires F2, while P2 accesses and holds F2 and requires F1.
• The deadlock persists until one program is withdrawn or forcibly removed and its file released.

Deadlocks in Databases

• Occurs when two processes access and lock database records.
• Locking: Technique that utilizes locking out all other users and working within the database.
• Includes locking the entire database, a subsection, or an individual record.
• Example: Processes P1 and P2 both need to update records R1 and R2.
• A deadlock sequence: P1 accesses and locks R1, P2 accesses and locks R2, P1 requests R2 (locked by P2), and P2 requests R1 (locked by P1).

Race between processes (Databases)

• Race occurs when locking is not used.
• Causes an inaccurate final version of data, depending on the process execution order.

Deadlocks in Dedicated Device Allocation

• Involves a limited number of dedicated devices.
• Example: Two programs, P1 and P2, each need two tape drives, but there are only two in the system.
• A deadlock occurs when P1 requests and gets tape drive 1, P2 requests and gets tape drive 2, P1 then requests tape drive 2 but is blocked, and P2 requests tape drive 1 but is blocked.

Deadlocks in Multiple Device Allocation

• Involves several processes requesting and holding dedicated devices.
• Example: Three programs (P1, P2, P3) and three dedicated devices (tape drive, printer, plotter).
• Deadlock sequence: P1 gets tape drive, P2 printer, P3 plotter; P1 requests printer, P2 plotter, and P3 requests tape drive (all blocked).

Deadlocks in Spooling

• Involves a virtual device where a dedicated device (printer) is made sharable through spooling.
• Spooling: the disk accepts output from users using the spooling process which is temporary storage for output until the printer accepts job data.
• A deadlock sequence occurs when the printer needs all job output before printing.
• The spooling system fills the disk space, but no one job has its entire print output in the spool area, which causes all jobs to be partially completed and results in deadlock.

Deadlocks in a Network

• Occurs from lack of network protocols controlling network message flow.
• Example: Seven computers on a network, each on different nodes.
• Direction of arrows indicates message flow.
• Deadlock occurs when all available buffer space fills up.

Deadlocks in Disk Sharing

• Competing processes send conflicting commands for disk access.
• Scenario: Two processes, one at cylinder 20 and one at cylinder 310.
• The deadlock sequence results when neither I/O request can be satisfied, and the device puts the request on hold while trying to fulfill the other request, leading to livelock.

Conditions for Deadlock

• Deadlock/livelock occurs when mutual exclusion, resource holding, no preemption, and circular wait conditions occur simultaneously.
• All four conditions have to happen for deadlock
• Removing one condition allows solving deadlocks

Mutual Exclusion

• Each resource is either available or assigned exclusively to one process.

Resource Holding (Hold and Wait)

• A process holding a resource requests another resource.

No preemption

• Resources previously granted cannot be forcibly taken away and must be released by the process holding them without interruption.

Circular Wait

• There must be a circular chain of two or more processes, each waiting for a resource held by the next member in the chain.

Consecutive Allocation Policy

• Max Active Jobs = Total Tape devices / Drives per job
• Min Idle devices = Total Drives - Used drives

Banker's Algorithm

• Deadlock avoidance algorithm
• Ensures the system never enters an unsafe state

Lecture 7: Differentiating Multiprogramming and Multiprocessing

Definitions, reader-writer problems, and applications of concurrent programming

Parallel Processing Definition

• Multiprocessing involves two or more processors working together.
• Multiple CPUs executing instructions simultaneously.
• The processor manager coordinates and synchronizes the activities of each processor.

Development of Multiprocessing

• Enhances throughput and increases computing power.
• Provides increased reliability, as one CPU can take over if another fails.
• Allows faster processing by processing instructions simultaneously.

Three Levels of Multiprocessing

• Job Level: Each job has its own processor - no explicit synchronization required.
• Process Level: Unrelated processes are assigned to available processors - moderate synchronization.
• Thread Level: Threads are assigned to available processors - requires high synchronization.

Readers and Writers Problem

• Involves two process types that need to access a shared resource where Mutual exclusion between readers and writers is ensured.
• The resource is given to all readers if no writers are processing
• The Resource is given to a single writer when there are no readers or other writers

Applications of Concurrent Programming Equation

• A = 3 * B * C + 4 / (D + E) ** (F – G)
• The exponent is computed first.
• With concurrent processing, the computation occurs in as little as four steps, improving the performance.

Lecture 8

• Discusses the advantages and disadvantages of dedicated vs shared devices, magnetic disk drive access times, device handler seek strategies, and algorithm goals.

Dedicated Devices

• Devices assigned to one job at a time for the duration it's active.
• These devices have low efficiency.

Shared Devices

• Assigned to multiple processes.
• Direct access storage devices
• Processes share DASD simultaneously
• Device Manager supervises interleaving

Magnetic Disk Drive Access Time Factors

• Seek time (slowest): Time to position the read/write head on the track.
• Search time: Rotational delay as the disk rotates until the desired record is under the read/write head.
• Transfer time (fastest): Time to transfer data from secondary storage to main memory.

Device Handler Seek Strategies

• Predetermined device handler which sets device processing order.
• Types: First-come, first-served (FCFS), shortest seek time first (SSTF), SCAN.
• Scheduling algorithm goals: Minimize arm movement, mean response time, variance in response time.

FCFS (Device Handling)

• On average tends to not meets three seek strategy goals.
• It can cause extensive movement of the arm.

Lectures 9 & 10

• Address access cotnrol including drawing access points and security

Access Control Matrix

• The system is simpler to implement if there a limited number of users and files.
• Disadvantages: As the system expands the matrix may need vast amounts of memory and space wasted on null entries.

Access Control Lists

• Access is Granted based on user names. Shorten the list by categorizing users.
• Categories: System, Owner, Group, World etc

Capability Lists

• Every user shows which files they can access. Can control devices as well as files

• Most common to use

• R-Read Access

• W-Write Access

• E-Execute Access

• D-Delete Access

Noncontiguous Storage

• File Storage using matrix diagrams

Contiguous storage

• Records are made in a sequence one-after-another

Non-Contiguous Storage

• Files use available storage on disks
• No Direct access support
• Store 1 by 1

Indexed Storage

• Allows direct record access by bringing the relevant items into one index block

Capability List

• Illustrate access, users, and lists
• Shows all users and the files that can be accessed
• It Can also control devices as well as files in this manner