” 辅导CPSC 415语言、 写作C++程序语言Assignment 2This assignment is, ideally, to be done in pairs. Working alone is strongly discouraged.Errataa) None so far1 MotivationThe purpose of this assignment is to investigate process pre-emption, simple device drivers, andsynchronization through semaphores. In this assignment you will extend your kernel to pre-emptprocesses, provide a simple sleep device, and implement semaphores. In doing so you will learnabout how a kernel Schedules a CPU, manages shared resources, handles interrupts, and the blockingand unblocking of process due to demdnd for resources.2 To StartAlthough the assignment is doable on your own, you are very strongly encouraged to work witha partner. Your starting point is the kernel resulting from the first assignment. If you did notcomplete assignment 1, or dont wish to use your kernel, you may use a kernel from someone else inthe class, with their permission, or the solution kernel you will get when you clone the assignmentrepo. You are also free to merge you or your partners assignment 1 solution with the samplesolution if you prefer. Your assignment must compile on the department Linux machines and runin the Bochs emulator on those machines.In this assignment you will modify the code in several modules and add a couple more modulesto extend the kernel. Note: If you use the supplied solution, the kfree() function is notfully implemented and does not actually free memory. Consequently, dont get tooexuberant with kmalloc() and expect kfree() to help you out.The provided assignment 1 solution kernel compiles without any compiler warnings except forroutines in the libx directory. Your code, regardless of the kernel you start with, must also compilewithout warnings except for files in the libx directory and maybe a warning about an unusedvariable in ctsw.c to hold the kernel stack pointer. You are not allowed to change the commandline options to the compiler to achieve this. (You should check the sample solution to see how itavoids 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 has1a problem with the build ever been observed when the message is printed. If in doubt do a makeclean and rebuild the code. You might get the message again, but it wont produce the requiredzImage file if there was an actual problem.2.1 Assignment 2 – GIT UsageFor this assignment everyone is Required to use a GIT repository on the departments bitbucketserver to manage the source code for their assignment. Furthermore you are required to regularlypush your changes to the server. Consult the assignment 1 description for the basic GIT referencesand 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 andreasonable check-ins of your code. If working in pairs it is expected that both partners will contributeto the assignment and check-in code. It is accepted that the checking in of codemay not be 50/50, but if only one person is checking in code then questions might beraised about who is doing the work and consequently who deserves the marks.2.2 Using your own kernel or someone elsesIf 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 fromassignment 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 shouldalso tag this set of files As your starting point. (Check the GIT references to figure out how to dothis if you didnt do it in A1.)3 ObjectivesYou will extend the kernel from the first assignment. In your documentation you must statewhich kernel you are using, be it your own, the provided solution kernel, or someoneelses.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 worksmoothly.There are numerous ways to tackle this assignment. One way is to implement the kernelextensions in the order they are described in this document. Another order would be to implementsection 3.3 after completing 3.4. If you use this latter approach you may want to disable pre-emptionwhile working on 3.3, but dont 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 thenext. The list below summarizes the extensions. For most of these extensions the dispatcher2function dispatch() in dispatch.c will require modifications and consequently it is not explicitlymentioned.Auxiliary System Calls: Add sysgetpid(), syskill() sysputs() in syscall.c – some usefulsystem calls.Semaphore system calls: sysP() and sysV() in syscall.c – used by processes for critical sectionprotection.Sempahore system – kernel side: P kern() and V kern() in semph.c – used by the kernel forhandling semaphores. The precise arguments amd details of the implementation of thesefunctions are left as design/implementation decisions for you to make.Pre-emption: contextswitch() and contextinit() in – ctsw.c for timer interrupts and timeslicing.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 requestand timer ticks.Producer/consumer: producer() (really root) and consumer() in user.c – improved producer/consumer.(Yes, it isnt a good name choice for demonstrating semaphore usage, butI wasnt 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 CallsAdd the four new system calls in syscall.c with corresponding additions to disp.c. The systemcall 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 anunsigned int.The prototype for Sysgetpid() isextern PID t sysgetpid( void );The system call sysputs() is to be used by processes to perform output. Since processes canbe pre-empted, and the screen is a shared resource, access to the screen must be synchronized viathe sysputs() system call. The system call takes a null terminated string that is to be displayedby the kernel. Since the kernel cannot be pre-empted, the kernel side of sysputs()can use kprintfto print the string. The prototype for the system call isextern void sysputs( char *str );3You 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 callreturns 0 on success. The call fails with -1 if the target process does not exist. It is okay for aprocess to call Kill on itself. In this case the call does not return and the process terminates. Theprototype isextern int syskill( PID t pid );The final auxiallary call you are to implement is syssetprio() which allows a process to setits 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 0being the lowest. Processes are created with priority 3. The result returned by this call is -1 if thecall fails for any reason (e.g. requested priority is out of range), otherwise it returns the prioritythe 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 callsimply returns the current priority of the process and does not update the processs priority.3.2 Changes to Process ManagementFor this assignment you must clean-up resources that are directly associated with a process. Thisincludes, among potentially other things, the stack and any data that might be part of the messagepassing system.One of the resources associated with a process is its PCB and as a result it must be possible toreuse a PCB. A side effect of this is that you will have to be careful with respect to how you assignPIDs. A PID cannot simply be the index into the PCB table. A good PCB selection algorithmwill make it possible to index into the PCB in small, constant time while still making it easy todetermine whether or not a PID is valid. In addition, to minimize the problems with processinteractions 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. doesnt call sysstop() and justkeeps going) or executes the C language return statement bad things happen. (If you dont believethis just try adding a Return to one of your processes in assignment 1.) In this assignment you areto modify the process creation code so that if a process does a return, either explicitly through thprocess to receive from is blocked on a send to this process return statement or by running off theend of its code, the process is cleaned up appropriately and the process/system does not crash orrestart.There are a couple of ways to do this. One is to set-up the stack of the process so thatwhen the process returns it transfers control to sysstop(). (i.e. set-up the stack so that thespot 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 thefunction address passed in as the argument to syscreate(). Now each time a process is createdthe 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, thewrapper process will call sysstop(). For this approach to work, when the wrapper process4is created the stack will have to be constructed such that when the wrapper process runs it canretrieve the address of the user function to call (i.e. run). That means the arguments will have tobe placed in the appropriate place of this initial stack. It should be noted that with both of theseapproaches no assembly language code is required. You may choose either approach or developsomething of your own.3.3 Semaphore SubsystemThis section describes a semaphore system for our Xeros kernel. In a general purpose semaphoresystem there are normally calls to create and destroy semaphores. In this system that will not bethe case. The kernel will initially create and initialize two semaphores identified by the integervalues 0 and 1. At the kernel implementation level, each semaphore has associated with it aninteger value and a queue of processes blocked and waiting for that semaphore. The initial valueof the integer associated With a semaphore is 0. This integer is called the semaphore value. Thesemaphore behaviour is as follows: Processes wanting to acquire a semaphore use the sysP() call. If the semaphore value is0 the process is blocked on this semaphore. If the semaphore value is greater than 0. Thesemaphore 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 notblocked. When sysV() is called, if there are processes blocked on the semaphore, the highestpriority process is unblocked and the semaphore value remains unchanged. If more than oneprocess of the same priority is waiting for a semaphore the first one makeing the sysP() is toget the sempahore. If there are no processes blocked on the semaphore the semaphore valueis 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 acquiredsemaphore, but that is not a requirement. This implies that the sysV() call does not need to bemade by the process acquiring a semaphore. (Observe that some process without the semaphorewill 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 bymaking extra sysV()) calls.3.3.1 The sysP() and sysV() CallsTo 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 twosemaphores the sysP() operation applies to. If the parameter is invalid 0 is returned otherwise 1is 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);5This function returns 1 on success and 0 on failure. The argument identifies which of the twosemaphores the sysV() operation applies to. If the parameter is invalid, 0 is returned otherwise 1is returned. If, when the call is made, there are processes blocked on the semaphore the highestpriority process is unblocked (if there are multiple processes of the same priority that can beunblocked the one that called sysP() first is to be selected). If no processes are waiting on thesemaphore, the value is simply incremented. The process calling sysV()is not blocked.3.4 Pre-emptionIn order to pre-empt a process the kernel must get control of the processor. Since the currentlyrunning process implicitly has control of the CPU, a hardware timer interrupt is used to transfercontrol to the kernel on a regular basis. In order to make our kernel pre-emptive, four steps need tobe performed. First the context switcher needs to be modified to handle both the hardware timerinterrupt, and the software system call interrupt; this is outlined in Figure 1. This figure is a broadoutline of the Processing and does not identify precisely what needs to be done and how.ContextSwitcherpush kernel state onto the kernel stacksave kernel stack pointerswitch to process stacksave return value of system callpop process state from the process stackirettimer entry point:disable interruptspush process state onto process stacksave some sort of indication that this is a timer interruptjump to common entry pointsyscall entry point:disable interruptspush process state onto process stacksave some sort of indication that this is system callcommon entry point:save Process stack pointerswitch to kernel stackpop kernel state from kernel stackrecover entry point type to determine return type.return from context switcherFigure 1: The new context switcher.Immediately after an interrupt occurs, the interrupts need to be disabled since we are notbuilding 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 isnt done automatically.6Note 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 cliinstruction does this. It is not necessary to re-enable interrupts before the iret is performedbecause 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. Itturns out that if you dont do the cli there is about a 5 instruction window where problems couldoccur if a hardware interrupt goes off. (Think about why the window is so small or what wouldcause 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 easilydistinguish between a system call trap and a hardware interrupt, like the timer, by having differentISRs. Ideally we want to reuse as much code as possible between the hardware interrupt and systemcall trap processing code. A hardware interrupt, unlike an exception used for a system call, requiresthat ALL registers contain what they had before the interrupt so special care needs to be taken.Although which registers can be clobbered during the kernels processing of a system call isdesign specific, it is the case that the return value of the system call will be in register eax. If thecontext switcher returns the value of a system call in eax, and the same code is used to return froman interrupt (which should be the case) then the return value of a hardware interrupt needs to bethe value of eax when the interrupt occurred.To have hardware interrupts fit in with our context switch model, one approach is to make ahardware interrupt appear like a system call. To do this the context switcher needs to return anindication to the dispatcher that a timer interrupt occurred. It is recommended that you define aTIMER INT request identifier along with all the other system call request identifiers that a dispatchercan 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 samething as the YIELD request: place the current process at the end of the ready queue, de-queue thenext process in the ready queue, and run it. In the next section you will have to add an additionalline of code to this request handler, so dont 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 willprevent 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 timeris on IRQ0 which translates to interrupt number 32. Make sure the handler is the timer entrypoint in the context switcher and not the syscall entry point. You will also have to initialize thetimer 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 triggerthe interrupt. For example, specifying a value of 100 will mean that the interrupt will be triggeredevery 100th of a second (every 10 milliseconds). Thus, a process will be given a time slice of 10milliseconds, before Being pre-empted. This is the recommended time slice for the system. Thus,after the call to set evec() you should addinitPIT( 100 );When a timer interrupt occurs, the hardware has to be re-armed in order for the interruptto occur again. This is done by signalling an end of interrupt (EOI). To signal an EOI use the7provided function end of intr(). This function should be called, probably from dispatch() asthe last operation in the servicing of the TIMER INT request. You will notice very quickly if youforget to do this.3.4.1 PrioritiesIn 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 apriority. You are not to add kernel support to avoid CPU starvation (i.e. priorities are not adjustedby the kernel based on how much CPU time a process has received) or to deal with the priorityinversion problem. If you are using the supplied kernel, observe that the code to manage the readyqueue is in disp.c and that there is a single queue. Consequently, you will need to modify the queuemanagement 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 ProcessSince processes might become blocked for one reason or another, such as waiting to acquire asemaphore or a timer to expire, among other things. Consequently it is important to ensure thatthere is at least one ready process available at all times. As you know, bad things happen if thekernel 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 dispatcherso that the idle process will run only if no other process is available. Instead of just having theidle process execute an infinite loop with an empty body, you might want to try executing the hltinstruction in the body of the loop. (You dont have to use hlt, it is just something you can try ifyou like.)The prototype for the process should beextern void idleproc( void );and it should be created by initproc(). You should start with a simple idle process before tryingto use hlt, if you Choose to try hlt. If you ever schedule the idle process, and dont have the timerinterrupt working, control will never return to the kernel.3.6 Sleep DeviceThe sleep device will allow processes to sleep for a requested number of milliseconds. First, adda system call syssleep() to syscall.c that takes one unsigned int parameter and returns anunsigned int. The single parameter is the number of milliseconds the process wishes to sleep. Forexample, to sleep for a second the call would be syssleep(1000); The prototype for the calls isextern unsigned int syssleep( unsigned int milliseconds );and should be added to xeroskernel.h. The return value for syssleep() is 0 if the call wasblocked for the amount of time requested otherwise it is the amount of time the process still hadto sleep at the time it was unblocked. In this assignment there is no mechanism to unblock theprocess early, But in assignment 3 there will be. So, at this point one would always expect to getback 0, although in A3 that wont be the case.8Modify the dispatcher appropriately to recognize the system call, and have it call the correspondingkernel sleep() function that you will write. To the TIMER INT request service code adda call to a function called tick(). This function will also be written by you and it notifies thesleep device code that a clock tick has occurred. Since Bochs is an emulator, it is sometimes thecase that the machine the emulator is running on can be emulated faster than the original machineactually ran. As a result, time will pass faster on these machines than in real or wall clocktime. An attempt has been made to minimize this problem through configuration options in thebochsrc file in the xeros directory, but dont be overly concerned if things do not match wall clocktime.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 suchthat its place in the list corresponds to when it needs to be woken. Observe that the clock tick hasa certain granularity And that the parameter to syssleep() has a finer granularity than a clocktick. To deal with this problem the kernel will treat the value of the parameter to syssleep() as theminimum amount of time to sleep for and wake a process on the next clock tick after this minimumamount of time has elapsed. To simplify the managing of the times and the sleep queue it wouldbe a good idea to convert, within the kernel, the amount of time to sleep into clock ticks (timeslices) 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 threeprocesses in the sleep list, that need to be woken after 5, 7, and 8 time slices respectively, and thecurrent 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 isNOT to be placed on the ready queue until it is woken. After the sleep() call completes, thedispatcher selects the next process in the ready queue to run. Dont confuse the behaviour of thekernel sleep() function with that of syssleep(). The sleep() function always returns to thedispatcher, even though a process is being blocked but the sysleep() call wont return to theapplication until at least the specified time has elapsed.The tick() kernel function Notifies the sleep device that another time slice has occurred. Thefunction should wake up any processes that need to be woken up by placing them on the readyqueue associated with their priority, marking them as ready, and updating internal counters.3.7 Some Testing – Demonstrating Semaphores and PrioritiesAt this point you should have a pre-emptive multitasking kernel and you should have extensivelytested it. To demononstrate some of the systems functionality implement processes with thefollowing 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 aprocess and what that processs 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 bothsemaphores. 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 its 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 Processxxx where xxx is the process ID of the process before acutualling printing the message specifiedabove. The times are to be the actual values provided as a parameter to the sleep system call. (i.ethe times you specify to sleep should be the actual ones that would be used if the timer on theemulator accurately captured wall clock elapsed time. You do not have to try to select sleep valuesthat result in the process actually sleeping that amount of time according to the wall clock. )104 Write-upYour write-up is to be a well organized, typed document containing testing and assignment questionssections as described in the next sections.4.1 Testing DocumentationYour testing documentation is to a plain text ASCII file with the name Testing.txt. A file with thisname has been provided for you.You are to handin test output for the 6 test scenarios outlined below. Each test scenario is tobe 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 Organiz”
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
