I was wondering if anyone could help me develop a code that could complete these

Question

I was wondering if anyone could help me develop a code that could complete these tasks. I tried using a single linked list but wasn't able to get my code to run correctly. Please if you could help that would help me a lot thank you.

QUESTION:

Linked lists are some of the most useful simple data structures in all of programming. They can be used in databases, text editing, process simulation, and a wide variety of other applications. The queue data structure (first in, first out), implemented using linked lists, is very common – useful, for example, in writing a program to process sales of Super Bowl tickets or, as will be the case here, in an operating system for scheduling different processes to execute on the CPU.

In this lab you will partner with another student in the class and work as a team. You should jointly develop an overall structure for the program, then divide the detailed design and implementation work evenly. Each member of the team must develop a significant portion of the code for the final solution, and each should mark which portions of the code were developed by them (put comments with your name by each function, or segment you wrote). In the comments at the beginning of your code, indicate both you and your partner’s names at the “Programmers”. You and your partner will jointly demonstrate your solution for the TA when finished.

This is a difficult lab. Begin work as soon as you can, developing a high-level outline of the program, the overall control flow, and specifications for various functions you will need. Implement and test those functions separately, then bring them together to create the final program.

Objectives:
1. Become familiar with use of pointers and structures
2. Become familiar with team dynamics in program development
3. Demonstrate good programming style, use of modularity, and command processing on a significant problem
4. Gain experience with devising test data that will execute all the various conditions with which a program must deal

Part 1: Program description and operation

This program will simulate a simple process scheduling Queue (list) such as used in an operating system. The program will add processes to the queue, and can delete processes from the queue. The list will be maintained as a linked list using pointers (read the linked list notes in the text). Each node in the list should be a structure with the following information about the process stored in the node:

PID: integer (Process ID) PIDs can only be positive numbers. Name: Text array of up to 20 characters (no white space in name) Priority: short int (0-15)

You should maintain both front and rear pointers for the list. You may implement the scheduling queue as a singly linked list, as shown below.

Alternatively, you can implement the queue as a doubly linked list. While this requires an extra link your code must manage, it will simplify the Delete command. The doubly linked list implementation might look as shown below:

The structures for each flavor of list should be similar to those shown below:

For singly linked list

For doubly linked list

Note the last flink and last rlink (if you implement a doubly linked list) are NULL.

Your program will read commands from an input text file to “add” a process, “delete” a process, and print out the current state of the queue. Your program should read and process commands until the end of the input file is encountered. The program should handle obvious command errors such as deleting a process that doesn’t exist, invalid command, etc. Command letters may be in upper or lower case.

The commands are: Add: A PID PRI Name Delete: D PID
D -1

Print: P

- add this process to the rear of the queue
- delete the process with this PID
- delete whichever process is at the front of the queue - print out a list of the processes currently in the queue.

When the program runs, it should open a file called “procinp.txt,” which will contain the commands that your program will process. A sample command input file might look like this:

Part 2: Program execution

The final text file prepared by the TA may have many more lines than shown above. There will be invalid commands, legal commands that do invalid things (such as delete a non-existent PID), as well as valid commands.

Some commands that are not necessarily “errors”, but that could occur and to which your program should respond appropriately, include:
Print a queue that is empty (all processes have been deleted)
Priority outside the range of 0-15

The commands will all be properly formatted, ie. no missing arguments Process names will never be more than 19 characters.

Lab steps:
1. Develop an outline for the program and begin implementation before coming to lab. 2. Open Visual Studio and create a new project called Lab9.
3. Create your program. Use “stubs” for unwritten functions initially, then implement the functions one at a time.
4. Debug and test your program.
5. When working properly, demonstrate your program for the TA.
6. Turn in the program listing to the TA.

Part 3: Extra credit

Modify your implementation of the Add function to maintain the process queue in PRI order (lower numbers indicate higher priority, so 1 should be on the list before 2, which will be before 3, etc.). Add a new process to the queue behind any other processes with the same priority, and before any processes with a lower (higher numerically) priority. You must successfully demonstrate your solution to the base lab assignment to the TA before you demonstrate the extra credit version.

Explanation / Answer

Single linked list

#include <sys/types.h>
#include <stdlib.h>
#include <alloca.h>
#include <stdio.h>
#include <unistd.h>

struct pnode {
    int pid;
    struct pnode *next;
};
typedef struct pnode pnode;


int
main(void)
{
    void startKilling(pnode *list);
    void createprocesses(pnode *list, pnode **current, pnode **temp);
    void getnode(pnode **ptr);
   
    pnode *list;
    pnode *current;
    pnode *temp;
   
    pid_t pID;
    pID = 0;
   
    getnode(&list);
    getnode(&current);
    getnode(&temp);

    list = NULL;
    current = NULL;
    temp = NULL;
   
    current = list;
   
    createprocesses(list, &current, &temp);
    printf("PID1: %d ", list->pid);
    list = list->next;
    printf("PID2: %d ", list->pid);

    exit(0);
}

void getnode(pnode **ptr)
{
    *ptr = malloc(sizeof(*ptr));
    printf("Address of ptr: %p ", ptr);
}

void insertnode(pnode **current, int processid)
{
        pnode *temp;
    getnode(&temp);
    (*current)->pid = processid;
    (*current)->next = temp;
    (*current) = temp;
}

void startKilling(pnode *list)
{
    printf("Merrily killing processes.... ");
    printf("Anything after this should not exist. ");
}

void createprocesses(pnode *list, pnode **current, pnode **temp) {
    void insertnode(pnode **current, pnode **temp, int processID);
   
    pid_t pID;

    pID = 0;
   
    while(pID != -1) {
        pID = fork();
        if(pID == 0) {
            pause();
        } else if(pID < 0) {
            printf("Failed to fork... ");
        } else {
            /* Parent Process */
            printf("Process ID: %d ", pID);
           
            insertnode(&(*current), (&(*temp)), pID);
        }
    }
}

Doubly LInked List

#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
        int data;
        struct Node *next;
        struct Node *prev;
}node;
void insert(node *pointer, int data)
{
        /* Iterate through the list till we encounter the last node.*/
        while(pointer->next!=NULL)
        {
                pointer = pointer -> next;
        }
        /* Allocate memory for the new node and put data in it.*/
        pointer->next = (node *)malloc(sizeof(node));
        (pointer->next)->prev = pointer;
        pointer = pointer->next;
        pointer->data = data;
        pointer->next = NULL;
}
int find(node *pointer, int key)
{
        pointer = pointer -> next; //First node is dummy node.
        /* Iterate through the entire linked list and search for the key. */
        while(pointer!=NULL)
        {
                if(pointer->data == key) //key is found.
                {
                        return 1;
                }
                pointer = pointer -> next;//Search in the next node.
        }
        /*Key is not found */
        return 0;
}
void delete(node *pointer, int data)
{
        /* Go to the node for which the node next to it has to be deleted */
        while(pointer->next!=NULL && (pointer->next)->data != data)
        {
                pointer = pointer -> next;
        }
        if(pointer->next==NULL)
        {
                printf("Element %d is not present in the list ",data);
                return;
        }
        /* Now pointer points to a node and the node next to it has to be removed */
        node *temp;
        temp = pointer -> next;
        /*temp points to the node which has to be removed*/
        pointer->next = temp->next;
        temp->prev = pointer;
        /*We removed the node which is next to the pointer (which is also temp) */
        free(temp);
        /* Beacuse we deleted the node, we no longer require the memory used for it .
           free() will deallocate the memory.
         */
        return;
}
void print(node *pointer)
{
        if(pointer==NULL)
        {
                return;
        }
        printf("%d ",pointer->data);
        print(pointer->next);
}
int main()
{
        /* start always points to the first node of the linked list.
           temp is used to point to the last node of the linked list.*/
        node *start,*temp;
        start = (node *)malloc(sizeof(node));
        temp = start;
        temp -> next = NULL;
        temp -> prev = NULL;
        /* Here in this code, we take the first node as a dummy node.
           The first node does not contain data, but it used because to avoid handling special cases
           in insert and delete functions.
         */
        printf("1. Insert ");
        printf("2. Delete ");
        printf("3. Print ");
        printf("4. Find ");
        while(1)
        {
                int query;
                scanf("%d",&query);
                if(query==1)
                {
                        int data;
                        scanf("%d",&data);
                        insert(start,data);
                }
                else if(query==2)
                {
                        int data;
                        scanf("%d",&data);
                        delete(start,data);
                }
                else if(query==3)
                {
                        printf("The list is ");
                        print(start->next);
                        printf(" ");
                }
                else if(query==4)
                {
                        int data;
                        scanf("%d",&data);
                        int status = find(start,data);
                        if(status)
                        {
                                printf("Element Found ");
                        }
                        else
                        {
                                printf("Element Not Found ");

                        }
                }
        }

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.