Session 6.1 – Secondary Storage Structure

Total Access Time Formula:

Access_Time = Seek_Time + Rotational_Delay + Transfer_Time

Component Breakdown:

┌───────────────────┬────────────────────────────────────────┐
│    Component     │                Description                     │
├───────────────────┼────────────────────────────────────────┤
│                 │ Time to position read/write head over      │
│   Seek Time     │ the correct track. Depends on:             │
│                 │ • Current head position                   │
│                 │ • Target track location                   │
├───────────────────┼────────────────────────────────────────┤
│                 │ Time for desired sector to rotate under    │
│ Rotational      │ the head. Average = Revolution_time / 2    │
│   Delay         │ • Depends on rotational speed (RPM)       │
│                 │ • Worst case = Full revolution            │
├───────────────────┼────────────────────────────────────────┤
│                 │ Time to read/write data from/to disk.      │
│ Transfer Time   │ = Data_size / Transfer_rate                 │
│                 │ • Usually smallest component               │
│                 │ • Sequential access is faster             │
└───────────────────┴────────────────────────────────────────┘

Performance Optimization Focus:
    • Seek Time: Use scheduling algorithms (SSTF, SCAN)
    • Rotational Delay: NCQ, read-ahead, write coalescing
    • Transfer Time: Larger block sizes, parallel I/O

Algorithm FCFS_Disk_Scheduling:

Input: request_queue[], initial_head_position
Output: service_sequence[], total_seek_time

BEGIN
    total_seek_time = 0
    current_position = initial_head_position
    service_sequence = []
    
    FOR EACH request in request_queue DO
        seek_distance = |current_position - request|
        total_seek_time = total_seek_time + seek_distance
        service_sequence.append(request)
        current_position = request
    END FOR
    
    RETURN service_sequence, total_seek_time
END

Algorithm SSTF_Disk_Scheduling:

Input: request_queue[], initial_head_position
Output: service_sequence[], total_seek_time

BEGIN
    remaining_requests = copy(request_queue)
    total_seek_time = 0
    current_position = initial_head_position
    service_sequence = []
    
    WHILE remaining_requests is not empty DO
        closest_request = NULL
        min_distance = INFINITY
        
        FOR EACH request in remaining_requests DO
            distance = |current_position - request|
            IF distance < min_distance THEN
                min_distance = distance
                closest_request = request
            END IF
        END FOR
        
        total_seek_time = total_seek_time + min_distance
        service_sequence.append(closest_request)
        remaining_requests.remove(closest_request)
        current_position = closest_request
    END WHILE
    
    RETURN service_sequence, total_seek_time
END

Algorithm SCAN_Disk_Scheduling:

Input: request_queue[], initial_head_position, disk_size, direction
Output: service_sequence[], total_seek_time

BEGIN
    left_requests = []
    right_requests = []
    
    // Partition requests based on initial head position
    FOR EACH request in request_queue DO
        IF request < initial_head_position THEN
            left_requests.append(request)
        ELSE
            right_requests.append(request)
        END IF
    END FOR
    
    // Sort requests for optimal scanning
    sort(left_requests, DESCENDING)   // From head toward 0
    sort(right_requests, ASCENDING)   // From head toward end
    
    total_seek_time = 0
    current_position = initial_head_position
    service_sequence = []
    
    IF direction == "RIGHT" THEN
        // Service right side first
        FOR EACH request in right_requests DO
            total_seek_time += |current_position - request|
            service_sequence.append(request)
            current_position = request
        END FOR
        
        // Move to disk end if needed
        IF current_position != disk_size-1 THEN
            total_seek_time += (disk_size-1) - current_position
            current_position = disk_size-1
        END IF
        
        // Service left side
        FOR EACH request in left_requests DO
            total_seek_time += |current_position - request|
            service_sequence.append(request)
            current_position = request
        END FOR
    END IF
    
    RETURN service_sequence, total_seek_time
END

Algorithm C_SCAN_Disk_Scheduling:

Input: request_queue[], initial_head_position, disk_size
Output: service_sequence[], total_seek_time

BEGIN
    left_requests = []
    right_requests = []
    
    // Partition requests based on initial head position
    FOR EACH request in request_queue DO
        IF request < initial_head_position THEN
            left_requests.append(request)
        ELSE
            right_requests.append(request)
        END IF
    END FOR
    
    // Sort for circular scanning (both ascending)
    sort(left_requests, ASCENDING)    // From 0 upward
    sort(right_requests, ASCENDING)   // From head upward
    
    total_seek_time = 0
    current_position = initial_head_position
    service_sequence = []
    
    // Service right side first (toward end)
    FOR EACH request in right_requests DO
        total_seek_time += |current_position - request|
        service_sequence.append(request)
        current_position = request
    END FOR
    
    // Circular jump: go to end, then to beginning
    IF right_requests is not empty THEN
        total_seek_time += (disk_size-1) - current_position  // To end
        total_seek_time += disk_size - 1                     // To beginning
        current_position = 0
    END IF
    
    // Service left side from beginning
    FOR EACH request in left_requests DO
        total_seek_time += |current_position - request|
        service_sequence.append(request)
        current_position = request
    END FOR
    
    RETURN service_sequence, total_seek_time
END

SSD Organization Structure:

Channel Level (Highest)
┌────────────────────────────────────────────────────────────────┐
│  CHANNEL (Parallel data pathways - typically 4-16 channels)    │
│  • Independent data buses for parallel operation              │
│  • Each channel can operate simultaneously                   │
│  • Bandwidth scales with number of channels                 │
└────────────────────────────────────────────────────────────────┘
                                  │
                                  ↓
┌────────────────────────────────────────────────────────────────┐
│  DIE (Independent flash memory units - 1-8 per channel)       │
│  • Each die has its own control logic                       │
│  • Can execute commands independently                       │
│  • Typical capacity: 32GB - 256GB per die                  │
└────────────────────────────────────────────────────────────────┘
                                  │
                                  ↓
┌────────────────────────────────────────────────────────────────┐
│  PLANE (Collection of blocks sharing resources - 1-4 per die) │
│  • Shares page buffers and bit lines                        │
│  │  • Can perform some operations in parallel                │
│  • Typical size: 8GB - 64GB per plane                      │
└────────────────────────────────────────────────────────────────┘
                                  │
                                  ↓
┌────────────────────────────────────────────────────────────────┐
│  BLOCK (Smallest erase unit - 128-512 pages per block)       │
│  • Erasing must be done at block level                     │
│  • Typical size: 512KB - 4MB per block                     │
│  • Limited erase cycles: 1K-10K (depends on NAND type)     │
└────────────────────────────────────────────────────────────────┘
                                  │
                                  ↓
┌────────────────────────────────────────────────────────────────┐
│  PAGE (Smallest read/write unit - 4KB to 16KB per page)      │
│  • Can only write to empty (erased) pages                  │
│  • Contains user data + spare area (ECC, metadata)         │
│  • Read/Program operations at page granularity              │
└────────────────────────────────────────────────────────────────┘
                                  │
                                  ↓
┌────────────────────────────────────────────────────────────────┐
│  CELL (Basic storage unit - stores 1-4 bits per cell)        │
│  • SLC: 1 bit/cell (fastest, most durable)                │
│  • MLC: 2 bits/cell (balanced performance/cost)            │
│  • TLC: 3 bits/cell (higher density, slower)              │
│  • QLC: 4 bits/cell (highest density, lowest endurance)   │
└────────────────────────────────────────────────────────────────┘
(Lowest Level)

Algorithm FTL_Write_Operation:

Input: logical_block_address (LBA), data
Output: success/failure status

Data Structures:
    mapping_table[LBA] → Physical_Block_Address (PBA)
    reverse_mapping[PBA] → LBA
    free_block_list[]
    erase_count[block_id]

BEGIN
    // Check if LBA already has a mapping
    IF LBA exists in mapping_table THEN
        old_PBA = mapping_table[LBA]
        mark_page_invalid(old_PBA)
        update_valid_page_count(get_block(old_PBA))
    END IF
    
    // Allocate new physical page
    new_PBA = allocate_free_page()
    IF new_PBA == NULL THEN
        // No free pages, trigger garbage collection
        victim_block = select_victim_block()
        new_PBA = garbage_collect(victim_block)
        IF new_PBA == NULL THEN
            RETURN FAILURE  // Disk full
        END IF
    END IF
    
    // Update mapping tables
    mapping_table[LBA] = new_PBA
    reverse_mapping[new_PBA] = LBA
    
    // Write data to flash memory
    status = flash_program(new_PBA, data)
    RETURN status
END

1. Read-ahead/Prefetching Algorithm:

Algorithm Adaptive_Readahead:
BEGIN
    window_size = INITIAL_WINDOW
    hit_rate = 0.0
    access_pattern = []
    
    FOR EACH read_request DO
        // Detect sequential pattern
        IF is_sequential(access_pattern) THEN
            window_size = min(MAX_WINDOW, window_size * 2)
            prefetch_blocks(current_block + 1, window_size)
        ELSE
            window_size = max(MIN_WINDOW, window_size / 2)
        END IF
        
        update_access_pattern(current_block)
    END FOR
END

2. Write Coalescing:
    • Combine small writes into larger sequential writes
    • Reduce number of I/O operations
    • Improve bandwidth utilization
    • Buffer writes temporarily in memory

3. I/O Scheduling Optimization:
    • NCQ (Native Command Queuing): 32 outstanding commands
    • TCQ (Tagged Command Queuing): Legacy alternative
    • Elevator algorithms: SCAN, C-SCAN for fairness
    • Deadline scheduling: Prevent I/O starvation

4. Multi-level Buffer Management:
    • L1: CPU Cache (1-3 cycles)
    • L2: Main Memory (50-100ns) 
    • L3: SSD Cache (10-100μs)
    • L4: HDD Storage (5-15ms)

5. Parallel I/O Techniques:
    • RAID striping across multiple disks
    • Multiple I/O channels utilization  
    • Asynchronous I/O operations
    • Multi-threading for concurrent access