2017 question paper

COMPUTER ORGANIZATION & ARCHITECTURE

16 questions

1. Q1a. Write the range of decimal integer that can be represented by n-bit 2’s complement representation.20172m

   Module 1: Functional Block of computer and Data representaion

   Write the range of decimal integer that can be represented by n-bit 2’s complement representation.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: Range $-2^{n-1}$ to $2^{n-1}-1$

   Explanation (n-bit 2's complement):

   • Most negative number: $100...0$ = $-2^{n-1}$
   • Most positive number: $011...1$ = $2^{n-1}-1$
   • Total distinct values: $2^n$
   • Single representation of zero (unlike 1's complement / sign-magnitude).
   • e.g., for n=8: $-128$ to $+127$; for n=4: $-8$ to $+7$.

   This is the range used in ALU and modern processors for signed integers.

2. Q1b. Justify the statement “Stack computer consists of an operation code only with no address field”.20172m

   Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

   Justify the statement “Stack computer consists of an operation code only with no address field”.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Justification: Stack computer is zero-address machine; operands implicitly on top of stack (TOS). Instruction needs only opcode because addresses of operands are implied: e.g., ADD pops two top elements, adds, pushes result. No fields to specify registers/memory. Useful for expression evaluation (postfix). Trade-off: needs stack manipulation instructions.

3. Q1c. What do you mean by Arithmetic shift left operation?20172m

   Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

   What do you mean by Arithmetic shift left operation?

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Arithmetic Shift Left:

   Arithmetic shift left shifts bits left by one position, LSB filled with 0, MSB (sign bit) preserved to maintain sign in 2's complement. Effectively multiplies signed number by 2.

   Example: 0101 (5) -> 1010 (10), 1101 (-3) -> 1010 (-6) [MSB kept as sign].

   If sign changes after shift (overflow), result is invalid and overflow flag V=1. Same operation as logical shift left except sign handling.

4. Q1d. What do you mean by locality of reference?20172m

   Module 4: Memory Organization

   What do you mean by locality of reference?

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Locality of Reference:

   Principle that memory accesses are clustered, not random — basis for caches and virtual memory.

   • Temporal Locality: Recently accessed locations tend to be accessed again soon (e.g., loops, stack variables). → Keep them in cache.
   • Spatial Locality: If a location is accessed, nearby locations will be accessed soon (e.g., sequential instructions, arrays). → Fetch blocks/lines.

   Due to locality, a small fast cache can achieve hit rate ~90-95% and make average access time close to cache speed despite large, slow main memory.

5. Q1e. What are the properties of an ideal instruction set computer?20172m

   Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

   What are the properties of an ideal instruction set computer?

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Properties of an Ideal ISA (Instruction Set Architecture):

   1. Completeness – All essential operations (data transfer, arithmetic/logic, control, I/O) are provided so any computable function can be implemented.

   2. Orthogonality – No special cases; any addressing mode can be used with any operation and any register. Instructions are independent and uniformly available.

   3. Regularity / Symmetry – Uniform instruction format, consistent opcode field, operand interpretation. Simplifies decoding.

   4. Efficiency – High code density, good performance, optimal use of registers/memory and support for high-level language constructs.

   5. Expandability / Extensibility – Opcode space reserved for future instructions/extensions without redesign.

   6. Compatibility & General Purpose – Balanced between hardware simplicity and software convenience; often includes support for interrupts, virtual memory and protection.

   An ideal ISA thus simplifies compiler design, hardware decoding and pipelining while remaining complete and efficient.

6. Q1f. Define the term hardware polling.20172m

   Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

   Define the term hardware polling.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Hardware Polling:

   A method to identify the interrupting device among multiple I/O devices using hardware logic instead of software.

   A dedicated polling unit / hardware poller sequentially interrogates (polls) each device's interrupt flag via a common bus. It checks status bits one-by-one in priority order using combinational/sequential polling logic.

   • Faster than software polling (which uses program loop to test each device).
   • Flexibility intermediate between daisy-chain and vectored interrupt.
   • On finding the requesting device, its address/vector is placed on bus and ISR is executed.

   Contrast: Software polling – CPU executes a program to poll each device; Hardware polling – special hardware does it automatically.

7. Q1g. What do you mean by data hazards in pipelining?20172m

   Module 3: Pipelining

   What do you mean by data hazards in pipelining?

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Data Hazards (RAW) Definition (2 Marks)

   In a pipelined processor, a data hazard occurs when an instruction depends on result of a previous instruction still in pipeline and data is not yet available.

   RAW (Read After Write) - True dependence: Most common type.

   I1: ADD R1, R2, R3   // R1 ← R2+R3
   I2: SUB R4, R1, R5   // needs R1
   

   I2 reads R1 before I1 writes it. If I2 enters ID/EX while I1 still in EX/MEM, it reads stale value — incorrect execution.

   Handling: Data forwarding/bypassing from MEM/WB to ALU input, pipeline stalling (bubble/NOP), compiler reordering.

   Other types WAW and WAR cause hazards only in out-of-order pipelines.

8. Q1h. Explain indirect address mode, and how the effective address is calculated in this case.20172m

   Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

   Explain indirect address mode, and how the effective address is calculated in this case.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Indirect Address Mode — EA = (Address Field) (2 Marks)

   Effective Address in indirect mode is not the operand itself but the memory location where the operand address is stored.

   • Definition: EA = M[A] or EA = (A) where A = address field of instruction. Instruction holds pointer to the operand address.
   • Example: LOAD R1, @1000 where M[1000] = 5000 → EA = 5000 → R1 ← M[5000]
   • Operation: Two memory accesses — 1st fetches address pointer M[A], 2nd fetches actual operand M[EA].
   • ** advantage:** Allows large address space with short field, supports pointers/indirect arrays, but slower due to extra access — indicated by * or @ or ( ) notation.
9. Q2. Why is read and write control lines in a DMA controller bidirectional? Under what condition and for what purpose are they used as inputs?201714m

   Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

   Why is read and write control lines in a DMA controller bidirectional? Under what condition and for what purpose are they used as inputs?

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Why Read ($\overline{MEMR}$/$\overline{IOR}$) and Write ($\overline{MEMW}$/$\overline{IOW}$) Lines in DMA Controller are Bidirectional [14 Marks]

   1. Background - 8237 / Generic DMAC and Bus Master Concept

   System bus has control lines $\overline{MEMR}$, $\overline{MEMW}$, $\overline{IOR}$, $\overline{IOW}$ (or unified $\overline{RD}$, $\overline{WR}$). Normally CPU is bus master and drives these lines as outputs to command memory/I/O.

   During DMA, DMAC becomes bus master after Bus Request ($HRQ$/$BUSREQ$) → Bus Grant ($HLDA$/$BUSACK$) handshake. The direction of $\overline{RD}$/$\overline{WR}$ reverses depending on who is master.

   Hence DMAC pins are bidirectional (open-drain with direction control): sometimes input, sometimes output.

   2. When DMAC is Bus Slave - Lines are INPUTS

   Condition: CPU is bus master, DMAC is not performing DMA (Idle or Programming mode). CPU addresses DMAC as an I/O device via its chip select ($\overline{CS}$) and register addresses (A0-A3).

   Purpose as Inputs: CPU programs DMAC's internal registers:

   • DMA Address Register (starting address)
   • Terminal Count / Word Count Register
   • Mode Register, Command Register, Mask Register, Request Register

   Operations:

   • CPU performs I/O Write to DMAC: $\overline{IOW}$ (= $\overline{WR}$) = 0 as input to DMAC + $\overline{CS}$=0 → data D0-D7 latched into DMAC register. Example: OUT 0BH, AL to write Mask Register.
   • CPU performs I/O Read from DMAC: $\overline{IOR}$ (= $\overline{RD}$) = 0 as input → DMAC drives data bus with status / remaining count register contents for CPU to read. Example: IN AL, 08H to read Status Register.

   Without input mode, CPU could not initialize DMA channel (source, destination, count, transfer type) before starting.

   3. When DMAC is Bus Master - Lines are OUTPUTS

   Condition: DMAC has acquired bus ( $HLDA=1$, $AEN=1$, CPU tristates its buses). Now DMAC drives address bus and control lines to perform data transfer between Memory and I/O without CPU.

   Purpose as Outputs - Two Types of DMA Transfer:

   • DMA Read (Memory → Peripheral): DMAC asserts $\overline{MEMR}$ (or $\overline{RD}$ as output, low) to read memory and $\overline{IOW}$ to write to I/O device in same bus cycle (or two cycles in flyby vs. two-cycle DMA). Data flows memory → DMAC → I/O.
   • DMA Write (Peripheral → Memory): DMAC asserts $\overline{IOR}$ to read peripheral and $\overline{MEMW}$ to write to memory. Data flows I/O → memory.
   • Memory-to-Memory (in 8237): $\overline{MEMR}$ and $\overline{MEMW}$ sequentially asserted.

   Thus as outputs, they act exactly as CPU's control signals would, commanding the memory and I/O participants.

   4. Summary Diagram (Conceptual)

            CPU (Master)  -------- IOR/IOW / MEMR/MEMW --------> DMAC (Slave) : INPUT mode (Program)
                                            |
            DMAC (Master) -------- MEMR/MEMW , IOR/IOW --------> Memory & I/O : OUTPUT mode (Transfer)
                                 (controls bus)
   

   Internal direction control via Bus Master Enable logic: when $HLDA=1$ & $AEN$ active → buffers set to output; otherwise inputs. Shared pins save package pins and reflect that bus control is mutually exclusive - only one master drives at a time.

   Key Advantage: Single set of control lines serves dual role → reduces interconnect and allows seamless hand-shaking: CPU configures DMAC as peripheral, then DMAC uses same lines as master to orchestrate high-speed block transfers (≈ 1.6 MB/s in 8237), freeing CPU.

   Exam Tip: Always mention both modes with concrete instruction example (OUT/IN) for input, and Flyby transfer example for output.

10. Q3. Explain the concept of virtual memory with the help of a diagram. Explain how virtual address is mapped to actual physical address.201714m

    Module 4: Memory Organization

    Explain the concept of virtual memory with the help of a diagram. Explain how virtual address is mapped to actual physical address.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Virtual Memory Concept

    Virtual memory is a memory management technique that gives program illusion of large contiguous main memory (e.g. $4$ GB) while physically only part resides in RAM; remainder kept on secondary storage (disk). Address generated by CPU (virtual/logical) is translated to physical via MMU.

    CPU generates              MMU + Page Table + TLB                Main Memory / Disk
    Virtual Address  ----->   Translation  -----> Physical Address ---> RAM (if present)
      32-bit                    VPN -> PFN       32-bit              else Page Fault -> Disk
    

    • Virtual address space $>>$ Physical address space (e.g. $2^{32}$ virtual vs $2^{28}$ physical).
    • Transparent to programmer, allows multiprogramming, protection, demand paging.
    • Uses locality – only active pages kept in RAM.

    Diagram: Paged Virtual Memory Mapping

    Virtual Address (32b)
    +----------------------+------------------+
    | Virtual Page Number  | Page Offset      |
    |  VPN (20b)           |  OFFSET (12b)    |  -> 4KB pages
    +-----------+----------+-----+------------+
                |                  |
                v                  |
         +--------------+          |
         | Page Table   | TLB      |
         | (in RAM)     | cache    |
         | VPN -> PFN   |          |
         +------+-------+          |
                |                  |
                v                  v
    Physical Address (32b)
    +----------------------+------------------+
    | Physical Frame Number| Offset           |
    |  PFN (20b)           | (12b same)       |
    +----------------------+------------------+
    
    RAM: [Frame 0][Frame 1]...[Frame N]   Disk: swap space with all pages
    

    Virtual to Physical Mapping Steps (Paging)

    Assume page size $4$ KB $=2^{12}$ B $\Rightarrow$ offset $12$ bits, VPN $20$ bits for $32$-bit virtual.

    1. CPU generates virtual address $VA = (VPN, offset)$.
    2. MMU looks up TLB (Translation Lookaside Buffer) – cache of page table.
       • TLB hit: get PFN immediately.
       • TLB miss: access page table in RAM (pointed by Page Table Base Register - PTBR). May be multi-level (e.g. 2-level for 32-bit).
    3. Page Table Entry (PTE) contains: PFN, valid bit, dirty, protection (R/W/X), referenced.
       • If valid=1: $PA = PFN \times PAGE\_SIZE + offset$ (concatenation).
       • If valid=0: Page Fault → trap to OS. OS loads required page from disk to free frame (using replacement e.g. LRU), updates PTE, restarts instruction.
    4. Physical address sent to cache/memory.

    Example: $VA=0x12345678$, page $4$ KB $\Rightarrow$ VPN=$0x12345$, offset=$0x678$; page table maps VPN $0x12345 \rightarrow PFN 0x00ABC$ $\Rightarrow$ $PA=0x00ABC678$.

    Segmentation + Paging: Sometimes VA = segment + offset; segment table → page table. But pure paging described above is most common (x86, ARM).

    Advantages: Large logical space, protection/isolation, sharing, efficient multiprogramming, demand loading.

    Overhead: Translation time (mitigated by TLB $>95\%$ hit), page fault handling, fragmentation (internal).

11. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
12. Q4. What is meant by Addressing Mode? Explain at least five different addressing modes with an example.201714m

    Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

    What is meant by Addressing Mode? Explain at least five different addressing modes with an example.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Addressing Mode

    Definition: The method by which the CPU interprets the address field of an instruction to obtain the effective address ($EA$) of the operand or the data itself. It determines where operand is and how to compute $EA$. Choice affects instruction length, cycles, and programming ease.

    General flow: $EA = f(\text{address field}, \text{registers}, PC )$, operand $= M[EA]$ or $R[EA]$.

    5+ Addressing Modes with Examples (8085/8086/Mano style)

    1. Implied / Implicit Mode
    Operand is implicit in opcode, no address field.
    EA = implied register
    Example: CLA (Clear AC), CLC (clear carry), HLT. STC on 8086 implies $CF\leftarrow1$.

    2. Immediate Mode
    Operand itself is in address field / next byte. No memory fetch beyond instruction.
    $Operand = \text{field}$
    Example: MVI A, 05H -> $A\leftarrow05H$; ADD #10 -> $AC\leftarrow AC+10$; LDA #100 loads value 100, not $M[100]$. Useful for constants. Fast.

    3. Direct / Absolute Mode
    Address field = $EA$. $EA = A$, operand $= M[A]$.
    Example: LDA 1000H -> $AC\leftarrow M[1000H]$; STA 2050H stores AC at 2050H.
    [8086: MOV AX, [5000H]]. Simple but instruction must hold full address.

    4. Indirect Mode
    Address field = address of address. $EA = M[A]$.
    Example (Mano): LDA I 200 where $M[200]=300$ -> $AC\leftarrow M[300]$.
    Often denoted LDA @200 or MOV AX, [BX] indirect via register. Allows $2^n$ addressability beyond field size but extra memory access.

    5. Register Mode
    Operand in register, field specifies register.
    $EA = R$
    Example: MOV A, B -> $A\leftarrow B$; ADD R1 -> $AC\leftarrow AC+R1$; INC AX. Fastest, no memory.

    6. Register Indirect Mode
    Field specifies register holding $EA$. $EA = (R)$.
    Example: MOV A, M where H-L holds address (8085: MOV A, M with $HL=2050H$ => $A\leftarrow M[2050H]$); 8086: MOV AX, [BX] where $BX=1000H$ => $AX\leftarrow M[1000H]$. LDA (R1) etc.

    7. Indexed / Auto-increment Mode (bonus)
    $EA = \text{Base} + \text{Index register}$; useful for arrays.
    Example: LOAD X(R1) where $R1$=index, $EA=X+R1$ -> $AC\leftarrow M[X+R1]$.
    Auto-increment: MOV (R1)+, R2 -> operand at $(R1)$ then $R1++$ for sequential access.
    8086: MOV AX, [SI+1000H].

    8. Relative / PC-relative Mode
    $EA = PC + \text{offset}$ (offset in field). For branching.
    Example: BNE -5 -> $PC\leftarrow PC-5$ if condition; 8086 JZ 08H is $PC+8$.

    9. Base Register Mode
    $EA = \text{Base register} + \text{displacement}$. For relocatable code/structures.
    Example: LDA 20(Rbase).

    Mode	Cycles	When used
    Immediate	1 fetch	Constants
    Direct	1 mem	Global variable
    Indirect	2 mem	Pointers
    Register	0 mem	Temporaries
    Indexed	1 mem+add	Arrays/loops

    Effective programming uses mixture; RISC favors register+immediate, CISC supports all.

13. Q5. What are the different conflicts that will arise in pipeline (elaborate)? How do you remove the conflicts?201714m

    Module 3: Pipelining

    What are the different conflicts that will arise in pipeline (elaborate)? How do you remove the conflicts?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Pipeline Conflicts (Hazards) and Remedies

    Pipeline ideally gives 1 instruction per cycle, but dependencies cause hazards that stall/flush pipeline.

    1. Structural Hazards (Resource Conflicts)

    • Cause: Two stages need same hardware same cycle. e.g., single memory for IF and MEM stage; single ALU; register file with one write port but two instructions need write.
    • Example: 4-stage pipeline with IF and MEM sharing memory -> IF of I4 conflicts with MEM of I1.
    • Solutions:
      • Separate Instruction and Data caches (Harvard) / L1 split - simultaneous IF+MEM.
      • Multiple functional units, pipelined units, extra ports on register file.
      • Stall (bubble) - hardware interlock delays one instruction.

    2. Data Hazards (Data Dependency)

    • RAW - Read After Write (True): ADD R1,R2,R3 ; SUB R4,R1,R5 - second needs R1 before first writes. Classic.
      • Sub-types: distance 1,2 hazards in pipeline.
    • WAR - Write After Read and WAW - Write After Write (false dependencies) - occur in OOO / superscalar pipelines due to register reuse.
    • Effects: Wrong operand value if pipeline forwards unupdated register.
    • Solutions:
      • Data Forwarding / Bypassing: Directly route ALU output to next instruction's ALU input via forwarding path (EX->EX, MEM->EX) - avoids stall for most RAW.
      • Stall / Pipeline Interlock + NOP injection: Compiler/hardware inserts bubble when forwarding insufficient (e.g., Load-Use hazard: LW R1,0(R2) ; ADD R3,R1,R4 - needs one stall because data available after MEM).
      • Register Renaming: Remove WAR/WAW by mapping to physical registers (Tomasulo).
      • Compiler Scheduling: Reorder independent instructions between dependent pair: LW R1; ... independent ... ; USE R1
      • Out-of-Order Execution + Scoreboarding: Execute independent instructions while dependent waits in reservation station.

    3. Control Hazards (Branch Hazards)

    • Cause: Pipeline doesn't know next PC after Branch/Jump until decode/execute stage. Fetches wrong path.
    • Example: BEQ R1,R2, Label - 2-3 instructions after branch already fetched before condition resolved.
    • Penalties: Flush 1-3 cycles (branch penalty) ~10-20% performance loss if ~15% branches.
    • Solutions:
      • Stall + Flush: On branch detection, freeze IF/ID, flush wrong path once target known (simple, slow).
      • Branch Prediction: Predict taken/not-taken.
        • Static: Predict not-taken or compiler hint.
        • Dynamic: 1-bit / 2-bit saturating counter, Correlated (Gshare), BTB (Branch Target Buffer) to store target. Accuracy 90-95% -> penalty only on mispredict.
      • Delayed Branch (Branch Delay Slot): Architecturally fill slot after branch with useful independent instruction - used in MIPS.
      • Predicated Execution: Convert branch to conditional move CMOV -> no flush.
      • Speculative Execution: Execute predicted path speculatively with ROB, rollback on mispredict.
      • Loop Buffer / Branch Target Cache: Cache branch targets.

    Summary Table

    Hazard	Cause	Detection	Remedy	Cost
    Structural	Resource sharing	Scheduler	Duplicate resources, split cache	Hardware cost
    Data RAW	Register dependency	Comparator on RD vs RS	Forwarding + stall if load-use	1 bubble if not forwarded
    Control	PC change	Branch logic	Predict, delayed branch, flush	1-3 cycles mispredict penalty

    Overall techniques to keep pipeline busy: Forwarding (data), Prediction + Speculation (control), Superscalar OOO + Renaming.

    Ideal CPI =1, actual CPI =1 + stall cycles per instruction. With forwarding+prediction CPI ~1.1-1.3 instead of ~1.6 without.

14. Q6. Explain Von Neumann Architecture. What are its drawbacks?201714m

    Module 1: Functional Block of computer and Data representaion

    Explain Von Neumann Architecture. What are its drawbacks?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Von Neumann Architecture

    Proposed by John von Neumann (1945, EDVAC report). Also called Stored-Program Concept and Princeton Architecture. Dominant architecture for general-purpose computers.

    1. Principle

    Program (sequence of instructions) and data are stored together in the same read-write memory and treated alike. CPU fetches instructions sequentially from memory, decodes and executes them, modifying data in same memory.

    2. Block Diagram

                      +----------------------------------+
                      |        Central Processing Unit     |
                      |   +------------------+  +------+  |
                      |   | Control Unit (CU)|  | ALU  |  |
       Input Device -->|   |  - PC            |<-+      |  |
       (Keyboard,     |   |  - IR            |  |      |  |
        Disk)         |   |  - Decodes inst. |->+      |  |
                      |   +------------------+  +------+  |
                      |            ^   |    ^             |
                      |            |   v    |             |
                      +------------+---+----+-------------+
                                   |   |    |
                              +----+---v----+----+
                              |      Memory       |
                              |  (Single Address  |
                              |   Space for       |
                              | Program + Data)   |
                              +---------+---------+
                                        ^   |
                      +-----------------+   +--v---------------+
                      | Output Device   |<-----| I/O Interface |
                      | (Display, etc)  |      +---------------+
                      +---------------+
    
    Simplified bus view:
    
      +----------------+     Address Bus
      |      CPU       |<---------------->+----------------+
      |  CU + ALU +    |     Data Bus     |    Memory      |
      |  Registers     |<---------------->| (Instructions  |
      +----------------+   Control Bus    |  + Data)       |
             ^                            +----------------+
             |                            |
             +------> I/O Module ---------> Devices
    

    Core components:

    1. Memory (M): Single linear address space, stores both instructions and data. Each location has unique address.
    2. Control Unit (CU): Fetches instruction at M[PC], increments PC, decodes opcode, generates control signals, coordinates fetch-decode-execute cycle.
    3. ALU: Performs arithmetic/logic on data from registers/memory.
    4. Registers: PC, IR, MAR, MBR, Accumulator/GPRs inside CPU.
    5. I/O: Input/Output mechanism via same bus.

    Operation Cycle (Fetch-Decode-Execute):

    1. Fetch: MAR <- PC; MBR <- M[MAR]; IR <- MBR; PC <- PC+1
    2. Decode: CU decodes IR
    3. Execute: ALU or memory operation as per opcode; repeat
    

    3. Characteristics

    • Single memory bus for instructions and data (sequential access).
    • Instruction execution is sequential unless branch modifies PC.
    • Hardware simple - one memory, one bus.

    4. Drawbacks / Limitations

    1. Von Neumann Bottleneck: Single bus between CPU and memory can only transfer one word at a time - cannot fetch instruction and access data simultaneously. CPU stalls waiting for memory (memory wall). Limits throughput even if CPU is fast.

    2. Sequential execution: No inherent parallelism; instruction-level parallelism must be extracted via pipelining/cache which complicates control.

    3. Memory is limiting factor: CPU speed >> memory speed, bottleneck dominates performance.

    4. Shared bus contention: I/O and CPU compete for same memory bus.

    5. Not suitable for real-time DSP: Harvard architecture (separate instruction and data memories/buses) used in DSP/microcontrollers for simultaneous fetch to overcome this - Von Neumann lacks that.

    6. Virus/security issue: Since code and data share same memory, erroneous data can be executed as code (buffer overflow attacks).

    Improvement: Modern computers keep Von Neumann logically but implement Harvard-like cache (split L1 I-cache/D-cache), pipeline, out-of-order execution, and hierarchy to hide bottleneck while retaining stored-program simplicity.

15. Q7. What is a page fault? What does a page fault signify? Explain the different page replacement algorithms which determine the page to be removed in case of full memory.201714m

    Module 4: Memory Organization

    What is a page fault? What does a page fault signify? Explain the different page replacement algorithms which determine the page to be removed in case of full memory.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Solution - Page Fault and Page Replacement Algorithms (14M)

    What is a Page Fault?
    In virtual memory with demand paging, pages are loaded from secondary storage (disk) to main memory only when needed. A page fault is an exception (trap) that occurs when a running process tries to access a page that is currently not present in main memory (valid bit = 0 in Page Table or TLB miss). The MMU detects this via page table entry's present/absent bit and raises interrupt #14 (x86).

    What does it signify?

    • Indicates miss in main memory hierarchy; required page (or segment of program/data) is still on disk (swap space).
    • Triggers OS fault handler: OS must block the process, allocate a free frame, read the page from disk into frame (I/O), update page table (frame number, valid=1), and restart the faulting instruction.
    • High frequency = thrashing if insufficient frames (working set > memory).
    • Counted as overhead: interrupt + context switch + disk I/O (ms) >> memory access (ns).

    Page fault handling steps:

    1. Trap to OS, save registers.
    2. Check if reference was legal (segmentation violation vs valid page on disk).
    3. Find free frame (or victim via replacement algorithm if none free).
    4. If victim dirty, write back to disk.
    5. Read required page from disk into frame (DMA).
    6. Update page table, TLB invalidated.
    7. Restart process at faulting instruction.

    Page Replacement Algorithms - when memory is full (no free frame), which victim page to evict:

    1. FIFO (First-In First-Out):

    • Replaces page that has been in memory longest (queue). Simple via FIFO queue.
    • Belady's Anomaly: More frames can increase faults! Not stack algorithm.
    • Example: Reference string 1,2,3,4,1,2,5,1,2,3,4,5 with 3 frames -> 9 faults.

    2. Optimal (OPT / MIN) - Theoretical:

    • Replaces page that will not be used for longest period in future (furthest next use). Gives minimum faults, used as benchmark.
    • Impossible to implement perfectly (requires future knowledge), but approximated.
    • Example: Same string -> 7 faults (optimal).

    3. LRU (Least Recently Used):

    • Replaces page that has not been used for longest time in past. Exploits locality.
    • Implementation: counter/timestamp or stack, or approximation via reference bits.
    • Good performance, close to Optimal. Stack algorithm (more frames never hurts).
    • Example: With same string -> 10 faults.

    4. Approx. LRU variants:

    • NRU / Clock (Second Chance): Circular queue with reference bit R. Give second chance if R=1 then clear and rotate; if R=0 replace. Efficient.
    • Aging / LFU / MFU: Least Frequently Used (count accesses) / Most Frequently Used - but LFU suffers cache pollution.

    5. LIFO / Random:

    • LIFO replaces last loaded; Random picks random victim - simple, avoids Belady but unpredictable.

    Comparison Table:

    Algorithm	Needs future?	Overhead	Anomaly	Performance
    FIFO	No	Low	Yes	Poor
    Optimal	Yes	-	No	Best (ideal)
    LRU	No	High (stack)	No	Good
    Clock	No	Low	No	Good approx.
    LFU	No	Medium	No	Depends

    Selection criteria: Fault rate, implementation cost, hardware support (R and M bits in page table entry help Clock/LRU approximation). Modern OS uses Clock (enhanced second chance with Dirty bit) or LRU approximation with aging.

    Dirty bit: If victim page modified (M=1), must write back before replacement - double I/O cost, so some algorithms prefer clean victims (NRU class 0: R=0 M=0).

16. Q8. Why does I/O interrupt make more efficient use of the CPU? Explain the sequence of operations that take place in an interrupt-driven I/O transfer.201714m

    Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

    Why does I/O interrupt make more efficient use of the CPU? Explain the sequence of operations that take place in an interrupt-driven I/O transfer.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Why Interrupt-Driven I/O is More Efficient

    Programmed I/O (Polling): CPU continuously checks (polls) device status flag Ready/Busy in a loop until device is ready. During polling CPU is blocked, wastes thousands of cycles, cannot do useful work.

    Interrupt-Driven I/O: CPU initiates I/O, then continues executing current program. I/O device signals readiness by asserting an interrupt request (INTR/IRQ). CPU is interrupted only when needed, so no busy-wait. Efficiency is high especially for slow devices (keyboard, disk) where waiting time >> transfer time.

    Advantages: CPU not wasted in polling loops, allows concurrent computation and I/O (overlap), enables handling of asynchronous events, supports priority handling.

    Sequence of Operations in Interrupt-Driven Transfer

    Assume CPU → enables interrupts, issues I/O command to Interface.

    1. Device prepares data: Interface sets Ready or fills buffer.
    2. Interrupt Request: Interface asserts INTR line to CPU.
    3. Interrupt Acknowledgement: After completing current instruction, CPU checks INTR if Interrupt Enable (IE)=1 and no higher priority interrupt.
    4. Save context: CPU pushes Program Counter (PC) and Processor Status Word (PSW) onto stack, disables further interrupts (clears IE), branches to interrupt vector address.
    5. Vectoring: CPU fetches ISR address from Interrupt Vector Table using interrupt vector number supplied by device (or via daisy chain/priority encoder).
    6. Interrupt Service Routine (ISR):
       a. Save registers (if not done by HW).
       b. Poll device status / identify source if multiple devices share line.
       c. Transfer data: For input - read data register → memory/accumulator; For output - write data. If block transfer, loop or initiate next byte.
       d. Clear interrupt flag in device interface.
       e. Restore registers.
    7. Return from Interrupt: Execute IRET / RTI → restores PC and PSW (re-enables interrupts).
    8. Resume: CPU resumes interrupted program from next instruction.

    For vectored priority interrupt the device identifies itself; for non-vectored, CPU polls devices branch.

    Timing: CPU overhead is only saving/restoring + ISR execution, versus continuous polling. DMA further improves efficiency by transferring block without per-word ISR.

17. Q9. How many ROM chips are required to produce a memory capacity of 4096 bytes? How many address lines are required to access the 4096 bytes? How many of these addresses will be common to all these chips?201714m

    Module 4: Memory Organization

    How many ROM chips are required to produce a memory capacity of 4096 bytes? How many address lines are required to access the 4096 bytes? How many of these addresses will be common to all these chips?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    ROM Chip Calculation for 4096 Bytes (14 Marks)

    Given: Required memory capacity = 4096 bytes = $4096 \times 8 = 32768$ bits.
    Let ROM chip capacity be $C$ bytes/chip. Standard chips often $512 \times 4$, $1024 \times 4$, $1024 \times 8$ etc. General formulae below; numerical example for most common exam assumption follows.

    General Formulae:

    1. Number of chips $N = \frac{\text{Required capacity}}{\text{Chip capacity}}$
    2. Number of address lines to access 4096 bytes: $2^{k}=4096 \Rightarrow k=\log_2 4096 =12$ lines ($A_{11}$-$A_{0}$)
    3. Common addresses: Address lines are split into chip-select (higher) + intra-chip (lower). Lower $m$ lines where $2^{m}= \text{chip size in bytes}$ go to all chips in parallel (common), upper $(k-m)$ lines go to decoder to generate chip selects.

    Worked Example – Assume typical exam chip $512 \times 4$ bit (512 nibbles = 256 bytes? often quoted as 1024×4):

    Most textbooks assume $1024 \times 4$ bit ROM (128 bytes? actually $1024 \times 4 =4096$ bits =512 bytes) or $512 \times 8$ (512 bytes).

    Case A: If chip = $1024 \times 8$ (1024 bytes = 1 KB) – commonest for 4096:

    • $N = 4096/1024 = 4$ chips
    • Address lines =12
    • Per chip needs $\log_2 1024=10$ lines ($A_9$-$A_0$) common to all 4 chips (connected in parallel)
    • Remaining $12-10=2$ lines ($A_{11}A_{10}$) decoded via 2:4 decoder for chip select. So 10 common address lines, 2 chip-select lines.

    Case B: If chip = $512 \times 4$ bit = 256 bytes? Many colleges treat chip as $512$ bytes ($512 \times 8$):

    • $N =4096/512=8$ chips
    • Per chip needs 9 lines ($\log_2 512=9$) common to all 8 chips
    • Remaining 3 lines decoded via 3:8 decoder. So 9 common lines.

    Case C: If chip = $512 \times 4$ bit = 2048 bits =256 bytes and need byte organized memory: Need 2 chips per byte location (pair to make 8 bits), so $N=(4096 \times 8)/(512 \times 4)=16$ chips. Per chip 9 lines common? Actually 9 lines for 512 locations, 4 lines common? Detailed: $16$ chips arranged as 8 rows ×2 columns, $A_8$-$A_0$ (9 lines) common to all, $A_{11}$-$A_9$ (3 lines) to 3:8 decoder.

    Answer in generic terms:

    • Chips required = $4096 / C$ (e.g., $4$ for 1K×8, $8$ for 512×8, $16$ for 512×4)
    • Address lines =12
    • Common lines = $\log_2(C)$ to all chips (e.g., 10 lines for 1K chips, 9 for 512-byte chips), remaining lines are chip-select decoded.

    Without loss, exam expects: 8 chips of 512 bytes, 12 address lines, 9 common (if 512-byte assumed) or 4 chips, 10 common (if 1K assumed). State assumption explicitly.