1
Final Project (20 points)
Dr. Ahmed E. Khaled
Computer Science Department
Northeastern Illinois University (NEIU)
CS308 – Operating Systems
For the final project, you should select only one of the following options detailed below:
§ Option 1 is a group project (up to 2 members), but you can choose to work on this project by yourself as
individual project.
§ Option 2 is a group project (up to 2 members), but you can choose to work on this project by yourself as
individual project.
§ Option 3 is an individual project.
§ Option 4 is an individual project.
Attached with this document, 3 test cases files to be used with option1 and option2.
2
Option 1 (20 + 2 bonus points)
You (and your team if you decide to work in a team) should use the Java IDE you find appropriate (e.g.,
NetBeans, Eclipse) to solve this project. You are building a round-robin preemptive scheduler to organize
the work of processes in a computing system. Any process can be either newly created, ready to be selected
by the scheduler, running for a certain amount of time (a.k.a. Quantum), or terminated when done. You
may assume that a process will not be waiting/blocked while being in the running state. Your scheduler is
composed of the following components:
Process (Component 1): Create a class that represents a process in a computing system. Any process to
work within your scheduler needs to be described in terms of: 1) Unique identifier(integer value); 2) Arrival
time (integer value represents when the process became available in the system); 3) Execution time (integer
value represents how long the process should run to finish the task); and 4) Priority (integer value represents
the priority of the process with 1 represents the highest priority). The class must have the following
mandatory functions:
1- Default constructor: provides a unique ID and initializes the rest of the variables by zeros.
2- Full constructor: initializes the four variables by the constructor’s data.
3- Get/Set for each variable.
4- toString: return a string with the current values of the process’ variables.
You can add more functions if required.
Scheduler (Component 2): Function that accepts an array of processes and quantum (integer value
represents the maximum time window for how long each process should run). The scheduler schedules the
input processes with respect to their arrival time and considers their unique identifiers whenever they have
same arrival time (two processes with same arrival time, then consider the one with smaller id as first
choice). The scheduler finally prints the selected processes for running by calling the toString function.
Initializer (Component 3): As mentioned in the previous component, the scheduler accepts an array of
processes as input. Initializer, function, creates such an array of processes dynamically. The initializer reads
an input text file that resides on your computer and holds information about the processes you need to create
for your system. The file is structured as follows:
The first line of the file shows the number of processes you have in the file and the quantum time (the input
to the scheduler). The next lines represent information about the different processes. Take the following as
an example for such file – here we have 3 processes and quantum to be 5. Each process (takes a separate
line) is represented as id, arrival time, and executing time. For example: first process has id of 1, arrival
time of 5, execution time of 8, and priority of 1 (highest priority).
3, 5
1, 5, 8, 1
2, 0, 10, 2
3, 10, 7, 3
Number of processes, quantum time
id, arrival time, executing time, priority
id, arrival time, executing time, priority
…..
id, arrival time, executing time, priority
3
Main Engine (Component 4): The engine is the module that runs the different components you
developed sequentially. As your scheduler is just one module of the OS, it should run in parallel with
other modules of the OS. The engine works on two threads, thread 1 and thread 2, that run sequentially.
Thread 1 runs the initializer, and Thread 2 waits until thread 1 is done then runs the scheduler directly
after.
public class MainEngine {
//array of processes, initially empty
//quantum value, initially zero
public static void Initializer (…) {
}
public static void Scheduler (…) {
}
public static void main (String[] args) {
Thread 1: run the Initializer
Thread 2: run the scheduler
}
}
Project submission Guidelines:
1. Submit only ONE ZIP to the folder titled FinalProject under the D2L Assignments tab (other formats
will not be accepted). Only one of the team members should submit the developed team project.
2. The .ZIP file contains:
• The java files you developed on.
• PDF file constructed as follows:
• Page1: your name and the name of your teammate.
• Page2: the output (screenshots) of running your scheduler using the shared testcases (0,1, and 2)
• Page3: the two (at least) test cases you developed to test the correctness of your scheduler
• Page4: the output (screenshots) of running your scheduler using your testcases.
3. The submission is due 11:59 pm – December 5th. You can submit any updates to your submission within 24 hours
after this due date will be graded out of 75% of the final project’s grade (for the whole team). After this grace
period your late submission will not be accepted.
4
Option 2 (20 + 2 bonus points)
You (and your team if you decided to work in a team) should use the Java IDE you find appropriate (e.g.,
NetBeans, Eclipse) to solve this project. You implement and compare the different non-preemptive
schedulers (SFJ: Shortest Job First, FCFS: First Come First Serve, PF: Priority First) that organize the work
of processes in a computing system. Any process can be either newly created, ready to be selected by the
scheduler, running until the process is done, or terminated when done. You may assume that a process will
not be waiting/blocked while being in the running state. Your scheduler is composed of the following
components:
Process (Component 1): Create a class that represents a process in a computing system. Any process, in
order to work within your scheduler, needs to be described in terms of: 1) Unique identifier (integer value);
2) Arrival time (integer value represents when the process became available in the system); 3) Execution
time (integer value represents how long the process should run to finish the task); and 4) Priority (integer
value represents the priority of the process with 1 represents the highest priority). The class must have the
following mandatory functions:
1- Default constructor: provides a unique ID and initializes the rest of variable by zeros.
2- Full constructor: initializes the four variables by the constructor’s data.
3- Get/Set for each variable.
4- toString: return a string with the current values of the process’ variables.
You can add more functions if required.
SJF Scheduler (Component 2): Function that accepts an array of processes and schedules them with
respect to their arrival time and considers their execution times whenever they have same arrival time (two
processes with same arrival time, then consider the one with smaller execution time as first choice). The
scheduler finally prints the selected processes for running by calling the toString function, then calculates
and prints the average waiting time of the processes.
PF Scheduler (Component 3): Function that accepts an array of processes and schedules them with respect
to their arrival time and considers their priority whenever they have same arrival time (two processes with
same arrival time, then consider the one with highest priority as first choice). The scheduler finally prints
the selected processes for running by calling the toString function, then calculates and prints the average
waiting time of the processes.
FCFS Scheduler (Component 4): Function that accepts an array of processes and schedules them with
respect to their arrival time and considers their identifiers whenever they have same arrival time (two
processes with same arrival time, then consider the one with smaller ID as first choice). The scheduler
finally prints the selected processes for running by calling the toString function, then calculates and prints
the average waiting time of the processes.
Initializer (Component 5): As mentioned in the previous component, the scheduler accepts an array of
processes as input. Initializer, function, creates such an array of processes dynamically. The initializer reads
an input text file that resides on your computer and holds information about the processes you need to create
for your system. The file is structured as follows:
Number of processes, quantum time
id, arrival time, executing time, priority
id, arrival time, executing time, priority
…..
id, arrival time, executing time, priority
5
The first line of the file shows the number of processes you have in the file and the quantum time (the input
to the scheduler). The next lines represent information about the different processes. Take the following as
an example for such file – here we have 3 processes and quantum to be 5. Each process (takes a separate
line) is represented as id, arrival time, and executing time. For example: first process has id of 1, arrival
time of 5, execution time of 8, and priority of 1 (highest priority). As you are working with non-preemptive
schedulers, so you can ignore the quantum time.
3, 5
1, 5, 8, 1
2, 0, 10, 2
3, 10, 7, 3
Main Engine (Component 6): The engine is the module that runs the different components you developed.
After the initializer adds the required info in the array of processes, the different scheduler should work in
parallel using 3 threads over such shared array. You may utilize either Mutex locks or semaphores to
enable mutual access to the shared resource (the array of processes) that is shared between the three
threads (don’t create three separate arrays).
public class MainEngine {
//array of processes, initially empty
public static void Initializer (…) {
}
public static void SFJ_Scheduler (…) {
}
public static void PF_Scheduler (…) {
}
public static void FCFS_Scheduler (…) {
}
public static void main (String[] args) {
Run the Initializer
Thread 1: run the SJF scheduler
Thread 2: run the PF scheduler
Thread 3: run the FCFS scheduler
}
}
Project submission Guidelines:
1. Submit only ONE ZIP to the folder titled FinalProject under the D2L Assignments tab (other formats
will not be accepted). Only one of the team members should submit the developed team project.
2. The .ZIP file contains:
• The java files you developed on.
• PDF file constructed as follows:
• Page1: your name and the name of your teammate.
• Page2: the output (screenshots) of running your schedulers using the shared testcases (0,1, and 2)
• Page3: the two (at least) test cases you developed to test the correctness of your schedulers.
• Page4: the output (screenshots) of running your schedulers using your testcases.
6
3. The submission is due 11:59 pm – December 5th. You can submit any updates to your submission within 24 hours
after this due date will be graded out of 75% of the final project’s grade (for the whole team). After this grace
period your late submission will not be accepted.
7
Option 3 (20 points)
The course, so far, introduced fundamental concepts and topics associated with Operating Systems.
However, the domain covers a broader range of topics and the goal of the final project is to study topics
that expand the covered content in this course. In this option, you will select only one of the following
topics, do enough readings on the selected topic from important research resources, and finally develop a
4-page research document summarizing your findings and answering the questions listed under the
selected topic in enough details.
Topic Description
1 While using paging for memory management, we need a page replacement algorithm to select a page to be replaced
when a new page is required. First In First Out (FIFO), Least Recent Used (LRU), and Least Frequent Used (LFU)
are three methods for the page replacement.
What is page replacement? and how does each of these methods work? – Describe the steps and provide example(s).
2 Demand paging in a memory management system requires a frame allocation algorithm. When there are multiple
processes, this algorithm is used to decide how many frames to allocate to each process.
What is frame allocation? what is the difference between equal allocation and proportional allocation? and what is
the difference between global and local allocation?
3 The banker’s algorithm is a resource allocation and deadlock avoidance algorithm. The algorithm is used to check
the safety of the system before deciding whether allocation of a resource should be allowed or not.
What is this technique? and how does it work? – Describe the steps and provide example(s).
4 I am interested in another operating-systems related topic (e.g., Multi-processor scheduling and load balancing) and
I would like to do a research on such topic instead.
In this case, you need to discuss the topic with me first and get my confirmation before you can start
working on it.
Step1: Select one topic from those listed in the table above, the best way to do this step is to do a quick
read on each of these topics and accordingly select a topic of your interest.
Step2: Use the Internet to prepare at least two references (research papers, chapters from textbooks) that
will assist you developing the required research. Don’t consider a blog or a Wikipedia page or a
YouTube video to be a reference – these can be side resources not references.
Step3: You will develop a minimum of 4-pages research document (Use Times New Roman, font size 12,
Single Spaced) summarizing your findings and answering the questions listed under the selected topic in
enough details, as follows:
§ Use your own words to describe the topic in an appropriate way, make your target readers to be
with no pre-knowledge of your topic, so don’t use abbreviations or keywords without explaining
them.
§ Develop appropriate figures/charts/pseudo-codes that help you describe your topic in a smooth
way. For example, if your topic is about an algorithm to avoid deadlock, develop
figure/figures/pseudo-codes showing such the steps and include the essential information on the
figures/charts/pseudo-codes. If your topic presents certain architecture, develop
figures/charts/pseudo-codes showing such architecture along with the main components and the
functions per component.
8
§ Use the tool you find appropriate to develop figures/charts/pseudo-codes. (you are not allowed
to copy figures from online/offline resources – develop your material, plagiarism will be
checked and will receive zero).
Project submission:
1. Submit only ONE PDF, to the folder titled FinalProject under the D2L Assignments tab (other formats
will not be accepted).
§ In the top part of the first page, place your topic and your name (first and last name) – just as a header
and sub-header respectively, not the full page.
§ In the lower part of the last page, place the resources (references) you used to prepare your topic –
just the lower part, not the full page.
§ The grading criteria will be as follows:
1. The technical content (6 points)
2. The quality of the research document (6 points)
3. The development of figures (6 points)
4. The structure of the document (2 points)
2. The submission is due 11:59 pm – December 5th. You can submit any updates to your submission within 24 hours
after this due date will be graded out of 75% of the final project’s grade (for the whole team). After this grace
period your late submission will not be accepted.
Option 4 (20 points)
You have an idea for a module that offers certain function for an operating system you would like to implement. In
this case, you need to define the structure and the goals of your system and then discuss the topic with me first, and
get my confirmation before you can start working on it.
Project submission:
1. Submit only ONE ZIP, to the folder titled FinalProject under the D2L Assignments tab (other formats will not be
accepted). Only one member should submit the project.
2. The .ZIP file contains: 1) PDF with clear screenshots for the different testcases you developed to test the correctness
of your implementation; and 2) The java files you developed.
3. The submission is due 11:59 pm – December 5th. You can submit any updates to your submission within 24 hours
after this due date will be graded out of 75% of the final project’s grade (for the whole team). After this grace
period your late submission will not be accepted.
