Matthew's Notes

Search

SearchSearch

Lab 3 Writeup - 354

Feb 20, 2025, 9 min read

So. I plan to try and do a writeup for each of the remaining labs. Both as a helpful thing for other people doing it and to better my own understanding of the material. None of the information here is guaranteed to be correct. Also importantly, none of this is supposed to be giving you the answers straight up. It’s more of a guide to reading and understanding the lab spec than anything. I will only give details of things that are from the lab spec or things I found helpful while working on the lab, but any and all code is on your own. Read the lab spec before using this, even though I’ll likely repeat a LOT of things from the spec.

Part 1 (Labeled as 3 idky) - 100 pts

Implementing producer and consumer processes that coordinate with semaphores.

Circular Buffer

First thing is to create a circular buffer. Define it in include/cb.h as a global static array of characters called cbuffer. The size will be a defined variable, #define BUF_SIZE 50. You will also need the head and tail pointers, uint32 cb_head and uint32 cb_tail.

// system/cb.c

void cb_init() {
	// Initialize the circular buffer.
	// Call this function once in system/intialize.c somewhere
}

void cb_insert(char ch) {
	// Add one character into the head of `cbuffer`. Increment cb_head accordingly.
	// Buffer is circular, if the head reaches the end of the buffer, reset it to 0
}

char cb_remove() {
	// Remove one character from the tail of `cbuffer` and return it. Increment the tail int accordingly.
	// Same as insert, buffer is circular don't forget.
}

Notes

  • These functions will be used with semaphores in the producer and consumer processes later
  • In a standard circular buffer implementation you might worry about inserting when the buffer is full or removing when its empty. In our implementation we are ignoring these things. Our cb_* calls should be blind, they shouldn’t care about anything. - Ed Discussion

Circular Buffer

What exactly is a circular buffer? Put simply, its an array. That’s it lol. You insert things at the head index and remove things from the tail, making it a FIFO array. When you get to the end, the indices circle back around to the start, hence circular buffer. That’s pretty much it. It’s just as simple as you think. To print the buffer, you have to print each character going from the tail to the head, making sure to loop around when you get to the end of the buffer.

Producer and Consumer Processes

Define any data structures (like semaphores) that you need in include/pc.h. Then implement the following functions.

// system/pc_init.c
void pc_init() {
	// Initialize any data structures from the header file here. Call this function in the same place you call cb_init() (or somewhere else in initialize, you do you)
}
// system/pc_produce.c
void pc_produce(char* str, uint32 len) {
	// The first len number of characters (starting from the beginning of str) should be inserted into cbuffer
	// The total length of str will always be equal or greater than len
	// Use cb_insert(ch) to insert characters one by one
	// Note this needs to coordinate with other producers/consumers over the access of the buffer
}
// system/pc_consume.c
void pc_consume(char* buf, uint32 len) {
	// Remove len number of characters from cbuffer and write them to buf
	// The total length of str will always be equal or greater than len
	// Use cb_remove() to remove characters one by one from the buffer
	// Note this needs to coordinate with other producers/consumers over the access of the buffer
}

Notes

  • These three functions are in separate files
  • Semaphores are done on the atomic scale, not for the entire inserting of len characters. See Ed Discussion for more details. Asker describes what it would be on a non-atomic scale, you don’t want to worry about that.

Testing

Since they describe how to setup main for testing in the lab spec I won’t provide any main code here. Start with a simple case where there are producer and consumer processes calling pc_produce() and pc_consume() respectively. Try not to make the buffer full. Try more complicated cases like adding more processes or forcing the buffer to be full. While I was testing I had a process constantly printing the buffer to keep track of what it looked like. I also made use of sleep calls so I could time things and not have my screen spammed with tons of characters. I found it quite hard to make sure this section was being done correctly, if anyone comes up with good ways of testing this section of lab let me know and I’ll add here.

Deadlock Detection - 100 pts

Resource Graph

We are going to create a semaphore resource allocation graph (resource graph). The graph will have nodes and edges as follows:

  • Nodes - Nodes are either a process or a semaphore
  • Edges - An edge encodes a semaphore being owned/held by a process or a process requesting/waiting for a semaphore

You can define your own data structures for the resource graph. Any custom data structures not extending the XINU default ones should be specified in include/dl.h. Some assumptions/restrictions on our graph

  • Only static memory allocation. No dynamic memory allocation primitives like getmem() (essentially no malloc())
  • We will only consider cases where any process can request/wait for one semaphore and any semaphore can be owned/held by one process. Basically each node will only have one outgoing edge and only one incoming edge. Ever.

That’s all you get for this section. You can choose to implement the graph in code however you want. Pull out the CS 251 notes everyone. I would link mine but unfortunately I don’t have them :). Personally, I made it so if an edge was going from a process to a semaphore, it indicated that process waiting on that semaphore. If a semaphore had an edge connecting to a process, it meant that process was in control of that semaphore. You can look here for more general information on the actual resource graph Resource Allocation Graph (RAG) in Operating System - GeeksforGeeks. This doesn’t have implementation details (at least not this link).

Maintaining the Graph with System Calls

We will implement two new system calls. (Hopefully my notes about the resource graph make sense, if not ignore them and use lab spec)

// system/dl_wait.c
syscall dl_wait(sid32 sem) {
	// IT IS IDENTICAL TO WAIT WITH TWO EXCEPTIONS
	// When a process is put into a semaphore queue, change its state to PR_DLWAIT instead of PR_WAIT (define PR_DLWAIT in include/process.h)
	// Also update the resource graph properly. Both if the process is waiting on this semaphore (put into queue) or if the process continues running and now "controls" this semaphore
}
// system/dl_signal.c
syscall dl_signal(sid32 sem) {
	// IT IS IDENTICAL TO SIGNAL EXCEPT FOR ONE THING
	// The resource graph should be updated when a process dequeues from a semaphore and becomes ready.
	// This includes both if a process is removed from waiting for this semaphore and if a semaphore is no longer controlled by a process
}

Outputting a deadlock

// system/print_deadlock.c
void print_deadlock() {
	// Check if theres a cycle in the resource graph (this will vary depending on graph implmentation)
	if (no cycle) {
		kprintf("At %d seconds, no deadlock detected.\n", clktime); // Lab spec gives you this (well not the kprintf but thats obvious lol)
	}
	else {
		// Theres a cycle! That means deadlock!
		kprintf("At %d seconds, a deadlock is detected!\n", clktime);
		// Print any cycle in the graph in a readable manner
		// I printed it something like  1 -> 2 -> 3 -> 1 -> cycle continue
	}
}

Modify system/clkhandler.c so that it calls print_deadlock() every second since bootload time (`clktime = 0, 1, 2, …)

**To reduce overhead on the serach, set both NPROC and NSEM to 20 for this lab. This is done by going to the config/Configuration file **

Test cases

Test this with a deadlock scenario of 2 processes and 2 semaphores. The dl_wait and dl_signal calls should occur in a specific sequence. Try it agian with 3 processes and 3 semaphores deadlocking. Make sure the graph cycle printed is actually a cycle, etc.

Notes

  • Don’t worry about making dl_wait work with signal and vice versa. If dl_wait is called, there will always be a corresponding dl_signal just like wait and signal
  • If you need help generating a deadlock scenario, ChatGPT is great at it

Bonus Problem - 25 pts

There’s no code necessary for this. Instead, you will put your answer into lab3.pdf in the lab3 source directory. Here is the bonus problem straight from lab spec if you’re lazy.

Consider a hypothetical scenario where dl_wait() is modified in a way that it returns an error (say, SYSERR_DL) when calling dl_wait() would result in a cycle in the resource graph (instead of blindly allowing the cycle). Assume that a developer has built some program, and it turns out a call to dl_wait() from some process has returned SYSERR_DL. What would be a rational way to fix this problem from the developer’s perspective? Provide one approach and explain your reasoning in lab3.pdf (place the pdf under lab3/ directory). Try to be brief and concise (e.g., aim for one or two paragraphs). Basic approaches, such as terminating the offending process, or sleeping and then attempting to call dl_wait(), will not be accepted.

Turn In

Same as past two labs, nothing new here. Don’t forget to remove any extra kprintf statements (or use macros and such).

Helpful Links

Graph View

Backlinks