FIT2100 Operating Systems Assignment #2 Process scheduling simulator Daniel Kos Lecturer, Faculty of IT. Email: [email protected] c© 2010-2019, Monash University September 19, 2019 c© 2019, Faculty of IT, Monash University 1 Introduction 2 1 Introduction Aim In this assignment, you will create programs to simulate two different scheduling algorithms. You will not be doing scheduling of real processes, however your program will determine the sequence in which a certain number of ‘imaginary’ processes are to be executed. This document constitutes the requirement specification for this assignment. You will be assessed on your ability to both comprehend and comply with the requirements as specified herein. Due: 14th October 2019 (Monday) 11am. Late submissions: A late submission penalty of 5% of assignment total per day will apply. No submissions will be accepted after 25th October 2019 (end of semester 2) except in exceptional circumstances. This assignment is worth 15% of the total marks for this unit. 2 About the ‘processes’ We will use a simplified model of a process. Each process has a pre-defined total service time. Our processes do not use I/O and can never be in a blocked state. Each process should be represented within your program as a process control block instance defined as follows: /∗ S p e c i a l enumerated data t y p e f o r p r o c e s s s t a t e ∗/ t y p e d e f enum { READY, RUNNING , EXIT } p r o c e s s s t a t e t ; /∗ C data s t r u c t u r e used as p r o c e s s c o n t r o l b l o c k . The s c h e d u l e r ∗ s h o u l d c r e a t e one i n s t a n c e p e r r u n n i n g p r o c e s s i n t h e system . ∗/ c© 2019, Faculty of IT, Monash University 3 About the program output 3 t y p e d e f s t r u c t { c h a r p r o c e s s n a m e [ 1 1 ] ; // a s t r i n g t h a t i d e n t i f i e s t h e p r o c e s s /∗ Times measured i n s e c o n d s . . . ∗/ i n t ent ryTime ; // t ime p r o c e s s e n t e r e d system i n t s e r v i c e T i m e ; // t h e t o t a l CPU t ime r e q u i r e d by t h e p r o c e s s i n t remain ingTime ; // r e m a i n i n g s e r v i c e t ime u n t i l c o m p l e t i o n . p r o c e s s s t a t e t s t a t e ; // c u r r e n t p r o c e s s s t a t e ( e . g . READY ) . } p c b t ; You may modify this struct definition to include additional process information if you wish. 2.0.1 To ‘run’ a process Our processes have state information, but no program code to be executed! Therefore, to ‘run’ a process for one unit of time, your program should simply sleep for one second (or the amount of time until the state of the system changes). (Although we don’t have real processes to run, it makes sense that the scheduler would be sleeping while the scheduled process is ‘running.’) 3 About the program output In the lecture on I/O, two types of terminal device (both line-based and form-based) were mentioned. Up until now, you have been printing to a line-based terminal, but this is not the only possible target for standard output! In this assignment, you will use a form-based terminal to display the process scheduling chart graphically. Your VM environment includes such a system known as ioL. ioL makes use of markup instructions (similar to HTML1) to interpret how to display content on the screen. To save you having to learn ioL’s markup language yourself, a small ‘library’ of four functions has been provided for this assignment. These are provided in the files: process-visualiser.h and process-visualiser.c. You should include these files in 1Unlike HTML which was designed for one-way transmission of a web page to a web browser, ioL is designed for synchronous communication between the program and the user. c© 2019, Faculty of IT, Monash University 3 About the program output 4 your submission. You are free to modify these functions if desired, but do not move the functions out of the files provided. The functions allow you to plot bar segments on the screen, with one row for each process. Bars can be dotted (for processes in the ready state/waiting) or solid (for the currently running process). Figure: Sample output for a particular data set. (Note: the use of colors, captions, etc. is up to your own design preference.) • void initInterface(const char* backgroundColor, const char* foregroundColor) — call this function first to set up the user interface before you produce other output. c© 2019, Faculty of IT, Monash University 3 About the program output 5 • int appendRow(const char* processName) — use this to add a row to the chart representing a process in the system. Returns an index number for the new row. • int appendBar(int rowIndex, int length, const char* color, const char* caption, int dotted) — adds a bar of activity to the end of the specified row. • void appendBlank(int rowIndex, int length) — adds a blank space to the end of the specified row (e.g. process has not arrived in the system yet). • void waitExit() — keeps the window open until the user decides to exit. For instructions on using these functions: read the comments in the process-visualiser.h header file. You can also choose what color to make each bar segment, and specify a caption (string of text) to be displayed when the user moves the mouse over a bar. These design choices are up to you. Printing text output in the form-based terminal During the simulation, you should print information about how the state of the system has changed (e.g. ”Process A now running.”). To print output, simply use the printf() function (or write to standard output in whichever way you prefer). However: note that ioL uses the following characters for markup instructions.2 If you print them in your output, you may get strange results. < > { } Also note that the ioL console produces new-lines in a different way to the regular line-based terminal. To produce a newline, print the “” character sequence (instead of the regular \n): p r i n t f (” H e l l o w o r l d !”); /∗ This t e r m i n a l r e q u i r e s a d i f f e r e n t n e w l i n e s e q u e n c e . ∗/ 2 For more information about ioL’s markup syntax (e.g. for printing text in bold or italics), refer to the online documentation at: http://doc.iol.science – however this is not required for this assignment. c© 2019, Faculty of IT, Monash University 3.1 Running the program in the form-based terminal 6 3.1 Running the program in the form-based terminal When you try to run your program in the normal terminal environment, you may see weird markup code in the terminal. To run your program in the ioL terminal environment (to see the output displayed correctly), place ‘iol — ’ in front of the command.3 For example: i o l −− . / y o u r p r o g r a m arg1 arg2 . . . 4 If you require extra help If you are stuck knowing where to begin, refer to the helpful hints in section 8. This assignment is an independent learning and assessment exercise. You may utilise the student forums to ask questions and obtain clarification, however you may not share details or code in your implementation with other students, nor may you show your code to the teaching team prior to submission. This is an assessment task: tutors and lecturers are not permitted to help you debug your assignment code directly (you are expected to debug and test your own code), but can help with more general queries, such as queries related to C programming syntax, concepts and debugging tips. You may make use of online references with appropriate citation in accordance with academic integrity policies, however your work must be your own. 5 Task 1: non-preemptive scheduling Choose one of these scheduling algorithms to implement. • FCFS (First come, first served) • SPN (Shortest process next) Write a scheduling simulator for your chosen algorithm as described above. 3Due to a known issue in our Virtual Machine environment, ioL may glitch-out the very first time you run it. In this case, press Ctrl+C in the bash window and try again. c© 2019, Faculty of IT, Monash University 5 Task 1: non-preemptive scheduling 7 Yo
ur main C source file should be named with your student ID as: non-preempt-123456789.c, where 123456789 is your student ID.4 Your program should take a filename as its only argument. If no argument is specified, use the default filename process-data.txt. Each line in the process data file (process-data.txt) should contain space-separated values for a single process as follows: [ p r o c e s s name ] [ a r r i v a l t ime ] [ s e r v i c e t ime ] For example: P1 0 3 P2 1 6 P3 4 4 P4 6 2 Times are measured in seconds. In the above file, the process named P1 enters the system at time: 0 seconds, and has a total required service time of 3 seconds, and so on. You cannot assume that the entries will be listed in order of entry time. You can assume that the maximum number of processes in the system is limited to 10. For creating the process-data.txt file, a utility has been provided to assist you. Download and compile create-data.c to use the utility. Alternatively, you could just enter your process data using an ordinary text editor. Note: you can assume that the name of each process is never more than 10 characters in length and does not contain spaces. Your scheduler should read the process data from the file.5 It should then begin ‘running’ the processes according to your chosen algorithm. Each process in the system should be stored in its own process control block using the pcb t data structure as defined above, which should be kept updated throughout the lifetime of the process. While a process is ‘running’, your scheduler should sleep for the appropriate length of time using the sleep function. When each process completes, print the following information: • The name of the process that has completed 4 If your completed program contains additional source files, you may name other source and header files as you wish. 5Hint: You may (if you wish) use high-level functions such as fopen, fclose and fscanf defined in for reading the file contents. Note that these functions do not work with the low-level open, close, etc. functions you have used in the previous assignment. c© 2019, Faculty of IT, Monash University 6 Task 2: Preemptive Round Robin scheduling 8 • The process’s turnaround time • The process’s total wait time. You should also print a message whenever a process enters the system, or enters the running state. Document the usage of your program in a plain text file and include this with your submission. Also document any assumptions you have made about your interpretation of the scheduling algorithm’s implementation. 6 Task 2: Preemptive Round Robin scheduling Now implement a second scheduling program according to the same requirements as task 1, except: • Now Implement Round Robin scheduling on the given process data, with a time-slice quantum of 2 seconds. For this task, your main C source file should be named with your student ID as: preempt-123456789.c, where 123456789 is your student ID.6 Both your Task 1 and Task 2 implementations should be separate programs. User documen- tation for both tasks may be included in a single file. If you need to make an assumption about how to interpret the scheduling in a certain circumstance, you should mention any such assumptions in your documentation. 6.1 Important: commenting is required Commenting your code is essential as part of the assessment criteria (refer to Section 7). All program code should include three types of comments: (a) File header comments at the beginning of your program file, which specify your name, your Student ID, the start date and the last modified date of the program, as well as with a high-level description of the program. (b) Function header comments at the beginning of each function should describe the function, arguments and interpretation of return value. (c) In-line comments within the program are also part of the required documentation. 6 If your completed program contains additional source files, you may name other source and header files as you wish. c© 2019, Faculty of IT, Monash University 7 Marking criteria 9 7 Marking criteria Tasks 1 and 2 are worth 50% each. The same marking criteria will be applied to both tasks: • 50% for working functionality according to specification. • 20% for code architecture (algorithms, use of functions for clarity, appropriate use of libraries, correct use of pointers, etc. in your implementations of the three tasks.) • 10% for general coding style (clarity in variable names, function names, blocks of code clearly indented, etc.) • 20% for documentation (user documentation describes functionality for the relevant task, critical assumptions are documented, code is well-commented with file-header-, function- header-, and inline- comments.) 8 Helpful hints 8.1 If you aren’t sure where to begin… Try breaking the problem down until you find a starting point that you are comfortable with. You can extend the functionality later, once you have a small part working, and you can still pass the assignment without all of the functionality completed. • A good place to start is simply to try printing some output, adding some rows to the chart and appending some bars to each row in different lengths and colours. • If you find that the window appears and disappears quicker than you can read the output, try using the waitExit() function provided in process-visualiser.h. • Or, if you aren’t sure where to begin with producing graphical output, start out just printing text output. • Use the utility provided (create-data.c), to generate process data files to test with, and take a look at the resulting files in a text editor. • If you are having difficulty reading the process values from a file, try hard-coding them at first, in order to get other parts of your program working first. (Later, adapt your code to read the values from file instead.) c© 2019, Faculty of IT, Monash University 8.2 DOs and DON’Ts 10 8.2 DOs and DON’Ts Do… Don’t… (!) + read through the comments in process-visualiser.h for instructions – copy and paste the provided visualisation functions into another file + break your program logic into multiple func- tions to make things easier to handle – stuff everything into a single main function. + follow a clear convention for variable names – use vague names like array or p. + copy the specified pcb t data type definition into your program – hard-code lots of separate variables. + use a sensible data structure for holding up to 10 process control blocks – hard-code separate variables for each process. + use a loop (and sleep function) to simulate the passage of time – try to determine process states in an ad-hoc way. + comment your code as you write it – leave commenting until the last step. + check over this specification carefully (e.g. using a pen or highlighter) – skip over specified instructions. 9 Submission There will be NO hard copy submission required for this assignment. You are required to archive and compress all your deliverables into a single .tar.gz file named with your Student ID, for submission. For example, if your Student ID is 12345678, you would submit a zipped file named 12345678 A2.tar.gz. Your submission is via the assignment submission link on the FIT2100 Moodle site by the due date specified in Section 1, i.e. 14th October 2019 (Monday) by 11:00am. Note: You must ensure you complete the entire Moodle submission process (do not sim- ply leave your assignment in draft status) to signify your acceptance of academic integrity requirements. 9.1 Deliverables Your submission should be archived and compressed into a single .tar.gz file containing the following documents: • Electronic copies of ALL your files (e.g. C source file(s)) that are needed to compile c© 2019, Faculty of IT, Monash University 9.2 Academic Integrity: Plagiarism and Collusion 11 and run your program. (Note that your program must run in the Linux Virtual Machine environment which has been provided for this unit. Any implementation that does not run at all in this environment will receive no marks.) • A user documentation file (not more than 2 pages) in plain .
txt format with clear and complete instructions on how to compile and run your program. Marks will deducted for any of these requirements that are not strictly complied with. 9.2 Academic Integrity: Plagiarism and Collusion Plagiarism: Plagiarism means to take and use another person’s ideas and or manner of ex- pressing them and to pass them off as your own by failing to give appropriate acknowledgement. This includes materials sourced from the Internet, staff, other students, and from published and unpublished works. Collusion: Collusion means unauthorised collaboration on assessable work (written, oral, or practical) with other people. This occurs when you present group work as your own or as the work of another person. Collusion may be with another Monash student or with people or students external to the University. This applies to work assessed by Monash or another university. It is your responsibility to make yourself familiar with the University’s policies and procedures in the event of suspected breaches of academic integrity. (Note: Stu- dents will be asked to attend an interview should such a situation is detected.) The University’s policies are available at: http://www.monash.edu/students/academic/ policies/academic-integrity c© 2019, Faculty of IT, Monash University
