Direct Memory Access (DMA)

Definition

DMA (Direct Memory Access) is a feature of computer systems that allows certain hardware subsystems (such as disk controllers, network cards, or sound cards) to access main memory (RAM) independently of the CPU. It enables data transfer between I/O devices and memory without continuous CPU involvement, freeing the CPU to perform other tasks during the transfer.

Why DMA is Needed

Without DMA, the CPU must supervise every byte transferred between an I/O device and memory (programmed I/O), which wastes CPU cycles. DMA offloads this work to a dedicated DMA Controller (DMAC).

Key Components

How DMA Works (Step-by-Step)

Step 1: CPU Initialization

• The CPU programs the DMA controller by providing:
  • Source address
  • Destination address
  • Number of bytes to transfer
  • Direction of transfer (read/write)
• The CPU then continues its own tasks.

Step 2: DMA Request

• The I/O device signals the DMAC that it is ready to transfer data (via DMA Request line - DREQ).

Step 3: Bus Request

• The DMAC requests control of the system bus from the CPU by asserting the Bus Request (BR) signal.

Step 4: Bus Grant

• The CPU completes its current bus cycle and grants the bus to the DMAC by asserting Bus Grant (BG). The CPU is now temporarily disconnected from the bus (CPU is in a "hold" state).

Step 5: Data Transfer

• The DMAC takes control of the address bus, data bus, and control bus.
• Data is transferred directly between the I/O device and memory, one block at a time, without CPU involvement.
• The address and count registers are updated after each transfer.

Step 6: Transfer Complete

• When the count reaches zero (all data transferred), the DMAC sends an interrupt to the CPU to notify it that the transfer is complete.
• The CPU resumes control of the bus.

Diagram

        +------------------+
        |       CPU        |
        +--------+---------+
                 |  BR / BG (Bus Request / Bus Grant)
                 |
        +--------+---------+
        |  DMA Controller  |<-------- DREQ (from I/O Device)
        | (Source Addr Reg)|
        | (Dest  Addr Reg) |
        | (Count Reg)      |
        +---+----------+---+
            |          |
     Address/Data/Control Bus
            |          |
    +-------+--+    +--+--------+
    |  Main    |    | I/O Device|
    |  Memory  |    | (Disk,NIC)|
    +----------+    +-----------+

Data Flow:

I/O Device  ----[DMA Controller]---->  Main Memory
                  (No CPU needed
                   during transfer)

Advantages of DMA

• CPU is free to execute other instructions during data transfer.
• Faster data transfer compared to programmed I/O or interrupt-driven I/O.
• Suitable for high-speed, bulk data transfers (e.g., disk to memory).

Summary

DMA allows I/O devices to transfer data directly to/from memory by temporarily taking control of the system bus, with the CPU only involved at the start (initialization) and end (interrupt) of the transfer.

Types of Files, Sequential and Random Access

Types of Files

Files can be classified based on their nature and access method:

1. Text Files - Store data as human-readable characters (ASCII/Unicode). Each line ends with a newline character. Example: .txt, .csv

2. Binary Files - Store data in binary format (as bytes), not human-readable. Example: .exe, .jpg, .mp3

3. Sequential Files - Records are stored and accessed one after another in order.

4. Random Access Files (Direct Access Files) - Records can be accessed directly at any position without reading preceding records.

5. Index Sequential Files - Combination of sequential and direct access; uses an index to locate records.

Sequential Access of Files

In sequential access, data is read or written in order from the beginning to the end of the file. To reach a particular record, all preceding records must be read first.

Characteristics:

• Simple to implement
• Suitable for batch processing (e.g., payroll, billing)
• Slow for searching a specific record
• Pointer moves only forward (one record at a time)

Operations:

Example (in C-like pseudocode):

FILE *fp = fopen("data.txt", "r");
while (!feof(fp)) {
    fscanf(fp, "%s", record);
    // process record
}
fclose(fp);

Diagram:

[Record 1] --> [Record 2] --> [Record 3] --> [Record 4] --> EOF
   Read 1st      Read 2nd      Read 3rd      Read 4th

Random Access of Files

In random access (direct access), any record can be read or written directly by specifying its position (offset) in the file, without reading preceding records.

Characteristics:

• Faster access to specific records
• Suitable for databases and real-time systems
• Uses seek() function to move file pointer to any position
• Requires knowledge of record size for offset calculation

Key Functions:

fseek() Origins:

• SEEK_SET - Beginning of file
• SEEK_CUR - Current position
• SEEK_END - End of file

Example (in C):

FILE *fp = fopen("data.bin", "rb");
int recordSize = sizeof(struct Record);
int recordNo = 3;  // Access 3rd record directly

fseek(fp, (recordNo - 1) * recordSize, SEEK_SET);
fread(&record, recordSize, 1, fp);
fclose(fp);

Diagram:

[Record 1] [Record 2] [Record 3] [Record 4] [Record 5]
                          ^
                          |
                    Direct jump using fseek()

Comparison Table

Deadlock

Definition

A deadlock is a situation in a multiprogramming environment where a set of processes are blocked permanently because each process in the set is waiting for a resource that is held by another process in the same set. None of the processes can proceed, and they wait indefinitely.

Example: Process P1 holds Resource R1 and waits for R2, while Process P2 holds R2 and waits for R1. Neither can proceed.

Necessary Conditions for Deadlock (Coffman Conditions)

Deadlock can occur if and only if all four of the following conditions hold simultaneously:

1. Mutual Exclusion

• At least one resource must be held in a non-shareable mode.
• Only one process can use the resource at a time.
• If another process requests that resource, it must wait until the resource is released.

Example: A printer can be used by only one process at a time.

2. Hold and Wait

• A process must be holding at least one resource and waiting to acquire additional resources that are currently held by other processes.
• The process does not release the resources it already holds while waiting.

Example: P1 holds R1 and is waiting for R2.

3. No Preemption

• Resources cannot be forcibly taken away from a process.
• A resource can only be released voluntarily by the process holding it, after it has completed its task.

Example: A process holding a file lock cannot be forced to release it.

4. Circular Wait

• A set of processes {P0, P1, P2, ..., Pn} must exist such that:
  • P0 is waiting for a resource held by P1
  • P1 is waiting for a resource held by P2
  • ...
  • Pn is waiting for a resource held by P0
• This forms a circular chain of waiting processes.

Example: P1 → waits for R2 (held by P2) → waits for R1 (held by P1)

Summary Table

Note: All four conditions must hold simultaneously for deadlock to occur. Preventing even one condition is sufficient to prevent deadlock.

Thread, User Level Thread, and Kernel Level Thread

What is a Thread?

A thread is the smallest unit of CPU execution within a process. It is also called a lightweight process (LWP). A thread shares the code section, data section, and OS resources (like open files and signals) with other threads belonging to the same process, but has its own:

• Thread ID
• Program counter (PC)
• Register set
• Stack

A process can have multiple threads running concurrently, which improves performance and responsiveness.

User Level Threads (ULT)

User level threads are managed entirely by a user-space thread library (e.g., POSIX Pthreads) without kernel involvement.

Characteristics:

• The kernel is not aware of the existence of these threads.
• Thread management (creation, scheduling, synchronization) is done by the user-level library.
• From the kernel's perspective, the entire process appears as a single-threaded process.

Advantages:

• Thread switching does not require kernel mode, so it is faster.
• Can be implemented on any OS, even those that do not support threads.
• More portable and flexible scheduling.

Disadvantages:

• If one thread makes a blocking system call, the entire process is blocked.
• Cannot take advantage of multiprocessor systems (all threads map to one kernel thread).

Kernel Level Threads (KLT)

Kernel level threads are managed directly by the operating system kernel.

Characteristics:

• The kernel maintains information about each thread.
• Thread creation, scheduling, and management are performed by the kernel.
• Each user thread maps to a kernel thread.

Advantages:

• If one thread is blocked, the kernel can schedule another thread of the same process.
• Can run on multiple processors simultaneously (true parallelism).
• Better support for multiprocessor environments.

Disadvantages:

• Thread switching requires a mode switch to kernel, making it slower than ULT.
• More overhead in thread management.

Comparison Table

Note: Many modern operating systems use a combined (hybrid) approach where multiple user threads are mapped to multiple kernel threads to get the benefits of both models.

CPU Scheduling: RR (q=3) and Priority

STEP 1 - Given Data

All arrive at time 0, in order A, B, C, D.

Formulas: $TAT = CT - AT$, $WT = TAT - Burst$.

STEP 2 - Solve

1. Round Robin (Quantum = 3)

Ready queue starts: A, B, C, D. A process that still has remaining burst rejoins the tail of the queue after its slice.

Tracing execution (remaining bursts A=8, B=9, C=10, D=6):

Gantt:

| A | B | C | D | A | B | C | D | A | B | C | C |
0   3   6   9  12  15  18  21 24  26  29  32  33

$$\text{Avg TAT} = \frac{26+29+33+24}{4} = \frac{112}{4} = 28 \text{ ms}$$ $$\text{Avg WT} = \frac{18+20+23+18}{4} = \frac{79}{4} = 19.75 \text{ ms}$$

2. Priority Scheduling (Non-Preemptive)

Higher number = higher priority. Execution order: D (4) → A (3) → C (2) → B (1)

Gantt:

| D | A | C | B |
0   6  14  24  33

$$\text{Avg TAT} = \frac{6+14+24+33}{4} = \frac{77}{4} = 19.25 \text{ ms}$$ $$\text{Avg WT} = \frac{0+6+14+24}{4} = \frac{44}{4} = 11 \text{ ms}$$

Summary