CS 370 Final Review: Deadlocks, Memory, and Security

Deadlock

A situation where a set of processes are unable to proceed because each is waiting for resources held by another.

Mutual Exclusion

Only one process can use a resource at a time.

Hold and Wait

Processes holding resources can request additional resources.

No Preemption

Resources cannot be forcibly taken from a process; they must be released voluntarily.

Circular Wait

A set of processes exists where each process is waiting for a resource held by the next process in the chain.

Prevention

Ensure at least one of the four necessary conditions cannot occur, e.g., prevent circular wait by imposing an ordering on resource allocation.

Avoidance

Use algorithms like the Banker's Algorithm to determine safe states.

Detection and Recovery

Allow deadlocks to occur but detect them using techniques like a wait-for graph and recover by terminating processes or preempting resources.

Safe State

A system is in a safe state if it can allocate resources to all processes in a sequence such that deadlock is avoided.

Banker's Algorithm

It determines whether the system can remain in a safe state after granting a resource request.

Wait-for Graph

A graph used for deadlock detection in systems where each resource type has a single instance.

Process Termination

Terminate one or more processes involved in the deadlock.

Resource Preemption

Forcefully take resources from one process and allocate them to another.

Base Register

Holds the smallest legal physical memory address.

Limit Register

Specifies the size of the range of legal addresses.

Compile Time

Addresses are determined during compilation.

Load Time

Binding occurs when the program is loaded into memory.

Execution Time

Binding happens dynamically during execution, allowing relocation.

Physical Address

Addresses generated after translation by the MMU.

Memory Management Unit (MMU)

The hardware device that maps virtual to physical addresses.

First Fit

Allocate the first hole large enough.

Best Fit

Allocate the smallest hole large enough.

Worst Fit

Allocate the largest available hole.

Internal Fragmentation

Wasted space within allocated memory blocks.

External Fragmentation

Wasted space between allocated blocks.

Page number and page offset

The two parts of an address generated by the CPU.

Page table entry

Contains frame number (physical address of the page) and control bits (e.g., valid/invalid, read/write permissions).

Fragmentation in paging systems

False. Paging eliminates external fragmentation but may suffer from internal fragmentation.

TLB Miss

Describes when a page number is not present in the TLB.

Page size calculation

If a page offset is 13 bits, the page size is 2^13 bytes = 8 KB.

Two-level page table entries

With a 20-bit page number, there are 2^20 = 1,048,576 entries.

Alternative to hierarchical paging

Inverted Page Table or Segmentation.

IA-32 address translation

True. IA-32 uses a combination of paging and segmentation.

IA-64 addressing bits usage

False. Only a subset of the 64 bits is typically used.

Components of a 32-bit ARM address

Page number, page table index, and page offset.

Virtual memory execution

True. Virtual memory allows programs to execute even if only part of their code or data is in memory.

Physical vs Virtual address space

False. Virtual address space can be much larger than physical memory, thanks to virtual memory.

Page fault occurrence

When a process attempts to access a page that is not currently in memory.

Pure demand-paged system behavior

True. Pure demand paging fetches pages only when a page fault occurs.

System call for copy on write

fork(). When a child process is created, pages are shared until either process writes to a page.

Simplest page replacement algorithm

FIFO (First In, First Out).

Optimal Page Replacement Algorithm

Replaces the page that will not be used for the longest period of time.

Least Recently Used (LRU)

Page replacement algorithm that could be implemented using a stack or counters.

Approximation algorithms in LRU

True. LRU is complex to implement directly, so approximations like the clock algorithm are used.

Global vs Local page replacement

Global Replacement: Pages can be replaced from any process. Local Replacement: Pages are replaced only within the faulting process.

Thrashing

Situation where a process spends more time paging than executing.

Working Set

Set of pages a process is currently referencing.

Page fault rate with pure demand paging

True. The page fault rate decreases as more pages are brought into memory.

Shared memory implementation

False. Shared memory is often implemented using memory mapping.

TLB reach calculation

32×4 KB=128 KB.

Typical page size

True. 4 KB is a typical page size.

Support for large page sizes

True. Many systems support large page sizes for performance reasons.

Magnetic disks

Provide almost all secondary storage for modern computer systems.

Solid-state disks (SSDs)

Have different performance characteristics, including no moving parts and faster access times.

Sector

The smallest unit of transfer between a disk.

Sequential Access

One of the two ways a computer can access disk storage.

Direct Access

One of the two ways a computer can access disk storage.

FCFS (First Come First Serve)

One of the three general disk scheduling algorithms.

SSTF (Shortest Seek Time First)

One of the three general disk scheduling algorithms.

SCAN (Elevator Algorithm)

One of the three general disk scheduling algorithms.

Formatting

What must be done to a disk before it can be used for storage, creating a file system on the disk.

Master Boot Record (MBR)

Where the Windows system places its boot code.

RAID

Improves performance, reliability, and redundancy.

Parity

Helps reconstruct a corrupted block by storing information about data redundancy.

Redundancy in HDFS

Ensures that multiple copies of data are stored across different nodes for fault tolerance.

File attributes

Name, size, type, permissions, owner, and timestamps (creation, modification, access).

File operations

Create, read, write, delete, open, close, append.

Volume

A logical storage unit that may span physical disks.

Hierarchical Directory Structure

The most common way of structuring directories.

Acyclic-graph directories

Supported by UNIX systems using symbolic links.

Complete path name

/home/programs when the device jane/programs is mounted on the mount point /home.

NFS (Network File System)

One type of remote file system.

User classifications

Owner, group, and others in connection with each file.

Ext4

The name of the standard Linux file system.

Inode

The UNIX term for a file control block.

Virtual File System (VFS)

What the acronym VFS refers to.

Directory implementation approaches

Linear List: Simple but slow; Hash Table: Fast lookup with some complexity.

Disk block allocation methods

Contiguous Allocation: Blocks are stored together sequentially; Linked Allocation: Blocks are linked via pointers.

Bit vector example

Appears as 01011001 if blocks 0, 3, 4, and 6 were free.

HDFS

Designed for distributed storage, fault tolerance, and handling large files across clusters.

MapReduce

Provides a framework for processing and generating large datasets in parallel.

Full Virtualization

Simulates hardware entirely.

Paravirtualization

Optimized for virtualization by modifying the guest OS.

Containers, Jails, Zones, Runtime Environments

They share the host OS kernel and lack full isolation.

Memory mapping in a virtualized system

Maps guest virtual addresses to host physical memory via a Virtual Machine Monitor (VMM).

Binary translation

Used by VMMs on CPUs lacking support to replace sensitive instructions.

Live migration

Possible in virtual environments due to hardware abstraction, allowing seamless transfer of VMs.

Containers implementation

Use OS-level virtualization, sharing the host OS kernel.

Advantages of containers

Lightweight, faster deployment, and reduced resource overhead.

Data centers usage

Increasingly used for scalability, efficiency, and to support modern cloud-based applications.

Social Engineering

The most common technique for security attacks, involving tricking individuals into divulging confidential information.

Physical Level security measures

Protect physical access to systems (e.g., locks, guards).

Human Level security measures

Ensure security practices among personnel (e.g., training, awareness).

Operating System Level security measures

Implement OS-based protections (e.g., access control, authentication).

Network Level security measures

Secure data transmission (e.g., firewalls, encryption).

Trojan Horse

A program that appears legitimate but performs malicious actions.

Buffer Overflow

Exploiting a program by overflowing its memory buffer to execute arbitrary code.

Worms

Self-replicating programs that spread across systems and networks without user intervention.

Password Authentication

The most common approach for authenticating a user, where users provide a password to verify their identity.

Firewall

Monitors and controls incoming and outgoing network traffic based on predetermined security rules.