Skip to content Skip to navigation

Connexions

You are here: Home » Content » Project 5: Multi-programming, Inter-process Communication & Scheduling

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • VOCW

    This module is included inLens: Vietnam OpenCourseWare's Lens
    By: Vietnam OpenCourseWare

    Click the "VOCW" link to see all content affiliated with them.

Recently Viewed

This feature requires Javascript to be enabled.
 

Project 5: Multi-programming, Inter-process Communication & Scheduling

Module by: Duong Anh Duc. E-mail the author

Summary: Operation Systems One-month project

Nachos is currently an uni-programming environment. In the second project you will design and implement appropriate support for multiprogramming. You will extend the system calls to handle process management and inter-process communication primitives. In addition you will implement a priority based scheduling and aging mechanism in nachos. You will add this to the coded first project. Make sure you correct all the deficiencies in your first project before starting the second project.

Phase 1 –Memory allocation for multiprogramming: (15%)

Required Reading –

  • Translate.h / .cc – Each object of this class is a translation of a single virtual page to a physical page.
  • Addrspace.h / .cc – Consists of all data needed to keep track of executing user programs. The constructor allocates memory/pages to processes assuming every virtual address is the same as its physical address. This restricts us to running one user program at a time. In this project we modify the constructor to allow multiple user programs to be run concurrently.
  • Progtest.cc – The StartProcess function serves as the starting point of every thread, where the addrspace is created and execution of the userprogram begins. You might have to create a similar function to account for new threads that you create.
  • System.h / .cc – All global/system objects are defined here.
  • Machine.h / .cc - emulates the part of the machine that executes user programs: main memory, processor registers, etc.

To implement multiprogramming we will have to alter Nachos so that each process is maintained in its own system thread. We will have to take care of memory allocation and de-allocation. Here are the details:

  1. Add a case in exception handler so that non-system call exceptions can finish (currentThread>Finish()) the thread. This will be important, as a run time exception should not cause the operating system to shut down.
  2. Implement multiprogramming. The code we have given you is restricted to running one user program at a time. You will need to make some changes to addrspace.h, and addrspace.cc in order to convert the system from uniprogramming to multiprogramming. You will need to:
  1. Come up with a way of allocating physical memory frames so that multiple programs can be loaded into memory at once.
  2. Provide a way of copying data to/from the kernel from/to the user’s virtual address space.
  3. Properly handling freeing address space when a user program finishes.
  4. It is very important to alter the user program loader algorithm such that it handles memory in terms of pages. Currently, memory space allocation assumes that a process is loaded into a contiguous section of memory. Once multiprogramming is active, memory will no longer appear contiguous in nature. If you do not correct the routine, it is most likely that loading another user program will corrupt the operating system.

Phase 2 –Process Management: (35%)

  1. Implement the SpaceID Exec(char *name, int priority) system call. Exec starts a new user program running within a new system thread with the given priority. You will need to examine the “StartProcess” function in progtest.cc in order to figure out how to set up user space inside a system thread. Exec should return –1 on failure, else it should return the “Process SpaceID” of the user level program it just created. (Note: SpaceIDs can be kept track of in a similar manner to OpenFileIDs of your project 1, except that you will want to keep track of them outside the thread.). For this phase you can simply ignore the priority.
  2. Implement the int Join(SpaceID id) and void Exit(int exitCode) system calls. Join will wait and block on a “Process SpaceID” as noted in its parameter. Exit returns an exit code to whomever is doing a join. The exit code is 0 if a program successfully completes, another value if there is an error. The exit code parameter is set via the exitcode parameter. Join returns the exit code for the process it is blocking on, -1 if the join fails. A user program can only join to processes that are directly created by the Exec system call. You can not join to other processes or to yourself. You will have to use semaphores inside your system calls to coordinate Joining and Exiting user processes. Also make sure that all processes release the resources they have been allocated, after they Exit.

Phase 3 – IPC primitives (Semaphores) (10%)

  1. Implement the int CreateSemaphore(char *name, int semval) system call. You will have to update start.s and syscall.h to add the new system call signatures. You will create a container at the system level that can hold upto 10 named semaphores. The CreateSemaphore system call will return 0 on success and –1 on failure. The CreateSemaphore system call will fail if there are not enough free spots in the container, the name is null, or the initial semaphore value is less than 0.
  2. Implement int wait(char *name) and int signal(char *name) system calls. Make sure you follow the wait and signal as the mnemonics for these two and not down and up or P and V. The name parameter is the name of the semaphore. Both system calls return 0 on success and –1 on failure. Failure can occur if the user gives an illegal semaphore name (one that has not been created).

Phase 4 –Priority Scheduling & Simple Aging

Required Reading –

  • Thread.h / .cc – The thread class has methods like Yield, Sleep, Finish to manage the scheduling of threads. Understand of this class is essential to proceed.
  • List.h /.cc – Implementation of a Generic Linked List. Understand the importance of the methods of this class clearly especially the SortedRemove & SortedInsert. The ready queue maintained by the scheduler is an object of this type.
  • Scheduler.h / .cc – Implementation of the nachos thread scheduler & dispatcher. You will have to make the majority of your changes in this class.

In this phase you will be implementing a policy that schedules threads depending upon the priority that you set for threads using the Exec(char * name, int priority) syscall. The details are as follows -

  • Modify the thread scheduler to always return highest priority thread. You will have to create another parameter in the Thread class– the priority level of the thread represented by an integer value. The range of thread priorities can be found in thread.h. Provide the appropriate tests in order to demonstrate the success of your priority scheduling system. Note: Enabling the –rs option for the test programs causes a thread to stop for context switching Yield the CPU to another thread (that could have lower priority) after a given time slice. You might want to have a look at the Thread: :Yield() method to take care of this. (7%)
  • Most priority scheduling solutions will starve out a low priority thread. After you complete and test the above part, implement a simple aging system to take care of the starvation problem. Under this policy the priority of a thread decreases one unit for every x times the thread is run. That is for every x thread switches from ready to run, decrement the priority of the high priority threads by 1. Specify x as a constant in your system, with the value -1 indicating that aging is disabled. Add thread (“t”) debug statements to display the trace of the aging algorithm. Provide the appropriate tests in order to demonstrate the success of your aging system. (9%)

Phase 5 –Putting it all together

  1. Implement a simple shell program to test your new system calls implemented as above. The shell should take a command at a time, and run the appropriate user program. The shell should “Join” on each program “Exec”ed, waiting for the program to exit. On return from the Join, print the exit code if it is anything other than 0 (normal execution). Also, design the shell such that it can run program in the background. Any command starting with character (&) should run in the background. (Ex: &create will run the test program create program in the background.) (6%)
  2. Solve the Dining Philosopher problem discussed in your text book. Use Semaphore you designed for realizing mutual exclusion and synchronization among the philosophers. (8%)

Documentation - Includes internal documentation, and external documentation as described:

  • How did you maintain a list of all processes in the system? What other data structures did you require? (3%)
  • Explain the significance of the Join & Exit system calls. How did you synchronize the 2 syscalls? (4%)
  • What changes did you make to implement Phase 4, and why? (3%)

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks