This assignment is to simulate the disk I/O handling in system programming by a linked list. A particular Unix kernel operation handles disk I/O by allowing independent user processes to place I/O request blocks (IORB) in a linked list. The order in which these requests are serviced depends on their scheduling priority. The scheduling strategy is adaptive, which simply means that the kernel may carry out different computations at different times in order to calculate the priority value for each element of the list. You are required to write a C program on Linux which designs, implements and tests a sorting function: sortList().
The first argument of the function is a pointer to the head of the list. The second argument is a priority computing function which computes and returns the scheduling priority. The sorting function will sort such a list according to the scheduling priority of each element. Since the OS will have other structures with pointers to IORB blocks, the list must be sorted in place.
Requirement:
1. IORB structure: Its data type is defined as: typedef struct iorb int base_pri; struct iorb *link; char filler[100]; IORB; where base pri is an integer representing the block’s base priority; link is a pointer to next block; f iller is a description about the block which is opaque to the sorting routine.
2. Separate source file for the priority computing function: void sortList(IORB * head, int(*prio)(int)); where head is a pointer to the linked list, and prio is a priority computing function. The sortList() implementation is to be in a separate source file from any driver code. You may however include other functions you’ll need for testing, such as those to build and display the list, in the same source file of the driver code.
3. Priority computing function: For this assignment, to keep things simple, scheduling priorities will be computed from a single integer field (named base pri) in each IORB. You may design any computing method. The function is to return an integer representing the scheduling priority.
4. Sorting algorithm: You are required to use the Selection Sort algorithm to sort the list in an ascending order. This algorithm finds the minimum value, swaps it with the value in the first position, and repeats these steps for the remainder of the list. In practice a more complex linking structure, permitting more efficient sorting, would be used, but this is beyond the scope of this assignment.
5. Sorting in place: The list must be sorted in place. This means that ONLY the links within the list may be altered, no IORB block may be copied to somewhere else in memory. 6. Building and display the list: The list is initially built by a function buildList(). For each IORB in the list, its base scheduling priority base pri is calculated by a random number generator. You may assign any string to f iller. The list is displayed by a function displayList(), which shows the description, the base priority and priority of each element.
A simple description of your solution logic or pseudo code
Sample output
Please enter your choice: 0) Exit 1) Build List 2) Sort List (ascending) 3) Display List Your choice: 1
Please enter your choice: 0) Exit 1) Build List 2) Sort List (ascending) 3) Display List Your choice: 3 Description: this is i/o request 0, Base Priority: 11 Priority: 89 Description: this is i/o request 1, Base Priority: 49 Priority: 51 Description: this is i/o request 2, Base Priority: 27 Priority: 73 Description: this is i/o request 3, Base Priority: 48 Priority: 52 Description: this is i/o request 4, Base Priority: 19 Priority: 81 Description: this is i/o request 5, Base Priority: 16 Priority: 84 Description: this is i/o request 6, Base Priority: 97 Priority: 3 Description: this is i/o request 7, Base Priority: 70 Priority: 30 Description: this is i/o request 8, Base Priority: 83 Priority: 17 Description: this is i/o request 9, Base Priority: 22 Priority: 78 Please enter your choice: 0) Exit 1) Build List 2) Sort List (ascending) 3) Display List Your choice: 2 Please enter your choice: 0) Exit 1) Build List 2) Sort List (ascending) 3) Display List Your choice: 3 Description: this is i/o request 6, Base Priority: 97 Priority: 3 Description: this is i/o request 8, Base Priority: 83 Priority: 17 Description: this is i/o request 7, Base Priority: 70 Priority: 30 Description: this is i/o request 1, Base Priority: 49 Priority: 51 Description: this is i/o request 3, Base Priority: 48 Priority: 52 Description: this is i/o request 2, Base Priority: 27 Priority: 73 Description: this is i/o request 9, Base Priority: 22 Priority: 78 Description: this is i/o request 4, Base Priority: 19 Priority: 81 Description: this is i/o request 5, Base Priority: 16 Priority: 84 Description: this is i/o request 0, Base Priority: 11 Priority: 89 Please enter your choice: 0) Exit 1) Build List 2) Sort List (ascending) 3) Display List Your choice: 0 Terminating… c language
The post This assignment is to simulate the disk I/O handling appeared first on My Assignment Online.
