How to implement a priority-based scheduler

Assignment Help Data Structure & Algorithms
Reference no: EM131306828

1 Overview

In this assignment, you will learn how to implement a priority-based scheduler forxv6. To get started, download a new copy of the xv6 source code fromhere.

Do NOT use the source code of project 1. You'll do two things in this assignment:

- You'll replace xv6's current round-robin scheduler with a priority-based scheduler.
- You'll add a new syscall for a process to set its own priority.
Words of wisdom: first, please start early! Second, please make minimal changes to xv6; you do not want to make it hard for us to grade!

Part 1: Priority-based Scheduler for Xv6

In the first part, you will replace the round-robin scheduler for xv6 with a priority-based scheduler. The valid priority for a process is in the range of 0 to 200, inclusive. The smaller value represents the higher priority. For example, a process with a priority of 0 has the highest priority, while a process with a priority of 200 has the lowest priority. The default priority for a process is 50. A priority-based scheduler always selects the process with the highest priority for execution. If there are multiple processes with the same highest priority, the scheduler uses round-robin to execute them in turn to avoid starvation. For example, if process A, B, C, D, E have the priority of 30, 30, 30, 40, 50, respectively, the scheduler should execute A, B, and C first in a round-robin fashion, then execute D, and execute E at last.

For this part, you will need to modify proc.h and proc.c. The change to proc.h is simple: just add an integer field called priority to struct proc. The changes to proc.c are more complicated. You first need to add a line of code in the allocproc function to set the default priority for a process to 50. Xv6's scheduler is implemented in the scheduler function in proc.c. The scheduler function is called by the mpmain function in main.c as the last step of initialization. This function will never return. It loops forever to schedule the next available process for execution. If you are curious about how it works, read Xv6 book/commentary, Chapter 5. In this part, you need to replace the scheduler function with your implementation of a priority-based scheduler. The major difference between your scheduler and the original one lies in how the next process is selected. Your scheduler loops through all the processes to find a process with the highest priority (instead of locating the next runnable process). If there are multiple processes with the same priority, it schedules them in turn (round-robin). One way to do that is to save the last scheduled process and start from it to loop through all the processes.

A major issue of the priority scheduling is starvation in which a low priority process never gets CPU time due to the existence of runnable higher priority processes. A solution to this problem is called aging. You will also implement aging for your scheduler. Specifically, if the process uses up its CPU time, you are going to decrease its priority by 2 (i.e., add 2 to its priority since lower numbers represent higher priority); if a process is waken up from waiting, increase its priority by 2. Keep in mind that you should always keep the priority in its valid range (0 to 200). In this part, you need to add some code to function wakeup1 in proc.c, and function trap in trap.c.

Part 2: Add a Syscall to Set Priority

The first part adds support of the priority-based scheduling. However, all the processes still have the same priority (50, the default priority). In the second part, you will add a new syscall (setpriority) for the process to change its priority. The syscall changes the current process's priority and returns the old priority. If the new priority is lower than the old priority (i.e., the value of new priority is larger), the syscall will call yield to reschedule.

In this part, you will need to change user.h, usys.S, syscall.h, syscall.c, and sysproc.c. Review project 1 to refresh the steps to add a new syscall. Here is a summery of what to do in each file:

- syscall.h: add a new definition for SYS_setpriority.
- user.h: declare the function for user-space applications to access the syscall by adding:

int setpriority(int);

- usys.S: implement the setpriority function by making a syscall to the kernel.
- syscall.c: add the handler for SYS_setpriority to the syscalls table using this declaration:

extern int sys_setpriority(void);

- sysproc.c: implement the syscall handler sys_setpriority. In this function, you need to check that the new priority is valid (in the range of [0, 200]), update the process's priority. If the new priority is larger than the old priority, call yield to reschedule. You can use the proc pointer to access the process control block of the current process.

Reference no: EM131306828

Questions Cloud

Design a perceptron network to solve this problem : Consider again the four-class decision problem that we introduced in Problem P4.3. Train a perceptron network to solve this problem using the perceptron learning rule.
What are some projects in place that will address problem : What are some projects in place that will address the problem (suggest one if none exist yet)? Why did you choose your topic? How has learning about the topic affected your ideas going into this assignment?
Compute the gross profit margin and operating income margin : On the same spreadsheet, compute the gross profit margin, operating income margin, and net profit margin for 2012, showing the numerator and denominator for all ratios.
Submit your topic of interest and tell how it relate to race : In a Word document, submit your topic of interest, tell how it relates to race and ethnicity or social change, and explain what you hope to learn from this topic. You will also provide a brief summary of the article.
How to implement a priority-based scheduler : COP4610: Introduction to Operating Systems - Project 4: Priority-based Scheduler - you will learn how to implement a priority-based scheduler forxv6. To get started, download a new copy of the xv6 source code fromhere.
How do you think you will feel after the reactions : Is it a formal norm or an informal one? What reactions by others do you expect? If published, might these reactions affect your life chances? How do you think you will feel after the reactions?
What implications does imperfect nature of type of research : What implications does the imperfect nature of this type of research have for social psychological science? How can these two competing views (by the same person) be reconciled?
Determine the fundamental the castle doctrine : Specify the key points involved in the court determining the lawfulness of the use of force. Next, evaluate the level of objectivity inherent in each point that you have specified.Determine the fundamental difference between the castle doctrine an..
Evaluate the main points of the reading in three paragraphs : Summarize, explain, and evaluate the main points of the reading in a minimum of 3 paragraphs. Do not simply cut and paste from the reading, but summarize the main points in your own words.

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Find capacity of a particular airplane type

Consider the entities and their attributes. You should 1st determine what entities want to track. Next determine what attributes are required for each entity, and what relations exist between these entities.

  Describe the requirement for complex data structures

Describe the requirement for complex data structures and how they are utilized. Describe the design and application of arrays and how the array simplifies program development.

  Create a program that should read in character from the file

Your program should read in the characters from the file, but ignore all characters except for the following: { } ( ) [ ]. The general algorithm is to use a stack to store the opening unmatched brackets.

  Searching of an item in a list of n numbers using linear

Ques:-Write a program in java for searching of an item in a list of n numbers using linear search.

  Nbspa stack evaluating the postfix expression lrm using

nbspa stack evaluating the postfix expression lrm using linked list implementationthis step will use the queue

  Arraysq1-write a program to find average marks obtained by

arraysq1-write a program to find average marks obtained by 10 students in a test along with algorithm?q2 -write a menu

  Create the pseudocode for a game application

Create the pseudocode for a game application that contains an array of five (5) multiple-choice questions related to your favorite hobby.

  Show the final shortest-path tree

draw a table showing the intermediate distance values of all vertices at each iteration of the algorithm; (ii) show the final shortest-path tree.

  Design and write the client and server programs

Each client requests multiple CPU and I/O bursts from the keyboard. This information and the private FIFO are sent to the server through a common FIFO. The server responds to each client using private FIFOs.

  The ace is played when both the king

The Ace is played when both the King and Queen are showing on the table, or when neither the King and Queen are showing on the table.

  Creating database for a human resources group

Construct a database for a human resources group. List a few different tables and columns to store the HR information.

  A program that performs depth first search in a graph

a program that performs Depth First Search in a graph

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd