CMIS 412

Homework 4 – Banker’s algorithm

Implement the Banker's algorithm for deadlock avoidance, with a given set of N processes

(N<10, processes are P1, P2, …, PN) and M resource types (M<10, resources are R1, R2, …, RM). Use Java or

C/C++ for the implementation, with a simple interface, where the user only supplies the name of the

input file (text file, say “input.txt”). The program reads all the necessary input data from that file. You

are free to choose the format of the input file, just make sure it contains all the necessary data. The

input data and the result of the algorithm must be displayed on the screen.

The pseudo code for the Greedy version for the Banker’s algorithm can be found in this module’s

Commentary. We know that this algorithm only finds ONE solution (safe sequence of processes)

assuming there is one; otherwise reports there is no solution.

You must adjust this algorithm to find exactly TWO solutions instead of just one (assuming of course

there are at least two solutions). If the algorithm only has one solution this must be reported as such

and the single solution must be displayed.

To resume, there are only three possible scenarios, for a correct input file:

1. There is no solution (no safe sequence). The program must report there is no solution.

2. There is EXACTLY ONE solution (safe sequence). The program must report there is exactly one

solution. The solution must be displayed on screen.

3. There are TWO OR MORE solutions (safe sequences). The program must find EXACTLY TWO

solutions. The solutions must be displayed on screen. If there are more than two solutions, it

doesn’t matter which ones are found, as long as they are exactly two.

Note 1: the solution must be based on the Greedy version for the Banker’s algorithm; in particular, using

an approach for finding ALL solutions and then keeping and reporting just two of them is NOT allowed.

Note 2: The input file may be incorrect, for various reasons. This must be checked and reported by your

program before any attempt of finding a solution.

HINTS:

– The input files should start with N and M, then the necessary matrices

– Work on your own computer or online using https://replit.com

DELIVERABLES:

1. The source code for your program, stored in a text file

2. One incorrect input file, “input0.txt” and one or more screenshots showing the results of your

program for this incorrect input.

3. Three input files, “input1.txt” (N=4, M=3), “input2.txt” (N=4, M=3), “input3.txt” (N=4, M=3). Please

choose the input data in such a way that the first input has no solution, the second input has exactly

one solution and the third input has at least two solutions.

4. Three screenshots showing the final results of your program’s execution for these three input files.

5. Store the screenshots in graphic files of your preferred format(“.png” or ”.gif” or “.pdf”, etc.).

Homework 6

Write a Java or C/C++ (the choice is yours) program for file/directory processing according to the following rules. The program requested for this homework must have a text menu like this: 0 – Exit

1 – Select directory

2 – List directory content

3 – Display file (hexadecimal view)

4 – Delete file

5 – Mirror reflect file (byte level)

Select option:

The menu is displayed and the user must select an option (a number between 0 and 5). The action corresponding to the selection is performed, then the menu is displayed again and the user can choose another option. This cycle is repeated until the user selects 0, which exits the loop and ends the program execution. The options are: 0 – Exit This options ends the program execution. This option should always work. 1 – Select directory The user is prompted for an [absolute] directory name (path). This is the first options that must be selected by the user. All the options below are working on the directory selected here. The directory name (path) must be correctly formatted and the directory must exist (the program must check for this and issue error messages if necessary). After performing several operations on the selected directory, the user can select another directory and work with it. If a user (by mistake or otherwise) selects any other option from the menu before selecting this one, an error message must be displayed instructing the user to select a directory first. 2 – List directory content This option displays the content of the directory (previously selected by option 1) on the screen. All the files and sub-directories from the first level ONLY must be displayed (files and directories should be listed separately one item per line, directories first). For each file, its size must also be displayed, in bytes. If no directory was selected an error message must be displayed. 3 – Display file (hexadecimal view) This option prompts the user for a filename (from the directory selected by option 1) and displays the content of that file on the screen, in hexadecimal view. If no directory was selected an error message must be displayed. If the directory does not contain the file specified by the user, another error message must be displayed. The filename does not include any path, it’s just the name of the file. Note: The hexadecimal view displays each byte of the file in hexadecimal, 16 bytes per line, separated by one white space; each byte must occupy two characters on the screen. It should look something like this (please note that the letters A to F must be in upper case !!!): 52 61 72 21 1A 07 01 00 96 45 15 22 0C 01 05 08

00 07 01 01 D3 94 89 80 00 CA 47 9D 13 4A 02 03

0B F3 93 09 04 95 A1 09 20 F7 2B 31 75 80 0B 00

2C 57 68 61 74 73 41 70 70 20 49 6D 61 67 65 20

32 30 32 32 2D 30 35 2D 31 31 20 61 74 20 37 2E

33 34 2E 31 34 20 50 4D 2E 6A 70 65 67 0A 03 02

F4 FF 17 13 CB 65 D8 01 8E 87 16 45 67 06 55 53

22 65 66 70 37 76 D4 D1 22 42 00 90 8C 20 D0 51

01 22 C0 EA 28 D0 34 02 03 01 04 08 28 49 10 58

29 4A 28 8D 02 88 88 95 AC 04 12 95 29 60 0A 55

01 12 85 7A 08 0D 42 89 4A 28 A5 30 10 51 51 51

51 29 45 45 20 22 08 BD 71 BD F5 BF 31 1D F7 DF

9C 79 DE FB E3 EF F5 F7 D1 B2 13 53 3A CD 5C F3

AC E7 38 CE 28 87 A6 71 F8 27 CC 63 39 E3 34 73

8F 4A FF 5E 6F EB D8 21 13 5B 16 CD 88 83 06 08

20 7F 25 E9 FD 5E 09 12 26 69 2F A4 D0 F6 3C 7A

69 04 FF F3 4A 59 B5 05 0C DA 91 42 2A 7F E0 A2

DA A6 79 53 FF 94 B6 B0 B8 B0 AC 97

4 – Delete file This option prompts the user for a filename and deletes that file from the selected directory. If no directory was selected an error message must be displayed. If the directory does not contain the file specified by the user, another error message must be displayed. The filename does not include any path, it’s just the name of the file. 5 – Mirror reflect file (byte level) This option prompts the user for a filename (from the selected directory) and performs an operation we will call ”mirror reflection” for every byte of that file. If no directory was selected an error message must be displayed. If the directory does not contain the file specified by the user, another error message must be displayed. The filename does not include any path, it’s just the name of the file. Note: Mirror reflection for a certain byte (which, as we know, is a string of 8 bits) changes the order of its bits just like a real world mirror does for any image: what was on the left side will appear on the right side and vice versa. More concretely, let’s denote the bits of a byte as b1b2b3b4b5b6b7b8. After the mirror reflection operation, they will be rearranged as b8b7b6b5b4b3b2b1. Hints: The required actions are: read the whole file into a memory buffer (we assume the file is small enough), then perform the mirror reflection for every byte of the memory buffer, then we write back the buffer into the file (we overwrite the file) resulting a file with the same size in bytes. No additional file must or should be used, as the initial file must be overwritten. Clearly if we apply this operation twice, we must obtain again the initial file content. Testing procedure: 0. Option 0 requires just one screenshot, for successful exit.

1. Option 1 requires one screenshot for a correct directory name (path) and one screenshot for an incorrect directory name (path).

2. Option 2 requires one screenshot showing the error (no directory was selected yet) and another one showing the content of the selected directory; make sure the directory you use contains at least three files and three subdirectories.

3. Option 3 requires screenshots showing the errors (no directory was selected yet, file does not exist) and another one showing the content of the selected file; make sure the display follows the required formatting.

4. Option 4 requires screenshots showing the errors (no directory was selected yet, file does not exist) and another one/two showing the content of the selected directory before and after deleting the file.

5. Option 5 requires screenshots showing the errors (no directory was selected yet, file does not exist) and others showing the hex view of the file before and after mirroring (also, make sure the file size remains the same). Deliverables: 1. Source code (zipped)

2. A Test Report showing the program performing each of the menu actions correctly (use the testing procedure described above, include all the required screenshots). Use this file (Homework 6.pdf) as the input file for options 3 and 5.

Homework 3 – Threads in Java

Write a Java program that creates several threads, according to the following scenario:

 The initial thread will be called the main thread (M)

 The main thread (M) creates and starts two worker threads; each worker thread will work on its task

 The main thread (M) joins the two worker threads in the end and computes the final result

The goal of this program is to find all the Vampire numbers in the interval [100000, 999999]. To achieve this

goal we will scan all the integer numbers from 100000 to 999999 and for each of these numbers we must

perform a test to verify if that number is a Vampire number or not. In order to solve this problem faster,

(assuming we have at least two processors on our system) we will divide the work between the two worker

threads: on worker will scan and verify all the even numbers and the other worker will scan and verify all the

odd numbers in the interval.

More precisely, the following list describes the behavior of each thread:

1. The main thread (M) creates the two worker threads, starts them and joins them in the end. After that,

the main thread will compute and display the TOTAL number of Vampire numbers found in the interval

[100000, 999999] as “The TOTAL number of Vampire numbers found is: …” (the ellipsis stand for the

actual number)

2. The first worker will scan and verify all the even numbers in the interval [100000, 999999]; whenever a

new Vampire number is found, it will be displayed like this: “First worker found: …” (the ellipsis stand

for the actual number); a counter will be incremented every time a new Vampire number was found,

and in the end the total number of Vampire numbers found will be displayed: “First worker found …

Vampire numbers” (the ellipsis stand for the actual number)

3. The second worker will scan and verify all the odd numbers in the interval [100000, 999999]; whenever

a new Vampire number is found, it will be displayed like this: “Second worker found: …” (the ellipsis

stand for the actual number); a counter will be incremented every time a new Vampire number was

found, and in the end the total number of Vampire numbers found will be displayed: “Second worker

found … Vampire numbers” (the ellipsis stand for the actual number)

HINTS:

– The Vampire numbers are described in detail here: https://en.wikipedia.org/wiki/Vampire_number

– In the end, the worker threads must communicate their counters to the main thread, in order to

compute and display the TOTAL number of Vampire numbers in the interval

– Work on your computer or online using https://replit.com

DELIVERABLES:

– The source code for the Java program, stored in the text file “hw3.java”

– A screenshot showing the final results of your program’s execution, stored in a graphic file like

“hw3.png” or ”hw3.gif” or “hw3.pdf”, etc.

Homework 1 – Writing a simple C program

The purpose of this assignment is to familiarize yourself with writing simple C programs.

For this assignment we will be using a free web-based IDE for C. You can find it at https://replit.com/

Follow these steps:

Follow the link, https://replit.com/, click the “Start Coding” button and login (you have several options).

When prompted for the programming language, pick C.

Click “Create Repl” button.

You will be shown the following C code by default:

You should use the editor to modify it by including your name in the displayed message (see the

screenshot below):

printf("Hello World! My name is _place_your_name_here_.n");

Then you should compile and run this code with the “Run” button. Notice a nice greetings message with

your name included in it in the Console frame.

Finally, you should capture a screenshot from Replit.com with your program’s execution (just like the

above screenshot) and save it on your computer in a graphics file like “hw1.png” or ”hw1.gif” or

“hw1.pdf”, etc.

Please submit this file under the Homework 1 assignment.

Final Project

Write a Java or C/C++ (the choice is yours) program for a Demand Paging Simulator according to the following rules. The program will implement two Demand Paging algorithms: the classical OPT algorithm (described in the module 5 readings) and a NEW algorithm, described below. The application must simulate the execution the OPT and NEW algorithms on a hypothetical computer having only N physical frames (numbered from 0 to N-1; the maximum value for the parameter N is 8), assuming that the single process that is running has a virtual memory of ten pages (numbered from 0 to 9). The number N should be a number provided as an input for the algorithms, using the program menu. To clarify, the user should be able to run the OPT algorithm (for example) using the same reference string for a scenario where N is 4, then change N to 5 and run again, then change N to 6 and run again and in the end compare the results for each scenario. In other words, the number of physical frames should not be fixed (hardcoded) in the program, but rather considered as an input variable (parameter) for the implemented algorithms. The program requested for this project must have a text menu like this: 0 – Exit

1 – Input N

2 – Input the reference string

3 – Simulate the OPT algorithm

4 – Simulate the NEW algorithm

Select option:

The menu is displayed and the user must select an option (a number between 0 and 4). The action corresponding to the selection is performed, then the menu is displayed again and the user can choose another option. This cycle is repeated until the user selects 0, which exits the loop and ends the program execution. The options are: 0 – Exit This options ends the program execution. This option should always work. 1 – Input N The user is prompted for a [positive integer] number N. This is normally one of the first options that must be selected by the user. The number N must be at least 2 (otherwise the algorithms don’t make any sense) but should not be larger than 8; the program must verify these constraints and issue an error message whenever necessary. After performing several operations from the menu, the user should be able to select another N and work with the new N just as easily as before. 2 – Input the reference string The user is prompted for a series of [positive integer] numbers that will constitute the reference string. The maximum length of the reference string should be 20. This is normally one of the first options that must be selected by the user. The number of elements in the reference string must be at least N

(otherwise the algorithms don’t make any sense) but should not be larger than 20; each element of the reference string must be an integer number between 0 and 9 (there are 10 virtual pages). The program must verify these constraints and issue an error message whenever necessary. After performing several operations from the menu, the user should be able to select another reference string and work with the new reference string just as easily as before. 3 – Simulate the OPT algorithm This option must first verify that a correct N and a correct reference string were already provided by the user; otherwise an error message should be issued and the program returns to the menu. If all the input data (N and the reference string) is available and correct, the simulation begins by printing the initial (empty) simulation table, for example:

Reference String 3 1 6 2 1 3 7 3 2 1 5 4 2 3 7 2 1 Physical frame 0

Physical frame 1 Physical frame 2

Physical frame 3

Page Faults Victim pages

Hint 1: Instead of the above reference string, the table will contain the ACTUAL reference string that was entered by the user; of course, everyone can use their reference strings for testing the correctness of the implementation. Using the reference strings from the readings to test your code is a great idea. Hint 2: Instead of having 4 physical frames in the simulation table, we must actually have N physical frames. So if the user has entered the value 6 for N using option 1 of the menu, then the simulation table should look like this:

Reference String 3 1 6 2 1 3 7 3 2 1 5 4 2 3 7 2 1

Physical frame 0 Physical frame 1

Physical frame 2 Physical frame 3

Physical frame 4

Physical frame 5 Page Faults

Victim pages

Hint 3: Being a text only interface, clearly we cannot display such a nice table, but rather an approximation of it; the table could instead look like this or similar:

The user must proceed with the STEP by STEP simulation of the OPT algorithm by pressing a key after each step of the algorithm; just as in the examples from the module 5 readings, each step of the simulation will fill a new column of the simulation table (previous steps must also be visible) and the table is re-printed on the screen after each step. This way, the user has an overview of all the previous steps and also of the current step. In the end, the table will be completely filled with information, and the user will have the complete view of the simulation. The total number of faults must also be displayed. In other words, the simulation must follow very closely the examples of Demand Paging algorithms from Module 5 of this course. Printing the explanations is optional. 4 – Simulate the NEW algorithm The simulation proceeds just like it did in option 4, but this time the algorithm is no longer the well known OPT algorithm, but a NEW algorithm. This NEW algorithm is a modified version of the LRU algorithm (LRU algorithm was discussed in Module 5 of this course). So how exactly does the NEW algorithm work? The NEW algorithm works just like the LRU algorithm with just one small change, regarding the policy for page replacement, when such an event occurs, and a page must be evicted and replaced with another page. In case of the LRU algorithm, the victim page is the one that has not been accessed, or used, for the longest period of time. Instead, in the NEW algorithm, the victim page is going to be the one that has not been accessed, or used, for the SECOND longest period of time. Consider the following example from the Module 5 LRU example, step 17: – Page 4: was referenced 5 steps ago – Page 3: was referenced 3 steps ago – Page 7: was referenced 2 steps ago – Page 2: was referenced 1 step ago The victim page for LRU is therefore page 4, because it was not accessed for the longest time. However, the victim page for NEW is page 3, because it was not accessed for the SECOND longest time.

Testing procedure for one set of input parameters (N, reference string): 0. Option 0 requires just one screenshot, for successful exit.

1. Option 1 requires one screenshot for a correct input of N and one screenshot for an incorrect N.

2. Option 2 requires one screenshot for a correct input of a reference string and several screenshots for an incorrect reference string, as several errors are possible (incorrect element smaller than 0, incorrect element greater than 9, incorrect sequence length).

3. Option 3 requires screenshots showing the simulation of the OPT algorithm. Two screenshots will suffice: one showing the “middle” of the simulation (approximately) and another showing the end of the simulation (simulation table must be full with information).

4. Option 4 requires screenshots showing the simulation of the NEW algorithm. Two screenshots will suffice: one showing the “middle” of the simulation (approximately) and another showing the end of the simulation (simulation table must be full with information).

Deliverables: 1. Source code (zipped)

2. A Test Report (called Test1.docx/Test1.pdf) showing the program performing each of the menu actions correctly (use the testing procedure described above, include all the required screenshots) for N=4 and the reference string from Homework 5. 3. A Test Report (called Test2.docx/Test2.pdf) showing the program performing each of the menu actions correctly (use the testing procedure described above, include all the required screenshots) for N=5 and the reference string from Homework 5. 2. A Test Report (called Test3.docx/Test3.pdf) showing the program performing each of the menu actions correctly (use the testing procedure described above, include all the required screenshots) for N=6 and the reference string from Homework 5.