Core Principles of Assemblers and Operating Systems

Assembly Language Fundamentals

Assembly language is a low-level language that uses mnemonic instructions instead of binary code. The assembler translates these instructions into machine language. Assembly language instructions are categorized into three types:

• Imperative Statements (IS): These are executable instructions that perform actual CPU operations and generate machine code. Examples include STOP, ADD, SUB, MULT, MOVER, MOVEM, COMP, BC, DIV, READ, and PRINT. For example, MOVER AREG, NUM moves data to a register, ADD AREG, ='5' adds a literal value, and MOVEM AREG, RESULT stores the result in memory.
• Declarative Statements (DL): These are used to define data and reserve storage. DC (Define Constant) allocates memory and stores a constant value, while DS (Define Storage) reserves the required number of memory locations. Example: NUM DC 10, ARRAY DS 5.
• Assembler Directives (AD): These guide the assembler and do not generate machine code. START specifies the starting address, END marks the end of the program, ORIGIN changes the Location Counter (LC) value, EQU assigns a value to a symbol, and LTORG allocates literals.

The Location Counter and Symbol Tables

The Location Counter (LC) is used by the assembler to assign addresses to instructions and data. It starts from the address specified by START and increases as each statement is processed.

Example:

START 200
LOOP MOVER AREG, ='5'
ADD AREG, NUM
MOVEM AREG, RESULT
SUB AREG, ='1'
BC ANY, LOOP
NUM DC 10
RESULT DS 1
END

LC Values:

• MOVER → 200
• ADD → 201
• MOVEM → 202
• SUB → 203
• BC → 204
• NUM DC → 205
• RESULT DS → 206
• Literal ='5' → 207
• Literal ='1' → 208

The Symbol Table stores labels and addresses: LOOP = 200, NUM = 205, RESULT = 206.

The Literal Table stores literals and their addresses: ='5' = 207, ='1' = 208.

Thus, LC processing performed in Pass I generates Symbol and Literal Tables, which are later used by the assembler to produce machine code.

Assembler Design and Data Structures

An assembler converts assembly language into machine code. Based on the number of scans, assemblers are of two types: Single-Pass and Two-Pass.

• Single-Pass Assembler: Scans the source program once and generates machine code immediately. It is faster, but handling forward references is difficult, requiring backpatching.
• Two-Pass Assembler: Scans the program twice. Pass I assigns addresses and generates tables, while Pass II generates machine code. It is easier to implement and handles forward references efficiently.

Essential Data Structures

• MOT (Machine Opcode Table): Stores mnemonic, opcode, and instruction length.
• POT (Pseudo Opcode Table): Stores assembler directives like START, END, ORIGIN, EQU, and LTORG.
• SYMTAB (Symbol Table): Stores symbols and their addresses.
• LITTAB (Literal Table): Stores literals and assigned addresses.
• POOLTAB (Pool Table): Maintains the starting index of each literal pool.
• LC (Location Counter): Keeps track of current memory addresses.

Two-Pass and Single-Pass Algorithms

Two-Pass Algorithm:
Pass I: Initialize LC, process START, search MOT/POT, enter symbols into SYMTAB and literals into LITTAB, process directives, update LC, generate intermediate code, and allocate literal addresses at END/LTORG.
Pass II: Read intermediate code, obtain opcodes from MOT, symbol addresses from SYMTAB, literal addresses from LITTAB, and generate final machine code.

Single-Pass Algorithm:
Initialize LC, read statements, search MOT/POT, enter symbols into SYMTAB, generate machine code immediately, create temporary entries for forward references, perform backpatching when symbols are defined, and update LC until END.

Operating System Functions and Architecture

An Operating System (OS) is system software that acts as an interface between the user and computer hardware. It manages system resources and provides services for program execution. Examples include Windows, Linux, UNIX, macOS, and Android.

Key Functions of an OS

• Process Management: Creates, schedules, synchronizes, and terminates processes. It allocates CPU time and handles deadlocks.
• Memory Management: Tracks memory usage, allocates/deallocates memory, and supports paging, segmentation, and virtual memory.
• File System Management: Manages files and directories, controls access, and organizes storage.
• Device Management: Controls I/O devices using drivers and schedules I/O operations.
• Secondary Storage Management: Manages disk space and scheduling.
• Security and Protection: Provides authentication and access control.
• User Interface: Offers CLI and GUI for interaction.
• Error Detection: Monitors performance and detects system errors.

General OS Architecture

Users interact with application programs, which request services through the System Call Interface. The Operating System Kernel manages the hardware directly.

Architecture Flow:
Users → Application Programs → System Call Interface → Operating System Kernel → Hardware

Distributed Operating Systems

A Distributed Operating System (DOS) manages multiple independent computers (nodes) connected through a network, making them appear as a single system. Each node has its own processor and memory, but resources are shared.

Characteristics and Advantages

• Resource Sharing: Files, printers, and processors are shared among nodes.
• Transparency: Users view the distributed system as a single entity.
• Concurrency: Multiple processes execute simultaneously.
• Scalability: New nodes can be added easily.
• Reliability and Fault Tolerance: Failure of one node does not stop the entire system.
• Load Sharing: Workload is distributed for better performance.

Limitations: Complex implementation, security concerns, synchronization difficulties, and network dependency.

Process and Thread Management

A process is a program in execution. It is an active entity consisting of program code, a program counter, registers, stack, heap, and resources. A thread is the smallest unit of CPU execution within a process, often called a lightweight process.

Types of Threads

• User-Level Threads (ULT): Managed by libraries without kernel support. They are fast but can cause the entire process to block if one thread blocks.
• Kernel-Level Threads (KLT): Managed directly by the OS. They support true parallelism and independent scheduling.

Process vs. Thread Comparison

• Processes have separate memory spaces; threads share memory within a process.
• Process switching is slower; thread switching is faster.
• Processes use IPC for communication; threads use shared memory.

Round Robin CPU Scheduling

Round Robin (RR) is a preemptive algorithm used in time-sharing systems. Each process is assigned a fixed Time Quantum. If a process isn't finished within that time, it is moved to the end of the ready queue.

Example: Processes P1=10, P2=5, P3=8 with Time Quantum = 3.
Gantt Chart:
0-3 P1 | 3-6 P2 | 6-9 P3 | 9-12 P1 | 12-15 P2 | 15-18 P3 | 18-20 P1 | 20-22 P3 | 22-23 P1

• Average Waiting Time: 12.33 units.
• Average Turnaround Time: 20 units.

The Dining Philosopher Problem

This classic synchronization problem illustrates deadlock and starvation. Five philosophers sit at a table with five chopsticks. To eat, a philosopher needs both the left and right chopsticks.

Deadlock occurs if all philosophers pick up their left chopstick simultaneously. Solutions include limiting the number of philosophers at the table, resource ordering, or using monitor-based solutions.

Deadlock and the Banker's Algorithm

Deadlock is a state where processes wait indefinitely for resources held by each other. Necessary conditions include Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait.

Banker's Algorithm for Avoidance

Proposed by Edsger Dijkstra, this algorithm grants resource requests only if the system remains in a safe state. It uses the formula:
Need = Max − Allocation

If a safe sequence (e.g., <P1, P3, P4, P0, P2>) exists where all processes can finish, the system is safe.

Memory Fragmentation and Compaction

Fragmentation is memory wastage during allocation:

• Internal Fragmentation: Occurs when allocated memory is larger than required (common in fixed partitions).
• External Fragmentation: Occurs when total free memory is sufficient, but it is scattered in non-contiguous blocks.
• Compaction: A technique to shuffle memory contents to place all free memory together in one large block.

Free Space Management Techniques

The OS tracks unused disk blocks using several methods:

• Bit Vector (Bitmap): Uses bits (0 for free, 1 for allocated).
• Linked List: Links all free blocks together.
• Grouping: Stores addresses of free blocks in other free blocks.
• Counting: Stores the address of the first free block and the number of contiguous free blocks.

File Allocation Methods

These methods determine how files are stored on disk:

• Contiguous Allocation: Files occupy consecutive blocks. Fast but causes external fragmentation.
• Linked Allocation: Each block contains a pointer to the next. No external fragmentation, but slow direct access.
• Indexed Allocation: An index block stores all pointers to file blocks. Supports direct access and eliminates fragmentation.