Mini Project 1 - Operating Systems and Networks

This project implements three major components: a C Shell, a Networking Protocol (S.H.A.M.), and xv6 Operating System modifications. Each component demonstrates fundamental concepts in systems programming.

Project Structure

mini-project1/
├── shell/                  # C Shell Implementation
│   ├── src/               # Source files
│   ├── include/           # Header files  
│   ├── Makefile           # Build configuration
│   └── shell.out          # Compiled binary
├── networking/            # S.H.A.M. Protocol Implementation
│   ├── client.c           # Client implementation
│   ├── server.c           # Server implementation
│   ├── sham.h             # Protocol header definitions
│   └── Makefile           # Build configuration
├── xv6/                   # xv6 OS Modifications
│   ├── xv6_modifications.patch  # Patch file for changes
│   ├── readcount.c        # User program for system call
│   └── report.md          # Implementation report
└── README.md              # This file

---

1. C Shell [645 Points]

A fully functional Unix shell with advanced features including job control, I/O redirection, pipes, and background execution.

Features Implemented

Part A: Shell Input (65 points)

• Shell Prompt: Dynamic prompt showing <Username@SystemName:current_path>
• User Input: Interactive command input with proper parsing
• Input Parsing: Context-free grammar parser supporting complex command structures

Part B: Shell Intrinsics (70 points)

• hop: Directory navigation with support for ~, ., .., -, and absolute/relative paths
• reveal: File listing with flags (-a for hidden files, -l for line format)
• log: Command history with persistence, execution, and purging capabilities

Part C: File Redirection and Pipes (200 points)

• Command Execution: Arbitrary command execution with error handling
• Input Redirection: command < file support
• Output Redirection: command > file and command >> file support
• Command Piping: Multi-stage pipelines with command1 | command2 | ...

Part D: Sequential and Background Execution (200 points)

• Sequential Execution: command1 ; command2 ; ... support
• Background Execution: command & with job tracking and status reporting

Part E: Exotic Shell Intrinsics (110 points)

• activities: List all running/stopped processes
• ping: Send signals to processes
• Signal Handling: Ctrl-C, Ctrl-D, and Ctrl-Z support
• Job Control: fg and bg commands for job management

How to Build and Run

cd shell/
make all                    # Compiles to shell.out
./shell.out                 # Run the shell

Usage Examples

# Basic commands
<user@host:~> echo "Hello World"
<user@host:~> ls -la

# Directory navigation
<user@host:~> hop /tmp
<user@host:/tmp> hop ~
<user@host:~> hop ..

# File operations
<user@host:~> reveal -la
<user@host:~> cat file.txt > output.txt
<user@host:~> grep "pattern" < input.txt

# Pipes and redirection
<user@host:~> cat file.txt | grep "pattern" | sort > sorted.txt
<user@host:~> ls | wc -l

# Background execution
<user@host:~> sleep 10 &
[1] 1234
<user@host:~> activities
[1234] : sleep - Running

# Job control
<user@host:~> sleep 100
^Z
[1] Stopped sleep
<user@host:~> bg 1
[1] sleep &
<user@host:~> fg 1

# Command history
<user@host:~> log
<user@host:~> log execute 1
<user@host:~> log purge

---

2. Networking - S.H.A.M. Protocol [80 Points]

A reliable UDP-based protocol implementing TCP-like features including connection management, flow control, and retransmission.

Features Implemented

Core Functionalities

• S.H.A.M. Packet Structure: Custom header with sequence numbers, acknowledgments, flags, and window size
• Connection Management: 3-way handshake for establishment, 4-way handshake for termination
• Data Sequencing and Retransmission: Sliding window, cumulative ACKs, timeout-based retransmission
• Flow Control: Window-based flow control mechanism

Modes of Operation

• File Transfer Mode: Reliable file transfer with MD5 verification
• Chat Mode: Real-time bidirectional communication with graceful termination

Testing Features

• Packet Loss Simulation: Configurable packet loss for testing reliability
• Verbose Logging: Detailed protocol events with microsecond timestamps

How to Build and Run

cd networking/
make                        # Compiles client and server

# File Transfer Mode
./server <port> [loss_rate]
./client <server_ip> <port> <input_file> <output_file> [loss_rate]

# Chat Mode  
./server <port> --chat [loss_rate]
./client <server_ip> <port> --chat [loss_rate]

# With verbose logging
RUDP_LOG=1 ./server 8080 --chat 0.1
RUDP_LOG=1 ./client 127.0.0.1 8080 --chat 0.1

Usage Examples

# File Transfer
Terminal 1: ./server 8080
Terminal 2: ./client 127.0.0.1 8080 input.txt received_file.txt
# Output: MD5: <32-character_hash>

# Chat Mode
Terminal 1: ./server 8080 --chat
Terminal 2: ./client 127.0.0.1 8080 --chat
# Type messages, use /quit to exit

# With packet loss simulation
Terminal 1: ./server 8080 --chat 0.3    # 30% packet loss
Terminal 2: ./client 127.0.0.1 8080 --chat 0.1  # 10% packet loss

# Verbose logging for debugging
Terminal 1: RUDP_LOG=1 ./server 8080 0.2
Terminal 2: RUDP_LOG=1 ./client 127.0.0.1 8080 test.txt output.txt 0.1
# Check server_log.txt and client_log.txt for detailed protocol events

Protocol Features Demonstrated

• Reliability: Automatic retransmission of lost packets
• Ordering: In-order delivery using sequence numbers
• Flow Control: Prevents overwhelming the receiver
• Connection State: Proper connection establishment and teardown
• Error Recovery: Handles packet loss gracefully

---

3. xv6 Operating System Modifications [140 Points]

Enhancements to the xv6 operating system including new system calls and alternative scheduling algorithms.

Features Implemented

Part A: Basic System Call (40 points)

• getreadcount(): System call tracking total bytes read across all processes
• User Program: readcount.c demonstrating the system call functionality

Part B: Completely Fair Scheduler (CFS) (100 points)

• Priority Support: Nice values affecting process weights
• Virtual Runtime Tracking: Fair CPU time distribution
• Dynamic Scheduling: Always schedules process with lowest virtual runtime
• Time Slice Calculation: Adaptive time slices based on system load

How to Build and Run

cd xv6/
# Extract and apply modifications
unzip xv6-riscv.zip
cd xv6-riscv/
patch -p1 < ../xv6_modifications.patch

# Build with different schedulers
make clean
make qemu                          # Default round-robin
make qemu SCHEDULER=FCFS          # First Come First Serve
make qemu SCHEDULER=CFS           # Completely Fair Scheduler

# Test the system call
$ readcount

Usage Examples

# Testing getreadcount system call
$ readcount
Initial read count: 0
Read 100 bytes
Final read count: 100

# Testing different schedulers
# In xv6 shell, use Ctrl-P to see process information
$ schedulertest                    # Run scheduler test program
$ (Ctrl-P)                        # Print process states

# CFS scheduler shows virtual runtime information
[Scheduler Tick]
PID: 3 | vRuntime: 200
PID: 4 | vRuntime: 150  
PID: 5 | vRuntime: 180
--> Scheduling PID 4 (lowest vRuntime)

Scheduling Algorithms

1. Round Robin (Default): Equal time slices for all processes
2. FCFS: First Come First Serve based on creation time
3. CFS: Fair scheduling based on virtual runtime and process weights

---

Testing and Verification

Shell Testing

cd shell/
./shell.tcl                 # Automated test suite
VERBOSE=1 ./shell.tcl       # Detailed test output

Networking Testing

cd networking/
# Basic functionality
./server 8080 &
./client 127.0.0.1 8080 test.txt output.txt
diff test.txt output.txt    # Should be identical

# Stress testing with packet loss
RUDP_LOG=1 ./server 8080 --chat 0.5 &
RUDP_LOG=1 ./client 127.0.0.1 8080 --chat 0.3
# Check logs for retransmissions and recovery

xv6 Testing

cd xv6/xv6-riscv/
make qemu SCHEDULER=CFS
# In xv6: run readcount, schedulertest
# Use Ctrl-P to monitor process states

Dependencies

Shell

• GCC with C99 support
• POSIX-compliant system
• Standard C library

Networking

• OpenSSL library for MD5 calculation

  # Linux
  sudo apt update && sudo apt install libssl-dev
  
  # macOS
  brew install openssl

xv6

• RISC-V toolchain
• QEMU emulator
• Make build system

Key Implementation Details

Shell Architecture

• Modular design with separate files for parsing, execution, signals, etc.
• Recursive descent parser for command grammar
• Process group management for job control
• Signal handling for interactive features

Networking Protocol

• UDP-based reliable transport
• Sliding window with cumulative acknowledgments
• Exponential backoff for retransmissions
• Flow control using advertised window

xv6 Enhancements

• System call interface extensions
• Scheduler algorithm abstractions
• Process control block modifications
• Kernel-user space communication

Error Handling

All components include comprehensive error handling:

• Invalid syntax detection and reporting
• Network error recovery and retransmission
• System call failure handling
• Resource cleanup on termination

---

Each component can be built and tested independently, making it suitable for incremental development and debugging.