/Teaching/Operating Systems/Assignments

Assignments A1 & A2

Before you start, read the Rules!

There are two assignments (50 points each, plus bonus points). Unlimited bonus points are available if you reached 40+ points on Assignment 2 through more thorough implementations and optional tasks. Assignment 1 focuses on Multithreading, Process Interaction, and Fork. Assignment 2 focuses on Virtual Memory. Each assignment starts with a Design Proof-of-Concept (PoC), which is graded by automated tests – you will have a short non-graded review meeting with your tutor. The Design Proof-of-Concept (PoC) is part of the overall assignment points.

Minimum Overall Score:

      • 30 points if you do not pass the student design debate (or, for A1, the preparatory assignment A0).
      • 25 points if you pass these preparatory requirements.
      • At least half of the points must come from the mandatory parts
      • Every team member must contribute points to the mandatory parts
      • At least 0.5 points on the design proof-of-concept

Assignment A1

Task 1: Multithreading

(Approx. 20 points)

Objective:
Upgrade the SWEB kernel (currently single-threaded) to support full multithreading.

Key Requirements:

      • Implement POSIX-compliant syscalls:
        • pthread_create
        • pthread_exit
        • pthread_cancel
        • pthread_join
      • Manage thread resources correctly (individual stacks, registers, etc.) while sharing the process’s address space.
      • Provide user programs to demonstrate functionality.

Grading Highlights:

      • Basic features: Correctly split up kernel resources for processes and threads, implement functioning syscalls, and correct context management.
      • Extra features: Guard pages, dynamic stack growth, proper return values, cancellation points, and handling joinable/detached threads.
      • Deductions: For non-standard behavior, missing parameter checks, or poor synchronization (-2 for most race conditions, -3 if they indicate complete ignorance of how locking works).

Task 2: Fork

(Approx. 10 points)

Objective:
Implement the fork syscall (with exec support) for launching new processes.

Key Requirements:

      • Fork creates an exact copy of the current process (only the calling thread is duplicated).
      • Duplicate process structures (especially page tables) and optionally use Copy-on-Write (COW) on the lowest level.
      • Correctly copy local file descriptors.

Grading Highlights:

      • Basic features: Creation of new process objects, proper copying of process data, and support for multithreading.
      • Deductions: For poor synchronization, poor resource duplication, or inadequate testing (deductions for no tests/too few tests).

Optional Additional Tasks

Extra features can earn additional points. Consult your tutor before starting optional work, especially if it overlaps with Assignment 2. Come up with your own ideas, come up with your own improved variants of features.

Optional Areas Include:

      • Process Manipulation: Additional support for exec, pipes, and waitpid.
      • User-Space Synchronization: Implement semaphores, mutexes, condition variables, and optionally spinlocks.
      • Miscellaneous Enhancements: Extra I/O syscalls (e.g., ls, rm, mkdir), precise implementations of sleep and clock functions.
      • Additional Architectures: Support for x86 (32-bit/PAE), ARM, RISC-V, New ISA, etc.
        (Extra architecture points are capped at 50% of your overall score.)
      • Anything OS / kernel-related you can think of

Final Reminders

      • Follow Tutorials: Review all provided materials and guidelines.
      • POSIX Compliance: Strictly adhere to POSIX standards for function names, parameters, and behavior.
      • Thorough Testing: Ensure robust testing (numerous tests for basic cases and corner cases) for both mandatory and optional features. No points for untested features. Deductions for too few tests.
      • Participation Impact: Your minimum overall score depends on participation in the student design debate and preparatory assignment A0.
      • Poor Synchronization: Race conditions, overlocking, busy waiting, “function locking”, etc. are by far the highest deductions on average across all groups every year. Don’t lose your points here.

Assignment 2

Mandatory Task: Virtual Memory (≈40 points)

In this assignment, you will dive deep into virtual memory by extending SWEB’s basic paging and on-demand-loading with swapping and copy-on-write (CoW).

Swapping

  • Overview:
    When a process uses more memory than physically available, your system must select pages for swap-out and later swap them back in on demand.
  • Key Requirements:
    • Implement a kernel thread dedicated to selecting pages for swap-out.
    • Ensure that requesting a free physical page never fails (unless the swap device is full).
    • Use the swap partition on the block device for writing swapped-out pages.
    • Implement a page replacement algorithm that goes beyond FIFO (e.g., Aging or WSClock/WSRandom); better strategies yield more points.
    • Write test programs that allocate more memory than is physically available.
    • Visualize virtual memory and swap statistics (e.g., a log, numbers, table, or graph).

Copy-on-Write (CoW)

  • Overview:
    CoW reduces memory usage by sharing identical pages between processes until a write occurs.
  • Key Requirements:
    • Mark pages as CoW when forking.
    • On a write access to a shared, read-only page, trigger a page fault that copies the page and sets it as writable.
    • Ensure that CoW pages remain correctly shared among processes, even after being swapped out/in.

Optional Additional Tasks

These tasks are available to earn extra points beyond the mandatory 40 points. Discuss your ideas with your tutor before starting any optional work to avoid overlap with Assignment 1.

  • Memory-Mapped I/O and Shared Memory:
    Implement basic mmap, multiple mappings of the same object, and shared memory support (including proper handling with swapping and CoW).
  • Suspend to Disk / Shutdown:
    Implement features for freezing and saving the system state to disk, proper shutdown procedures, and recovery (e.g., ACPI power-off, clean shutdown).
  • Security Enhancements:
    Add features like ASLR for userspace, stack canaries, W ⊕ X policies, seccomp filters, and improved user management and file access rights.
  • Dynamic Memory Allocation (malloc):
    Implement a robust malloc/free (using sbrk or mmap) that works in a multithreaded environment.
  • Other Enhancements:
    Extra drivers (e.g., network, sound, graphics) or support for additional architectures (e.g., x86, ARM, RISC-V) are welcome. (Note: Additional architecture points are capped at 50% of your overall score.)

Final Reminders

  • Thorough Testing: Your implementation must be robust—test both mandatory and optional features extensively (deductions for no tests/too few tests). No points for untested features. Deductions for too few tests.
  • Strict POSIX Compliance: Follow POSIX standards for system calls, parameter handling, and behavior.
  • Design and Performance: The solution should not negatively impact performance unless physical memory limits are reached.
  • Consult Early: If in doubt, talk to your tutor about your approach or optional features.
  • Poor Synchronization: Race conditions, overlocking, busy waiting, “function locking”, etc. are by far the highest deductions on average across all groups every year. Don’t lose your points here.
  • Other types of deductions you already know from A1 are still relevant.