代写CPSC 415语言、代做C++程序语言、c++编程设计调试

日期：2020-11-14 11:56

Assignment 2

This assignment is, ideally, to be done in pairs. Working alone is strongly discouraged.

Errata

a) None so far

1 Motivation

The purpose of this assignment is to investigate process pre-emption, simple device drivers, and

synchronization through semaphores. In this assignment you will extend your kernel to pre-empt

processes, provide a simple sleep device, and implement semaphores. In doing so you will learn

about how a kernel schedules a CPU, manages shared resources, handles interrupts, and the blocking

and unblocking of process due to demdnd for resources.

2 To Start

Although the assignment is doable on your own, you are very strongly encouraged to work with

a partner. Your starting point is the kernel resulting from the first assignment. If you did not

complete assignment 1, or don’t wish to use your kernel, you may use a kernel from someone else in

the class, with their permission, or the solution kernel you will get when you clone the assignment

repo. You are also free to merge you or your partner’s assignment 1 solution with the sample

solution if you prefer. Your assignment must compile on the department Linux machines and run

in the Bochs emulator on those machines.

In this assignment you will modify the code in several modules and add a couple more modules

to extend the kernel. Note: If you use the supplied solution, the kfree() function is not

fully implemented and does not actually free memory. Consequently, don’t get too

exuberant with kmalloc() and expect kfree() to help you out.

The provided assignment 1 solution kernel compiles without any compiler warnings except for

routines in the libx directory. Your code, regardless of the kernel you start with, must also compile

without warnings except for files in the libx directory and maybe a warning about an unused

variable in ctsw.c to hold the kernel stack pointer. You are not allowed to change the command

line options to the compiler to achieve this. (You should check the sample solution to see how it

avoids having the unused variable message.)

Note: Sometimes you may see the message Clock skew detected. Your build may be incomplete.

I have never managed to figure out just what conditions cause this message to be generated, nor has

1

a problem with the build ever been observed when the message is printed. If in doubt do a make

clean and rebuild the code. You might get the message again, but it won’t produce the required

zImage file if there was an actual problem.

2.1 Assignment 2 - GIT Usage

For this assignment everyone is required to use a GIT repository on the department’s bitbucket

server to manage the source code for their assignment. Furthermore you are required to regularly

“push” your changes to the server. Consult the assignment 1 description for the basic GIT references

and commands to do this.

NOTE: You are expected to regularly check-in the work you have done throughout the assignment.

To encourage this part of the grade for this assignment will be based on a regular and

reasonable check-ins of your code. If working in pairs it is expected that both partners will contribute

to the assignment and check-in code. It is accepted that the checking in of code

may not be 50/50, but if only one person is checking in code then questions might be

raised about who is doing the work and consequently who deserves the marks.

2.2 Using your own kernel or someone else’s

If you plan on using the supplied solution kernel, skip the step in the next paragraph.

After completing the steps in the previous section copy all the modified .c, and .h files from

assignment 1 that you intend to use over-top the supplied files. Use the git add, rm (if needed),

commit and push commands to commit the changes and push them to the repository. You should

also tag this set of files as your starting point. (Check the GIT references to figure out how to do

this if you didn’t do it in A1.)

3 Objectives

You will extend the kernel from the first assignment. In your documentation you must state

which kernel you are using, be it your own, the provided solution kernel, or someone

else’s.

There are three main implementation goals for this assignment:

• To add pre-emption. (i.e. time slicing);

• To implement a simple sleep device;

• To implement semaphores.

In addition, you will need to implement a couple of auxiliary system calls to help things work

smoothly.

There are numerous ways to tackle this assignment. One way is to implement the kernel

extensions in the order they are described in this document. Another order would be to implement

section 3.3 after completing 3.4. If you use this latter approach you may want to disable pre-emption

while working on 3.3, but don’t forget to turn pre-emption back on and to re-test things.

Regardless of the order you choose, you need to test each extension before proceeding to the

next. The list below summarizes the extensions. For most of these extensions the dispatcher

2

function dispatch() in dispatch.c will require modifications and consequently it is not explicitly

mentioned.

Auxiliary System Calls: Add sysgetpid(), syskill() sysputs() in syscall.c - some useful

system calls.

Semaphore system calls: sysP() and sysV() in syscall.c - used by processes for critical section

protection.

Sempahore system - kernel side: P kern() and V kern() in semph.c - used by the kernel for

handling semaphores. The precise arguments amd details of the implementation of these

functions are left as design/implementation decisions for you to make.

Pre-emption: contextswitch() and contextinit() in - ctsw.c for timer interrupts and time

slicing.

Idle process: idleproc() in init.c - to avoid running out of processes.

Sleep system call: syssleep() in syscall.c - used by a process to sleep a specified time.

Sleep device: sleep() and tick() in sleep.c - code in the kernel for processing sleep request

and timer ticks.

Producer/consumer: producer() (really root) and consumer() in user.c - improved producer/consumer.

(Yes, it isn’t a good name choice for demonstrating semaphore usage, but

I wasn’t feeling creative.)

You may also need to update various .h files to add add constants, data structures, prototypes etc.

Such updates will not always be explicitly mentioned in the assignment description.

3.1 Auxiliary System Calls

Add the four new system calls in syscall.c with corresponding additions to disp.c. The system

call sysgetpid() returns the PID of the current process and syskill() takes a PID as an argument,

and terminates the process. To simplify things, a PID is of type PID t which is a typedef of an

unsigned int.

The prototype for sysgetpid() is

extern PID t sysgetpid( void );

The system call sysputs() is to be used by processes to perform output. Since processes can

be pre-empted, and the screen is a shared resource, access to the screen must be synchronized via

the sysputs() system call. The system call takes a null terminated string that is to be displayed

by the kernel. Since the kernel cannot be pre-empted, the kernel side of sysputs()can use kprintf

to print the string. The prototype for the system call is

extern void sysputs( char *str );

3

You can use sprintf() to create formatted strings for fancier printing. (sprintf() is like printf()

except it puts the resulting string into memory, as opposed to printing it.)

The syskill() call terminates the process identified by the argument to the call. The call

returns 0 on success. The call fails with -1 if the target process does not exist. It is okay for a

process to call kill on itself. In this case the call does not return and the process terminates. The

prototype is

extern int syskill( PID t pid );

The final auxiallary call you are to implement is syssetprio() which allows a process to set

its priority. The prototype for the call is:

extern int syssetprio( int priority );

In this system a process can have a priority from 0 to 3, with 3 being the highest priority and 0

being the lowest. Processes are created with priority 3. The result returned by this call is -1 if the

call fails for any reason (e.g. requested priority is out of range), otherwise it returns the priority

the process had prior to this call changing the priority.

There is one special case and that is priority -1. If the requested priority is -1 then then call

simply returns the current priority of the process and does not update the process’s priority.

3.2 Changes to Process Management

For this assignment you must clean-up resources that are directly associated with a process. This

includes, among potentially other things, the stack and any data that might be part of the message

passing system.

One of the resources associated with a process is its PCB and as a result it must be possible to

reuse a PCB. A side effect of this is that you will have to be careful with respect to how you assign

PIDs. A PID cannot simply be the index into the PCB table. A good PCB selection algorithm

will make it possible to index into the PCB in small, constant time while still making it easy to

determine whether or not a PID is valid. In addition, to minimize the problems with process

interactions based on PIDs, the PID reuse interval needs to be as large as possible.

In assignment 1 if a process runs off the end of its code (i.e. doesn’t call sysstop() and just

keeps going) or executes the C language return statement bad things happen. (If you don’t believe

this just try adding a return to one of your processes in assignment 1.) In this assignment you are

to modify the process creation code so that if a process does a return, either explicitly through th

process to receive from is blocked on a send to this process return statement or by running off the

end of its code, the process is cleaned up appropriately and the process/system does not crash or

restart.

There are a couple of ways to do this. One is to set-up the stack of the process so that

when the process “returns” it transfers control to sysstop(). (i.e. set-up the stack so that the

spot that contains the return address for the function call now contains the address of sysstop().)

Alternatively you could introduce a “wrapper” process. This process takes as an argument the

function address passed in as the argument to syscreate(). Now each time a process is created

the wrapper process is what is created. The body of this process will call the real process (i.e.

the address of the user function passed to syscreate()), and when the “user process” returns, the

“wrapper process” will call sysstop(). For this approach to work, when the wrapper process

4

is created the stack will have to be constructed such that when the wrapper process runs it can

retrieve the address of the user function to “call” (i.e. run). That means the arguments will have to

be placed in the appropriate place of this initial stack. It should be noted that with both of these

approaches no assembly language code is required. You may choose either approach or develop

something of your own.

3.3 Semaphore Subsystem

This section describes a semaphore system for our Xeros kernel. In a general purpose semaphore

system there are normally calls to create and destroy semaphores. In this system that will not be

the case. The kernel will initially create and initialize two semaphores identified by the integer

values 0 and 1. At the kernel implementation level, each semaphore has associated with it an

integer value and a queue of processes blocked and waiting for that semaphore. The initial value

of the integer associated with a semaphore is 0. This integer is called the semaphore value. The

semaphore behaviour is as follows:

• Processes wanting to acquire a semaphore use the sysP() call. If the semaphore value is

0 the process is blocked on this semaphore. If the semaphore value is greater than 0. The

semaphore value is decremented by 1 and the process is not blocked.

• A process can “release” a semaphore by calling sysV(). The process calling sysV() is not

blocked. When sysV() is called, if there are processes blocked on the semaphore, the highest

priority process is unblocked and the semaphore value remains unchanged. If more than one

process of the same priority is waiting for a semaphore the first one makeing the sysP() is to

get the sempahore. If there are no processes blocked on the semaphore the semaphore value

is incremented by 1.

• the above actions are atomic at the kernel level.

The normal behaviour is that a process makes a corresponding sysV() to release an “acquired”

semaphore, but that is not a requirement. This implies that the sysV() call does not need to be

made by the process acquiring a semaphore. (Observe that some process without the semaphore

will initially have to call sysV() to get things going otherwise every call to sysP() will block.

Additionally, this semaphore implementation can be turned into a counting semaphore version by

making extra sysV()) calls.

3.3.1 The sysP() and sysV() Calls

To support the semaphore system two system calls are introduced and their specifications follow.

extern int P(int semaphore);

This function returns 1 on success and 0 on failure. The argument identifies which of the two

semaphores the sysP() operation applies to. If the parameter is invalid 0 is returned otherwise 1

is returned. If the value of the semaphore is 0 when sysP() is processed then the process blocks.

If the value is greater than 0 then the value is decremented by 1 and the process is not blocked.

extern int V(int semaphore);

5

This function returns 1 on success and 0 on failure. The argument identifies which of the two

semaphores the sysV() operation applies to. If the parameter is invalid, 0 is returned otherwise 1

is returned. If, when the call is made, there are processes blocked on the semaphore the highest

priority process is unblocked (if there are multiple processes of the same priority that can be

unblocked the one that called sysP() first is to be selected). If no processes are waiting on the

semaphore, the value is simply incremented. The process calling sysV()is not blocked.

3.4 Pre-emption

In order to pre-empt a process the kernel must get control of the processor. Since the currently

running process implicitly has control of the CPU, a hardware timer interrupt is used to transfer

control to the kernel on a regular basis. In order to make our kernel pre-emptive, four steps need to

be performed. First the context switcher needs to be modified to handle both the hardware timer

interrupt, and the software system call interrupt; this is outlined in Figure 1. This figure is a broad

outline of the processing and does not identify precisely what needs to be done and how.

ContextSwitcher

push kernel state onto the kernel stack

save kernel stack pointer

switch to process stack

save return value of system call

pop process state from the process stack

iret

timer entry point:

disable interrupts

push process state onto process stack

save some sort of indication that this is a timer interrupt

jump to common entry point

syscall entry point:

disable interrupts

push process state onto process stack

save some sort of indication that this is system call

common entry point:

save process stack pointer

switch to kernel stack

pop kernel state from kernel stack

recover entry point type to determine return type.

return from context switcher

Figure 1: The new context switcher.

Immediately after an interrupt occurs, the interrupts need to be disabled since we are not

building a re-entrant kernel. (In the set evec() code provided, when the interrupt vector is set-up,

a trap gate is specified instead of an interrupt gate so disabling interrupts isn’t done automatically.

6

Note that the context switcher draft 2 assumes that the interrupts are automatically disabled.

However, a couple of slides later it is pointed out that one might have to disable interrupts explicitly.)

As a result, this means that interrupts need to be deferred while the kernel is running. Consequently,

the first instruction executed by the ISR needs to disable interrupt checking by the CPU. The cli

instruction does this. It is not necessary to re-enable interrupts before the iret is performed

because the restoration of the saved eflags register will have the interrupt bit appropriately set.

If you forget to do this you probably will not encounter any problems, or at least very rarely. It

turns out that if you don’t do the cli there is about a 5 instruction window where problems could

occur if a hardware interrupt goes off. (Think about why the window is so small or what would

cause the window of vulnerability to close after about 5 instructions.)

Since each interrupt has its own vector (i.e. address of the ISR code to jump to), we can easily

distinguish between a system call trap and a hardware interrupt, like the timer, by having different

ISRs. Ideally we want to reuse as much code as possible between the hardware interrupt and system

call trap processing code. A hardware interrupt, unlike an exception used for a system call, requires

that ALL registers contain what they had before the interrupt so special care needs to be taken.

Although which registers can be clobbered during the kernel’s processing of a system call is

design specific, it is the case that the return value of the system call will be in register eax. If the

context switcher returns the value of a system call in eax, and the same code is used to return from

an interrupt (which should be the case) then the return value of a hardware interrupt needs to be

the value of eax when the interrupt occurred.

To have hardware interrupts fit in with our context switch model, one approach is to make a

hardware interrupt appear like a system call. To do this the context switcher needs to return an

indication to the dispatcher that a timer interrupt occurred. It is recommended that you define a

TIMER INT request identifier along with all the other system call request identifiers that a dispatcher

can receive and have that returned by the context switcher when a timer interrupt occurs.

Next, modify the dispatcher to handle the TIMER INT request. This request should do the same

thing as the YIELD request: place the current process at the end of the ready queue, de-queue the

next process in the ready queue, and run it. In the next section you will have to add an additional

line of code to this request handler, so don’t share it with the yield code.

Third, change the initial flags being set by the context initializer in create.c. Instead of 0,

the interrupt bit should be enabled, i.e., the initial flags should be 0x00003200. (The 0x3000 will

prevent processes from accessing privileged I/O space, not that that should be an issue.)

Finally, you must add a set evec() call as part of configuring the timer interrupt. The timer

is on IRQ0 which translates to interrupt number 32. Make sure the handler is the timer entry

point in the context switcher and not the syscall entry point. You will also have to initialize the

timer and enable the corresponding interrupt on the PIC (i8259). To do this use the initPIT(

divisor ) function. This function takes one argument, the rate at which the timer should trigger

the interrupt. For example, specifying a value of 100 will mean that the interrupt will be triggered

every 100th of a second (every 10 milliseconds). Thus, a process will be given a time slice of 10

milliseconds, before being pre-empted. This is the recommended time slice for the system. Thus,

after the call to set evec() you should add

initPIT( 100 );

When a timer interrupt occurs, the hardware has to be re-armed in order for the interrupt

to occur again. This is done by signalling an end of interrupt (EOI). To signal an EOI use the

7

provided function end of intr(). This function should be called, probably from dispatch() as

the last operation in the servicing of the TIMER INT request. You will notice very quickly if you

forget to do this.

3.4.1 Priorities

In this system processes have priorities and the scheduling policy is that higher priority processes

(i.e. higher priority number) are always run first and that round-robin scheduling is used within a

priority. You are not to add kernel support to avoid CPU starvation (i.e. priorities are not adjusted

by the kernel based on how much CPU time a process has received) or to deal with the priority

inversion problem. If you are using the supplied kernel, observe that the code to manage the ready

queue is in disp.c and that there is a single queue. Consequently, you will need to modify the queue

management routines to support multiple ready queues. It is okay to change the next() and ready()

functions to take additional arguments, perhaps the number of the queue they are working on.

3.5 Idle Process

Since processes might become blocked for one reason or another, such as waiting to acquire a

semaphore or a timer to expire, among other things. Consequently it is important to ensure that

there is at least one ready process available at all times. As you know, bad things happen if the

kernel runs out of processes to schedule. In order to prevent this, you should create an idle process.

Its only job is to be ready and is simply an infinite loop. You will need to modify the dispatcher

so that the idle process will run only if no other process is available. Instead of just having the

idle process execute an infinite loop with an empty body, you might want to try executing the hlt

instruction in the body of the loop. (You don’t have to use hlt, it is just something you can try if

you like.)

The prototype for the process should be

extern void idleproc( void );

and it should be created by initproc(). You should start with a simple idle process before trying

to use hlt, if you choose to try hlt. If you ever schedule the idle process, and don’t have the timer

interrupt working, control will never return to the kernel.

3.6 Sleep Device

The sleep device will allow processes to sleep for a requested number of milliseconds. First, add

a system call syssleep() to syscall.c that takes one unsigned int parameter and returns an

unsigned int. The single parameter is the number of milliseconds the process wishes to sleep. For

example, to sleep for a second the call would be syssleep(1000); The prototype for the calls is

extern unsigned int syssleep( unsigned int milliseconds );

and should be added to xeroskernel.h. The return value for syssleep() is 0 if the call was

blocked for the amount of time requested otherwise it is the amount of time the process still had

to sleep at the time it was unblocked. In this assignment there is no mechanism to unblock the

process early, but in assignment 3 there will be. So, at this point one would always expect to get

back 0, although in A3 that won’t be the case.

8

Modify the dispatcher appropriately to recognize the system call, and have it call the corresponding

kernel sleep() function that you will write. To the TIMER INT request service code add

a call to a function called tick(). This function will also be written by you and it notifies the

sleep device code that a clock tick has occurred. Since Bochs is an emulator, it is sometimes the

case that the machine the emulator is running on can be emulated faster than the original machine

actually ran. As a result, time will pass faster on these machines than in “real” or “wall clock”

time. An attempt has been made to minimize this problem through configuration options in the

bochsrc file in the xeros directory, but don’t be overly concerned if things do not match wall clock

time.

To implement the kernel side of syssleep(), implement in sleep.c, the two functions sleep()

and tick(). The sleep() function places the current process in a list of sleeping processes such

that its place in the list corresponds to when it needs to be woken. Observe that the clock tick has

a certain granularity and that the parameter to syssleep() has a finer granularity than a clock

tick. To deal with this problem the kernel will treat the value of the parameter to syssleep() as the

minimum amount of time to sleep for and wake a process on the next clock tick after this minimum

amount of time has elapsed. To simplify the managing of the times and the sleep queue it would

be a good idea to convert, within the kernel, the amount of time to sleep into “clock ticks” (time

slices) and work from there. (Example conversions: 10ms = 1 tick, 11ms = 2 ticks, 0 ms = 0 ticks,

1ms = 1 tick etc). As an example, assuming times have been converted to ticks, if there are three

processes in the sleep list, that need to be woken after 5, 7, and 8 time slices respectively, and the

current process wants to sleep for 6 time slices, then it should be placed second in the sleep list.

You should try to come up with an efficient way of doing this. (Hint: delta list). The process is

NOT to be placed on the ready queue until it is woken. After the sleep() call completes, the

dispatcher selects the next process in the ready queue to run. Don’t confuse the behaviour of the

kernel sleep() function with that of syssleep(). The sleep() function always returns to the

dispatcher, even though a process is being blocked but the sysleep() call won’t return to the

application until at least the specified time has elapsed.

The tick() kernel function notifies the sleep device that another time slice has occurred. The

function should wake up any processes that need to be woken up by placing them on the ready

queue associated with their priority, marking them as ready, and updating internal counters.

3.7 Some Testing - Demonstrating Semaphores and Priorities

At this point you should have a pre-emptive multitasking kernel and you should have extensively

tested it. To demononstrate some of the system’s functionality implement processes with the

following behaviour:

Create a root process that:

• Prints a message saying it is alive.

• Calls sysV() on semaphore 0.

• Creates 4 processes and as each process is created prints a message saying it has created a

process and what that process’s PID is.

• It then loops and calls sysP() on semaphore 1 four times.

• It then prints ”Got 4 semaphores” Each of these processes does the following:

9

– Prints a message indicating it is alive and its PID.

– Sleeps for 5 seconds.

– Attempts to acquire semaphore 0.

– Prints a message saying it got the semaphore and then sleeps for 3 seconds.

– Prints a message saying sleeping has stopped and it is going to release the semaphore.

– Calls sysV() on both semaphores 0 and 1.

– Runs off the end of its code.

• The root process next sleeps for 4 seconds.

• The root process sets its priority to 0.

• The root process calls sysP() on semaphore 0. At this point the root process “has” both

semaphores.

• The root process sets a global variable “priority” to 0.

• The root process creates 4 processes.

• The root process then performs the following block of actions 4 times:

– Call sysV() on semaphore 0.

– Call sysP() on semaphore 1.

– Increments the global priority variable by 1.

• The root process prints a message that it is done an calls syskill() on itself.

• Each of the created processes does the following:

– Prints a message indicating what it’s PID is.

– Calls sysP() on semaphore 0.

– Reads the priority value from the global variable “priority”.

– Prints the “My priority will be” followed by the priority value.

– Sets its priority to the indicated priority.

– Calls sysV() on semaphore 1

– Prints 10 times, via a loop “Loop i” where is the iteration number.

– The process then exits by running off the end of its code.

Note - In the above each line of printing is to be on a line by itself and start with ”Process

xxx” where xxx is the process ID of the process before acutualling printing the message specified

above. The times are to be the actual values provided as a parameter to the sleep system call. (i.e

the times you specify to sleep should be the actual ones that would be used if the timer on the

emulator accurately captured wall clock elapsed time. You do not have to try to select sleep values

that result in the process actually sleeping that amount of time according to the “wall clock.” )

10

4 Write-up

Your write-up is to be a well organized, typed document containing testing and assignment questions

sections as described in the next sections.

4.1 Testing Documentation

Your testing documentation is to a plain text ASCII file with the name Testing.txt. A file with this

name has been provided for you.

You are to handin test output for the 6 test scenarios outlined below. Each test scenario is to

be different (i.e. exercises a different code path in the kernel.)

1. One test demonstrating that time-sharing is working.

2. Two tests of syskill();

3. Two tests showing that priorities work.

4. One test showing the priority inversion problem.

The documentation is to organized in sections, with each section corresponding to one test.

The sections are to organized in the order of the tests described above. Each section is to indicate

the purpose of the test and provide a brief description of how the test was performed (i.e. what

was the scenario, how it was actually done.) You are then to provide a sample run for the test. It

is acceptable to remove large areas of repeated data provided you indicate this and you may also

annotate the output. Finally, indicate if this test was a pass or a fail. Note that it acceptable for

your program to fail a test. In such a case you will get full marks for the testing portion of the

assignment but may not get full marks in the implementation part of the assignment.

4.2 Some Questions to ponder

You do not have to hand in the answers to these questions. However they are representative of the

types of questions you might get on an exam.

1. In the implementation section, the instructions have the use of set evec() occurring before

the call to initPIT(). Could the order of these two calls be reversed (i.e. could initPIT()

be called before set evec()? Carefully explain/justify your answer.

2. Currently the function signature for new processes is such that the function takes no arguments.

Suppose that the syscreate() call were changed so that all functions passed to

syscreate() expect two arguments. The function being passed to create now has the form:

function(int argc, int** argv)

Draw and label as precisely as possible a picture of what a process’s stack would look like when

it is put onto the ready queue for the first time. The picture you draw is to assume that the

changes required by the “Changes to Process Management” section have been implemented.

11

5 How the TA’s will Test Your Code

To test your code, the TA’s will do three things. First, they will compile and run your code as is,

verifying that the testing scenario above seems to work. Second, they may replace your user.c

with ours, recompile the code and run it. Our code will test your kernel. Third, the TA’s will

visually inspect your code and meet with you to discuss your assignment.

6 What to Hand In

Handing in is done by simply making sure that your git repository with all appropriately committed

changes has been pushed to the Stash server. You will be marked on the last push to the main

branch of the repo and any late penalty computed will be based on the time of that push. If you

have added any files to your code base don’t forget to add them to the repo before doing your

commit and push. It can never hurt to clone the repo after you have handed things in and then

test that your assignment builds and runs as expected on the department Linux machines.

12