辅导CPSC 415语言、讲解C++程序语言、c++编程设计调试

日期：2020-11-15 09:22

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