How to Implement Multi-Process Scheduling in C for OS Projects

For example, the assignment above asks you to:

• Build on a shell from a prior assignment or from starter code.
• Enhance it to support running concurrent processes, via an exec command that may take up to 3 scripts and a scheduling policy.
• Develop infrastructure for process management: code loading, process control blocks (PCBs), a ready queue, and scheduling logic.
• Implement multiple scheduling strategies (FCFS, SJF, RR, AGING), test with provided scripts, and finally support multi-threading.

Action Step: Start by itemizing every required feature and making notes on how components link together. This early investment clarifies what you’ll build and when.

2. Decide on Starter Code and Workspace Setup

You are usually given options: use your own previous solution or an official baseline. If your prior work is solid and passes all test cases, it’s typically best to build on it—you’re already familiar with its structure and quirks. Otherwise, wait for the provided solution and study it carefully.

• Version control is not optional. Set up Git (or required system) from day one. Commit early and often, especially before major changes.
• Organize your codebase as per assignment expectations so grading scripts will work smoothly (e.g., required use of make and specific target names like make mysh).

3. Break Big Problems Into Manageable Parts

Large assignments like this are intimidating until you split them into components. Here’s how you might break down a scheduling assignment:

A. Code Loading

Modify your shell so that when a script is run, the script's lines are loaded into a shared shell memory. Decide on a data structure—a simple contiguous array for all lines, or a more flexible structure for future scalability.

B. PCBs (Process Control Blocks)

Each running process should be represented by a PCB structure, holding at minimum:

• Unique process ID (PID)
• Start location and length in shell memory
• Current program counter (which line to execute next)

You may later want to store the scheduling "score" for policies like SJF or AGING.

C. Ready Queue

Implement a structure (often a linked list or queue) to manage all PCBs that are ready to run. For single-process (as with run), the queue has one process; with exec, it includes all concurrently scheduled processes.

D. Scheduler Logic

The heart of your assignment: run processes from the ready queue following the active scheduling policy.

4. Implement Robust Process Scheduling Infrastructure

A. Loading Code and Assigning PCBs

• Check available shell memory and assign a block to the script.
• Create a PCB pointing to the right block and initialize its program counter to zero.

B. Queueing and Cleanup

Add each PCB to the queue. When a process terminates, remove its PCB and free any memory or resources it used.

C. Scheduler Loop

Your scheduler inspects the queue and, policy permitting, selects the next ready process. For the initial implementation, use FCFS (first-come, first-served): run the head of the queue until it finishes, then move to the next.

Example Flow:

• Load scripts prog1, prog2, prog3
• Create PCBs and enqueue them
• Loop: run head of queue (prog1), when done, dequeue and continue with the next.

5. Extend the Shell Command System (exec)

Now, your shell’s exec command must:

• Accept up to three script names and a policy keyword (FCFS, SJF, RR, AGING).
• Validate input, ensuring policy and arguments are correct and not duplicated.
• Load source code for each script in shell memory, reporting errors (e.g., insufficient memory or duplicate filenames) immediately and cleanly.
• Enqueue all PCBs.

When supporting single-scriptexec, the behavior must match run—use this as a test for correctness.

6. Implement Multiple Scheduling Policies

Here’s where theory meets practice. Each policy simulates a real-world OS scenario.

A. FCFS (First-Come, First-Served)

Simplest—you always run the front PCB until it is finished.

B. SJF (Shortest Job First)

Estimate script length by code lines; sort PCBs so shorter jobs run first.

• When enqueuing, sort by job length.
• When a process finishes, move to the next shortest.

C. RR (Round Robin)

Use time slicing, e.g., two instructions per process before yielding to the next in the queue.

• Track a per-process counter in PCBs.
• After N instructions, enqueue the process at the end, pick the next.

D. AGING Policy

Combat starvation by periodically lowering the job length score of aging jobs.

• After each time slice, decrement scores for all PCBs (not the current one).
• If any now has a lower score than the running process, promote it to the front.

Practical Tips:

• Use explicit PCB fields to track scores, time slices, and current instruction.
• Test policies one at a time; don’t try to implement all at once.

7. Handle Error Checking and Edge Cases Early

Your scheduler will fail in mysterious ways without robust error handling:

• Scripts with identical filenames in the same exec command? Show an error and abort.
• Not enough space in shell memory for all scripts? Abort cleanly before any are enqueued.
• Unexpected arguments or missing policy keyword? Print a usage error.
• Launching more programs than allowed? Cap arguments at the allowed maximum (3 here).

8. Plan for Clean Resource Management

As processes finish:

• Dequeue their PCBs.
• Remove their section of shell memory, or mark it as free for future scripts.
• Ensure you avoid memory leaks accordingly (in C, pay attention to manual memory allocation/deallocation).

For each process execution, reset local state to avoid accidentally polluting other processes.

9. Testing: Embrace the Provided Test Cases

Assignments like this one provide many test cases for a reason. Use them!

• Set up an automated testing cycle: a script that runs your shell with each test input and compares it to expected output.
• Test both valid and invalid scenarios.
• For batch mode, confirm your shell does not hang and produces correct output with and without errors.
• Thoroughly test scheduling policies, especially edge behaviors like round-robin context switches and aging promotions.

10. Advance to Multi-threaded Scheduling (Advanced Step)

Later assignment steps might require converting the scheduler to handle concurrent execution (multi-threading, often with pthreads in C). This models how modern OSes really work.

Key concepts:

• Spawn a fixed pool of worker threads (e.g., two threads).
• Each thread picks up a ready process and executes its instructions independently.
• Use mutexes (thread locks) around shared resources (output, shell memory management) to prevent race conditions.
• Remember that with real concurrency, outputs become non-deterministic; your test cases may not match output line order, but the content counts must.

Practical details:

• Debug with simple scripts before scaling up.
• Use thread-safe printf or wrap output routines in mutexes.
• Clean up worker threads correctly when the shell receives a quit command.

11. Document, Comment, and Organize

Don’t treat documentation as an afterthought:

• Comment data structures (explain what each PCB field means, what the ready queue structure is, etc).
• Mark scheduling policy code clearly.
• Include a README with your code that explains how it is structured, how to compile and run, and what each file does.
• Remove unused variables and dead code before submission.

A well-documented project is easier to debug, extend, and grade.

12. Common Pitfalls and How to Avoid Them

• Not following assignment conventions: If the assignment says to use make mysh and a particular output pattern, do so exactly.
• Forgetting to free memory or PCBs: Leads to subtle bugs, especially as scripts and processes scale up.
• Off-by-one errors in scheduling: Especially common in round robin and aging policies. Use print statements for debugging.
• Assuming deterministic output with threads: In the multi-threaded part, explicitly note to instructors (and yourself) that output order can vary.

13. Workflow Example: Tackling a Scheduling Assignment from Start to Finish

Here’s how you might schedule your own work:

1. Read and Annotate all requirements, distill a list of features and edge cases.
2. Set Up Baseline by compiling starter code and running test scripts.
3. Implement Basic Scheduling Infrastructure: Add code loading, PCBs, and a basic ready queue.
4. Develop Each Policy in Isolation: Start with FCFS and test exhaustively. Only then add SJF, RR, and AGING, one by one, testing after every change.
5. Add Robust Error Handling at every user input and process launch stage.
6. Automate Testing so you can rerun all test cases after each change.
7. Progress to Multi-threading if required, starting with simple scripts and confirming thread safety.
8. Comment and Clean Up code, add a README, and make a clean submission on time.

14. Building Mastery: What You’ll Learn

Assignments like this force you to:

• Grapple with real-world OS concepts: context switching, concurrency, and fairness.
• Write C code that manipulates complex data structures reliably.
• Balance multiple moving parts (input parsing, memory limits, multithreading) at once.
• Anticipate and handle a wide range of user and program errors.
• Test and debug code to an industrial standard.

You leave not just with a grade, but with practical skills invaluable for operating systems work, systems programming, and job interviews.

15. Final Advice: Be Systematic, Start Early, and Ask for Feedback

Multi-phase assignments reward students who:

• Start implementation early and make steady progress,
• Break down big tasks into steady, manageable daily goals,
• Use version control for every significant new piece,
• Ask questions on forums or with TAs when stuck,
• Test incrementally and frequently.

Most importantly, remember: every OS engineer started with a project like this. It’s normal to find it complex, and persistence is the key to both completion and true understanding. Good luck!