Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

An Operating System Simulator
COMP2007
Operating Systems and Concurrency Coursework
Specification v1.02
Dan Marsden and Geert De Maere
2024

1 Introduction

The purpose of this years coursework is to implement a simulator of an operating system. Completing this coursework will require understanding of both operating system design and multi-threaded programming. Once the concurrency topic has been covered in lectures, you should have all the background that you need to complete this coursework.

Several simplifying assumptions are made to keep the task manageable. In particular:

2 The simulator design

The core components of the simulator are shown in Figure 1. Their purposes is explained in more detail below.

The simulator pretends to be a simple operating systems. It provides:

The evaluator pretends to run processes. It provides:

The environment pretends to be the “outside world” requesting functionality of the operating system. It provides:

The event source notifies the simulator of IO events. It provides:

The logger implements logging functionality for the various other components.

The source code available on Moodle includes a complete implementation of the evaluator and trivial implementations of the interface functions required of the other components. Filling in the remaining functionality will be the aim of the coursework.

This initial description will probably be hard to digest, and may be overwhelming. The sections below provide more details, and break the task down into more manageable parts.

3 Getting started

3.1 Working on the department Linux environment

3.2 Extracting the files

The directory now contains the zip file, several C header and source files, and a makefile. These are described in more detail in Section 3.3.

3.3 What’s provided?

Some of the C code provides functionality to help with the project:

3.4 Using the code

make coursework

This should run a series of compilation steps, and complete successfully. Once this has completed, an executable file named coursework appears in the same directory. You can run this executable as follows:

The program should quickly complete successfully, but without printing anything out, or doing anything interesting. It will do more as you start adding your own code following the steps outlined in Section 4.

There are also some other things you can do with the provided makefile. Type the command:

It will compile and then run some unit tests for the provided linked list implementation. The tests should succeed, leaving a new file called list.tested. 

Similarly, you can run some unit tests for the evaluator by typing: 

make evaluator . tested

Finally, type:

It will remove all the files generated by the makefile. It can be useful to clean if your build gets into a state you don’t understand, or if you just want to prepare to run the whole build from scratch. Note this will even remove the zip file, as this can be regenerated from the source files by typing: 

make coursework . tar.gz

This feature will be used in Section 5, which describes how to submit your work.

4 Project instructions

• Please don’t modify the files you were asked to leave unchanged in Section 3.3.
• Please don’t add new source files. The coursework is designed so you only need to modify some of the provided files, and the marking process will assume this is how things have been done.
• You may use the C standard library, the standard Unix libraries, and the Posix threading library (pthreads). Please do not introduce other libraries to the project.
• You should avoid busy waiting in your solution whereever possible.
• For the other provided (.c) and (.h) files:
• Some function definitions are already provided, and you will be asked to fill in the details in the various parts below.
• You can add other code such as data types, global variables, and other functions in these files as needed to complete the tasks.
• The files utilities.h and utilities.c can be used for code that you want to reuse in different parts of the project. Place new declarations in the header (.h) file, and the corresponding definitions in the source (.c) file. To get you started, we have provided two utility functions:
• checked_malloc - A wrapper around the usual malloc function which aborts if the memory allocation fails. The coursework does not require you to handle memory allocation failures, but knowing they have occurred may help reveal other bugs.
• checked_free - A wrapper around the usual free function that asserts it hasn’t been passed a null pointer. You can use these functions if they prove useful in your projects. You should also follow the same pattern if you introduce other utility functions of your own.
• To provide a double-check to make sure student work is correctly associated with the right student, if you modify a C source file (.c file), please add a comment on the top line with your name and student ID in. For example:

// Student : Ada Lovelace ID: 123456789

Before starting, it might be worth reading the assessment guidance in Section 7 to understand how your work will be evaluated.

4.1 Implementing the logger

3802 : 16:44:23 : Simulator thread 1 terminated

Note that the time may not be accurate enough to increase every message, but the message counter will. You may need to add some setup and shutdown code to the logger. If so, modify the implementations of logger_start and logger_stop accordingly.

To check your implementation, you can recompile and run coursework. You should now see a couple of messages printed to the terminal during a run of the program.

4.2 Implementing a non-blocking queue

The aim of this section is to implement a non-blocking queue of unsigned int values which may be useful in later parts. A non-blocking queue is a queue where pop calls fail if no data is available, rather than blocking until another thread pushes a value.

If you don’t require this component later, you should still implement it as the code will be assessed. You should use the provided doubly linked list implementation to help you in this task.

To get you started, an outline implementation is provided in non_blocking_ queue.h and non_blocking_queue.c. The header file has the following contents:

You should modify the code in non_blocking_queue.c as follows:

You may also need to add other supporting code in these files, such as suitable type definitions or additional functions. You can also add or use functions from the files utilities.h and utilities.c.

The queue should be designed so it is safe to use in multi-threaded code.

You also should write some tests for your code. If you run 

make non_blocking_queue . tested 

two very simple tests will run, and the second will fail. You should modify the code in non_blocking_queue.tests.c to contain suitable tests of the correctness of your non-blocking queue, and remove the two example tests. If you want an example of how to write some more realistic tests, looking in list.tests.c may help. We are using assertions to check properties during the tests. If you need details about assertions, these can be found in Appendix A.

4.3 Implementing a blocking queue

The aim of this section is to implement a blocking queue of unsigned int values which may be useful in later parts. A blocking queue is a queue where pop calls block if no data is available, until another thread pushes a value.

As with the non-blocking queue, even if you don’t require this component later, you should still implement it as the code will be assessed. You should use the provided doubly linked list implementation to help you in this task.

To get you started, an outline implementation is provided in non_blocking_queue.h and non_blocking_queue.c. The header file has the following contents:

You should modify the code in blocking_queue.c as follows:

The key idea is that popping from this queue blocks if no data is available. Blocking makes disposing of such a queue more complicated as we have to clean up potential blocked threads. To do this, terminating the queue makes blocked and subsequent pop calls fail immediately.

You may also need to add other supporting code in these files, such as suitable type definitions or additional functions. You can also add or use functions from the files utilities.h and utilities.c.

The queue should be designed so it is safe to use in multi-threaded code.

You also should write some tests for your code. If you run 

make blocking_queue . tested 

two very simple tests will run, and the second will fail. You should modify the code in blocking_queue.tests.c to contain suitable tests of the correctness of your blocking queue, and remove the two example tests. If you want an example of how to write some more realistic tests, again, looking in list.tests.c may help. Details about assertions can be found in Appendix A.

4.4 Adding threads to the simulator

Now we have some supporting code, we start work on the main body of the simulator. The aim of this part is to create some threads in the simulator, which will simulate the available CPUs.

Add the following features in simulator.c:

You can briefly check your code by recompiling coursework and running it. It should now print out the additional logger messages that you added, and then terminate.

4.5 Managing process ids

As we are simulating an operating system, we will need to manage process identities. A process id should be stored in the ProcessIdT type, which is simply an unsigned int.

Modify simulator.c to efficiently store process ids in such a way that:

You can briefly check your code by recompiling coursework and running it.

You shouldn’t see much change, but the code should still run and complete successfully.

By efficiently, we mean your implementation should have time complexity for issuing and returning process ids which is better than linear in the maximum number of processes.

4.6 Simulating running processes and waiting for them to finish

The aim of this part is to add support in the simulator for creating processes and waiting for them to finish. This is a challenging step, as several changes are needed to achieve the desired functionality.

Modify simulator.c as follows:

4.7 Making the environment create and wait for processes

Now we are able to create and wait for the completion of processes in the simulator, the next step is to extend the environment so that it exercises this functionality.

4.8 Dealing with blocking processes

4.9 Making the environment create and wait for jobs that may block

4.10 Simulating killing processes

This is the final step of the coursework. The aim of this part is to add the ability to kill processes in the simulator. This part may be challenging to implement correctly, depending on your design.

You should modify simulator.c to:

11 Making the environment create and kill long running jobs

As a final check of your coursework you should run:

./ coursework

The program should eventually run to completion after sequentially displaying various log messages. If the program does not eventually halt, or terminates abnormally, then some debugging might be required.

5 Submitting your work

In order to submit your work, complete the following steps:

1. Make a zip file of your latest course code, by typing: 

make coursework . tar.gz

2. Copy the generated coursework.tar.gz file to a fresh directory, and ex tract it again, using the command: 

tar zxvf coursework .tar .gz

3. Use the Moodle submission page for COMP2007 to submit your generated coursework.tar.gz file.

6 Where to find help

If you are having trouble solving the programming tasks, we cannot provide direct help with that as it is part of the assessment. You could consider:

7 Assessment guidelines

8 Academic Misconduct

In particular, instead of doing any of the above:

Appendices

A Background on assertions

The coursework uses a simple feature provided by the C standard library called assertions. As these aren’t covered in first year courses, we will briefly introduce the idea.

Assertions are used to check conditions that you expect to hold in your code, typically in a debug build of your program. The makefile provided with the coursework is already configured to produce debug builds of your code, so you don’t need to worry about how to set this up.

# include < assert .h >

The inclusion #include <assert.h> includes the definitions needed to use as sertions. There are two assertions in the code:

Forcing your code to crash seems odd at first, but it is very useful in practice

int my_function ( void * pointer ) {

assert ( pointer );

// The rest of the code

...

}

makes very clear to callers of my_function that null pointers should not be passed as arguments to this function.

• You can use assertions in unit tests to verify your code is correct. For example, the code:

void test_empty_creation_destruction () {

printf (" Test empty creation / destruction \n");

ListT * list = list_create () ;

assert ( list_empty ( list ));

assert ( list_length ( list ) == 0) ;

list_destroy ( list );

}

checks a linked list implementation to verify that newly created lists are empty, and therefore have zero length. More examples of using assertions in tests can be found in the provided unit test file list.tests.c.

If needed, more background on assertions can be found in any standard source on C programming, such as the Kernighan and Ritchie book.

B Using the evaluator

typedef enum Reason {

reason_terminated ,

reason_timeslice_ended ,

reason_blocked ,

} ReasonT ;

typedef struct EvaluatorResult {

unsigned int PC;

unsigned int cpu_time ;

ReasonT reason ;

} EvaluatorResultT ;

typedef struct EvaluatorCode {

EvaluatorResultT (* implementation )( unsigned int , unsigned int );

unsigned int parameter ;

} EvaluatorCodeT ;

// The evaluator - pretends to run some code on a CPU

EvaluatorResultT evaluator_evaluate ( EvaluatorCodeT const code , unsigned int PC );

You wont need to understand the details of the type EvaluatorCodeT, as they are implementation detail of the evaluator.

The function evaluator_evaluate pretends to run the specified code, with the initial program counter set to PC. The PC should be set to zero on the first run of any code. The return value is a structure containing: