Kernel System Calls, Synchronization, and OS Concepts

Implementing a New System Call in the Kernel

Required Files to Add

• /usr/src/test_kernel/SystemCalls/test_call.c:
  • Creates system call pointer.
  • Exports the pointer so that the system call module can access it.
  • Defines the system call wrapper.
• /usr/src/test_kernel/SystemCalls/Makefile: obj-y := test_call.o (Compiles files directly into the kernel).

System Module Implementation

• /usr/src/test_kernel/SystemModule/syscallModule.c:
  • Holds module code.
  • Implements system call behavior.
  • Registers system call pointer to the proper system call handler.
• /usr/src/test_kernel/SystemModule/Makefile: obj-m := syscallmodule.o (Compiles file as a module).

Required Files to Modify

• /usr/src/test_kernel/arch/x86/entry/syscalls/syscall_64.tbl: Add the system call to the table.
• /usr/src/test_kernel/include/linux/syscalls.h: Define the system call prototype.
• /usr/src/test_kernel/Makefile: Add the SystemCalls directory to the list.

Note: Adding a new system call requires recompiling and reinstalling the whole kernel.

Readers-Writers Synchronization Problem

Roles and Actions

• Reader:
  • Wait until no writers.
  • Access database.
  • Wake up waiting writers.
• Writer:
  • Wait until no active readers or writers.
  • Access database.
  • Wake up any waiting readers or writers.

Synchronization Variables

activeReaders = 0;
activeWriters = 0;
waitingReaders = 0;
waitingWriters = 0;
Condition okToRead = NULL;
Condition okToWrite = NULL;
Lock lock = FREE;

Reader Function Implementation

Reader() {
    lock.Acquire();
    while (activeWriters > 0 || waitingWriters > 0) {
        ++waitingReaders;
        okToRead.Wait(&lock);
        --waitingReaders;
    }
    ++activeReaders;
    lock.Release();
    // access database
    lock.Acquire();
    --activeReaders;
    if (activeReaders == 0 && waitingWriters > 0) {
        okToWrite.Signal(&lock);
    }
}

Writer Function Implementation

Writer() {
    lock.Acquire();
    while (activeWriters > 0 || activeReaders > 0) {
        ++waitingWriters;
        okToWrite.Wait(&lock);
        --waitingWriters;
    }
    ++activeWriters;
    lock.Release();
    // access database
    lock.Acquire();
    --activeWriters;
    if (waitingWriters > 0) {
        okToWrite.Signal(&lock);
    } else if (waitingReaders > 0) {
        okToRead.Broadcast(&lock);
    }
    lock.Release();
}

Deadlock Conditions and Prevention

Four Necessary Conditions for Deadlocks

All four conditions must be true simultaneously for a deadlock to occur. Removing any one condition prevents deadlock.

1. Mutual Exclusion (Limited Access): Resources are non-sharable.
2. No Preemption: Resources cannot be forcibly taken away from a process holding them.
3. Hold and Wait (Wait while Holding): A process holds at least one resource and is waiting to acquire additional resources held by other processes.
4. Circular Wait (Circular Chain Request): A set of processes exists such that $P_i$ is waiting for a resource held by $P_{i+1}$ (modulo $n$).

Six Deadlock Prevention Techniques

1. Eliminate Mutual Exclusion: Infinite resource / No sharing.
2. Eliminate Hold and Wait (Pre-allocation): Independent threads allocate all the resources at the beginning, or if you need both, grab them at the same time.
3. Eliminate Circular Wait (Resource Ordering): Make everyone use the same ordering in accessing resources.
4. No Waiting (Phone Company Model): If a resource is unavailable, the process releases all held resources and tries again later.
5. Preempt Resources: Preempt resources (e.g., copy memory content to disk).
6. Banker's Algorithm: A combination of techniques (Resource Allocation Denial).

Switching Between Kernel and User Spaces

Kernel to User Mode Steps (7 Steps)

1. Creates a process.
2. Initializes the address space.
3. Loads the program into the memory.
4. Initializes translation tables.
5. Sets the hardware pointer to the translation table.
6. Sets the CPU to user mode.
7. Jumps to the entry point of the program.

User to Kernel Mode Mechanisms

The switch from user to kernel mode occurs through voluntary or involuntary mechanisms.

• Voluntary Mechanism: Through the use of system calls, where a user application asks the operating system to do something on the user’s behalf.
• Involuntary Mechanisms: By hardware interrupts (e.g., I/O) and program exceptions (e.g., segmentation fault).

Memory Management: Cache Misses and TLB Lookups

Four Types of Cache Misses

• Compulsory Misses: Data brought into the cache for the first time (e.g., booting).
• Capacity Misses: Caused by the limited size of a cache.
• Conflict Misses (Misses due to competing cache entries): A cache entry assigned to two pieces of data. When both are active, each will preempt the other.
• Policy Misses: Caused by the cache replacement policy, which chooses which cache entry to replace when the cache is full.

Ways to Perform TLB Lookups

TLB lookups can be performed via sequential search or parallel methods:

1. Sequential search of the TLB table.
2. Direct Mapping: Assigns each virtual page to a specific slot in the TLB.
3. Set Associativity: Uses N TLB banks to perform lookups in parallel.
4. Fully Associative Cache: Allows looking up all TLB entries in parallel.

Disk Access Time Metrics

• Disk Access Time: Seek time + rotational delay + transfer time
• Latency: Seek time + rotational delay
• Bandwidth: Bytes transferred / disk access time