Types of Operating Systems and Difference Between Real-Time and Batch OS

Types of Operating Systems

An Operating System (OS) is system software that manages hardware and software resources and provides services to computer programs. Operating systems are classified into the following types:

1. Batch Operating System

• Jobs with similar requirements are grouped (batched) together and executed without user interaction.
• A job scheduler picks jobs from the batch and submits them to the CPU one by one.
• Example: Early IBM mainframe systems, payroll processing.

2. Time-Sharing (Multitasking) Operating System

• CPU time is shared among multiple users/processes simultaneously.
• Each process gets a small time slice (quantum) in a round-robin fashion.
• Provides fast response time and interactive use.
• Example: UNIX, Linux, Windows.

3. Real-Time Operating System (RTOS)

• Designed to process data and respond within a strict, guaranteed time constraint (deadline).
• Used in time-critical applications.
• Example: Air traffic control, medical devices, missile guidance systems, VxWorks.

4. Distributed Operating System

• Manages a group of independent computers and makes them appear as a single system to the user.
• Resources (CPU, memory, storage) are distributed across multiple machines.
• Example: LOCUS, Amoeba.

5. Network Operating System

• Provides features to manage data, users, groups, security, and applications over a network.
• Each machine has its own local OS but can share resources over the network.
• Example: Windows Server, Novell NetWare.

6. Multiprocessor Operating System

• Supports systems with more than one CPU sharing the same memory and I/O devices.
• Increases throughput and reliability.
• Example: Symmetric Multiprocessing (SMP) systems.

7. Embedded Operating System

• Designed to operate on small machines (embedded systems) with limited resources.
• Highly specialized and resource-efficient.
• Example: Android (mobile), FreeRTOS, Windows CE.

8. Mobile Operating System

• Designed specifically for smartphones and tablets.
• Manages mobile hardware such as touchscreen, GPS, camera.
• Example: Android, iOS.

Difference Between Real-Time OS and Batch OS

Summary

Operating systems are classified based on how they manage processes, respond to users, and handle time constraints. Batch OS focuses on throughput and sequential job processing with no real-time constraints, while Real-Time OS focuses on correctness within strict time limits, making it essential for safety-critical and time-sensitive applications.

Kernel and System Call Process

What is Kernel? [3 marks]

The kernel is the core component of an operating system that acts as a bridge between application programs and the computer hardware. It is the first program loaded into memory when the computer starts (after the bootloader) and remains in memory throughout the entire session.

Key Characteristics of the Kernel:

• It runs in privileged mode (also called kernel mode or supervisor mode), which gives it unrestricted access to all hardware resources.
• It manages system resources such as CPU, memory, I/O devices, and file systems.
• It provides a protected environment so that user programs cannot directly access hardware.

Functions of the Kernel:

Types of Kernel:

1. Monolithic Kernel - All OS services run in kernel space (e.g., Linux, Unix)
2. Microkernel - Only essential services run in kernel space (e.g., Minix)
3. Hybrid Kernel - Combination of monolithic and microkernel (e.g., Windows NT)

System Call [7 marks]

Definition:

A system call is a programmatic way in which a user-level program requests a service from the operating system kernel. It provides the interface between a running process (user mode) and the operating system.

System calls are the only legal entry points into the kernel. When a user program needs to perform a privileged operation (such as reading a file, creating a process, or allocating memory), it must do so through a system call.

Types of System Calls:

1. Process Control - fork(), exit(), wait()
2. File Management - open(), read(), write(), close()
3. Device Management - ioctl(), read(), write()
4. Information Maintenance - getpid(), alarm(), sleep()
5. Communication - pipe(), shmget(), mmap()

Process of System Call (Step-by-Step):

USER SPACE                          KERNEL SPACE
-----------                         ------------

[User Program]
     |
     | 1. Calls library function
     v
[Library / API]
  e.g., printf()
     |
     | 2. Prepares parameters,
     |    places system call
     |    number in register
     v
[TRAP / INT instruction]
  (Software Interrupt)
     |
     |-------- MODE SWITCH -------->
                                   [Kernel Mode Activated]
                                          |
                                          | 3. Hardware saves
                                          |    CPU state (registers,
                                          |    PC, flags)
                                          v
                                   [Trap Handler / Interrupt
                                    Vector Table]
                                          |
                                          | 4. Identifies system
                                          |    call number
                                          v
                                   [System Call Dispatcher /
                                    System Call Table]
                                          |
                                          | 5. Calls appropriate
                                          |    kernel routine
                                          v
                                   [Kernel Service Routine]
                                    e.g., sys_write()
                                          |
                                          | 6. Executes the
                                          |    requested service
                                          |
                                          | 7. Places return value
                                          |    in register
                                          |
     <------- MODE SWITCH ----------      |
[Return to User Mode]              [Kernel Mode Ends]
     |
     | 8. Library function
     |    retrieves return value
     v
[User Program Continues]

Detailed Steps Explained:

Step 1: User Program Makes a Request

• The user program calls a high-level library function (e.g., read() in C).
• This library function is part of the API (Application Programming Interface).

Step 2: Prepare for System Call

• The library function places the system call number into a specific CPU register (e.g., register EAX in x86).
• Any arguments/parameters are placed in other registers or on the stack.

Step 3: Execute TRAP Instruction

• The library executes a special instruction called TRAP or INT (software interrupt), e.g., INT 0x80 in Linux x86.
• This causes a mode switch from user mode to kernel mode.
• The CPU saves the current state (program counter, registers, flags) onto the kernel stack.

Step 4: Trap Handler Invoked

• The hardware transfers control to a fixed memory address -- the trap handler (defined in the interrupt vector table).
• The trap handler verifies the system call number.

Step 5: System Call Dispatcher

• The dispatcher uses the system call number as an index into the system call table.
• The system call table is an array of function pointers pointing to kernel service routines.

Step 6: Kernel Service Routine Executes

• The appropriate kernel routine (e.g., sys_read()) executes with full hardware privileges.
• It performs the requested operation (reads from disk, allocates memory, etc.).

Step 7: Return from Kernel

• The return value (success/error code) is placed in a register.
• The kernel executes a return-from-trap instruction (e.g., IRET).
• The CPU restores the saved state and switches back to user mode.

Step 8: User Program Resumes

• The library function retrieves the return value from the register.
• Control returns to the user program, which continues execution.

Diagram Summary:

+------------------+        System Call        +------------------+
|                  |  -----------------------> |                  |
|   USER PROCESS     |                           |     KERNEL       |
|   (User Mode)    |  <----------------------- |   (Kernel Mode)  |
+------------------+       Return Value        +------------------+
         |                                              |
         | 1. call read()                               |
         v                                              |
+------------------+                                    |
|  Library / API   |  2. system call number -> register |
|  (libc wrapper)  |  3. TRAP / INT 0x80                |
+---------+--------+                                    |
          |                                             v
          |                          +---------------------------+
          +------------------------->|  4. Trap handler          |
                                     |  5. System call dispatcher|
                                     |     (system call table)   |
                                     |  6. sys_read() executes   |
                                     +-------------+-------------+
                                                   |
                                     7. IRET, restore state, back to user mode

Conclusion

The kernel is the core of the operating system: it always resides in memory, runs in privileged mode, and owns the hardware. A user program can never touch that hardware directly, so a system call is the controlled doorway between the two worlds. The library wrapper loads the call number and arguments, a TRAP instruction switches the CPU into kernel mode, the dispatcher looks the number up in the system call table, the kernel routine does the work with full privilege, and a return-from-trap puts the CPU back in user mode with the result in a register. This mode switch is what keeps one process from corrupting another or the operating system itself.

Memory Compaction and Best Fit Memory Allocation

Memory Compaction

Memory compaction is a memory management technique used to overcome the problem of external fragmentation. When processes are loaded and removed from memory over time, free memory becomes scattered in small, non-contiguous blocks. Even if the total free memory is sufficient to accommodate a new process, no single contiguous block may be large enough.

In compaction, the OS shuffles all occupied memory partitions together (toward one end of memory), merging all the scattered free holes into one large contiguous free block.

Key Points:

• Requires dynamic relocation (base register support)
• It is time-consuming and costly in terms of CPU overhead
• Not always possible if relocation cannot be done at runtime

Before Compaction:         After Compaction:
| P1  (20KB) |             | P1  (20KB) |
| Free (10KB)|             | P2  (15KB) |
| P2  (15KB) |    ---->    | P3  (5KB)  |
| Free (8KB) |             | Free (33KB)|
| P3  (5KB)  |             |            |
| Free (15KB)|             |            |

Best Fit Memory Allocation

Best Fit is a contiguous memory allocation strategy in which the OS searches the entire list of free memory holes and allocates the smallest hole that is large enough to satisfy the process's memory request.

Idea:

Allocate the hole that leaves the least leftover free space after allocation.

Advantages:

• Minimizes wasted space in each individual allocation
• Leaves larger holes available for bigger future requests

Disadvantages:

• Slower -- must search the entire free list every time
• Tends to create many tiny, unusable leftover fragments (small holes that are too small for any process) -- leading to external fragmentation

Example

Free Memory Holes (initially):

Process Requests:

Step 1: Allocate P1 (212 KB)

Search all holes for the smallest hole >= 212 KB:

• H1 = 100 KB -- too small
• H2 = 500 KB -- fits, leftover = 288 KB
• H3 = 200 KB -- too small
• H4 = 300 KB -- fits, leftover = 88 KB <-- smallest leftover
• H5 = 50 KB -- too small

Best Fit: H4 (300 KB) Remaining in H4 = 300 - 212 = 88 KB

Step 2: Allocate P2 (417 KB)

Updated holes: H1=100, H2=500, H3=200, H4=88, H5=50

• H2 = 500 KB -- fits, leftover = 83 KB <-- only hole large enough

Best Fit: H2 (500 KB) Remaining in H2 = 500 - 417 = 83 KB

Step 3: Allocate P3 (112 KB)

Updated holes: H1=100, H2=83, H3=200, H4=88, H5=50

• H1 = 100 KB -- too small
• H2 = 83 KB -- too small
• H3 = 200 KB -- fits, leftover = 88 KB <-- smallest leftover
• H4 = 88 KB -- too small
• H5 = 50 KB -- too small

Best Fit: H3 (200 KB) Remaining in H3 = 200 - 112 = 88 KB

Final State of Memory:

Notice that best fit leaves behind many small leftover fragments, which is its main drawback despite minimizing waste per allocation.

Translation Lookaside Buffer (TLB)

Definition

A Translation Lookaside Buffer (TLB) is a small, fast hardware cache (associative memory) that stores recently used page table entries. It acts as a high-speed lookup table used by the Memory Management Unit (MMU) to speed up the translation of logical (virtual) addresses to physical addresses.

Note: No specific reference notes were found for this topic; the answer is based on standard OS theory as taught in BSc CSIT curriculum.

Structure of TLB

Each entry in the TLB contains:

The TLB is implemented using associative memory, meaning all entries are searched simultaneously (in parallel), making lookup extremely fast.

Importance of TLB in Logical to Physical Address Conversion

Without TLB, every memory access requires two memory accesses:

1. One to fetch the page table entry (from main memory)
2. One to access the actual data/instruction

TLB eliminates this overhead in most cases.

Step-by-Step Address Translation with TLB

Logical Address = (Page Number p, Offset d)
                        |
                   Search TLB
                  /           \
            TLB Hit          TLB Miss
               |                 |
        Get frame f        Access Page Table
               |            (in main memory)
               |                 |
               |           Get frame f
               |           Update TLB
               |                 |
               +--------+--------+
                        |
              Physical Address = (f, d)
                        |
                  Access Memory

Case 1: TLB Hit

• The page number p is found in the TLB.
• The corresponding frame number f is retrieved directly.
• Physical address = f * page_size + d
• Only one memory access is needed (for actual data).

Case 2: TLB Miss

• The page number p is not found in the TLB.
• The page table in main memory is accessed to find frame f.
• The entry (p, f) is loaded into TLB for future use.
• Physical address is then formed.
• Two memory accesses are needed.

Effective Memory Access Time (EMAT)

$$EMAT = \alpha \times (T_{TLB} + T_m) + (1 - \alpha) \times (T_{TLB} + 2T_m)$$

Where:

• $\alpha$ = TLB hit ratio
• $T_{TLB}$ = TLB access time
• $T_m$ = Main memory access time

A high hit ratio (typically 90-99%) means most accesses are fast, greatly reducing average memory access time.

Summary of Importance

In conclusion, TLB is a critical hardware component that makes paged memory systems practical and efficient by caching frequently used address translations.