Project 2: Threads
Due: April 2, 2022
1 Introduction 3
1.1 Setup …………………………………………. 3
Copyright By PowCoder代写 加微信 powcoder
2.1 EfficientAlarmClock …………………………………. 4 2.2 StrictPriorityScheduler………………………………… 4 2.3 UserThreads……………………………………… 4 2.4 ConceptCheck …………………………………….. 5 2.5 Testing ………………………………………… 6
3 Deliverables 7
3.1 Design…………………………………………. 7 3.1.1 Document……………………………………. 7 3.1.2 Review …………………………………….. 8 3.1.3 Grading…………………………………….. 8
3.2 Code………………………………………….. 8 3.2.1 Checkpoints…………………………………… 8 3.2.2 Testing …………………………………….. 8 3.2.3 Quality …………………………………….. 8
3.3 Report…………………………………………. 9
3.4 Evaluations………………………………………. 9
3.5 Submission ………………………………………. 10
3.6 Grading………………………………………… 10
4.1 Checkpoint1 ……………………………………… 11 4.2 Checkpoint2 ……………………………………… 11 4.3 Final………………………………………….. 11
5.1 EfficientAlarmClock …………………………………. 13 5.2 StrictPriorityScheduler………………………………… 13
A Threads 14
A.1 UnderstandingThreads ………………………………… 14 A.2 TheThreadStruct…………………………………… 14 A.3 ThreadFunctions……………………………………. 16
B Scheduler
C User Threads
CS 162 Spring 2022 Project 2 Threads
C.1 ImplementationRequirements……………………………… 18 C.2 Synchronization…………………………………….. 19 C.3 AdditionalInformation…………………………………. 19
D Pthread Library 21
D.1 Threading……………………………………….. 21 D.2 User-LevelSynchronization ………………………………. 22
E Synchronization 24
E.1 DisablingInterrupts ………………………………….. 24 E.2 Semaphores………………………………………. 25 E.3 Locks …………………………………………. 25 E.4 Monitors………………………………………… 26 E.5 OptimizationBarriers …………………………………. 27
F Advice 29
F.1 GroupWork………………………………………. 29 F.1.1 Meetings ……………………………………. 29
F.2 Development ……………………………………… 29 F.2.1 CompilerWarnings……………………………….. 29 F.2.2 FasterCompilation……………………………….. 30 F.2.3 RepeatedCommands………………………………. 30 F.2.4 HailMary……………………………………. 30
CS 162 Spring 2022 Project 2 Threads
1 Introduction
Welcome to Project Threads! In this project, you will add features to the threading system of Pintos.
In Project User Programs, each thread that you dealt with (except the init and idle threads) was also a process, with its own address space, data backed by an executable file, and ability to execute in userspace. Importantly, each thread that was also a userspace process was the only thread in that process; multithreaded user programs were not supported. This project, you will be overcoming this limitation by adding support for multithreaded user programs. Moreover, you will be implementing an efficient alarm clock and strict priority scheduler. However, for simplicity, you will implement these features only for kernel threads – threads that only execute in the kernel mode and have no userspace component.
First, log into your VM. You should already have your Pintos code from Project User Programs, which you will be building off of. We recommend that you tag your final Project User Programs code since you will probably build off of it for Project File Systems.
If you are using the staff solution for Project User Programs (check Piazza for more information), you will need to reset your repo.
Then, you can apply the given patch p1.diff. Make sure p1.diff is in /code/group. > patch -p4 -i p1.diff
For this project, group0 has been updated to include important functions to implement for multi-threading. Please merge the starter code before starting Project 2 using git pull staff master. Because of this update, you will likely get merge conflicts in process.c and process.h. Please resolve the merge conflicts. [This guide1 may be helpful. It will also be helpful to take a look at what is being updated.]
> cd ~/code/group
> git tag proj-userprog-completed
> git push group master –tags
> git fetch staff master
> rm -rf src/
> git checkout staff/master — src
> git commit -m “Reset to skeleton code before applying diff”
> git pull staff master
> git push group master
1 https://docs.github.com/en/pull- requests/collaborating- with- pull- requests/addressing- merge- conflicts/ resolving- a- merge- conflict- using- the- command- line
CS 162 Spring 2022 Project 2 Threads
2.1 Efficient Alarm Clock
In Pintos, threads may call this function to put themselves to sleep:
* This function suspends execution of the calling thread until time has
* advanced by at least x timer ticks. Unless the system is otherwise idle, the
* thread need not wake up after exactly x ticks. Just put it on the ready queue
* after they have waited for the right number of ticks. The argument to
* timer_sleep() is expressed in timer ticks, not in milliseconds or any another * unit. There are TIMER_FREQ timer ticks per second, where TIMER_FREQ is a
* constant defined in devices/timer.h (spoiler: it’s 100 ticks per second).
void timer_sleep (int64_t ticks);
timer sleep is useful for threads that operate in real-time (e.g. for blinking the cursor once per second). The current implementation of timer sleep is inefficient, because it calls thread yield in a loop until enough time has passed. This consumes CPU cycles while the thread is waiting. Your task is to reimplement timer sleep so that it executes efficiently without any busy waiting.
2.2 Strict Priority Scheduler
In Pintos, each thread has a priority value ranging from 0 (PRI MIN) to 63 (PRI MAX). However, the current scheduler does not respect these priority values. You must modify the scheduler so that higher-priority threads always run before lower-priority threads (i.e. strict priority scheduling).
You must also modify the 3 Pintos synchronization primitives (lock, semaphore, condition variable), so that these shared resources prefer higher-priority threads over lower-priority threads.
Additionally, you must implement priority donation for Pintos locks. When a high-priority thread (A) has to wait to acquire a lock, which is already held by a lower-priority thread (B), we temporarily raise B’s priority to A’s priority. A scheduler that does not donate priorities is prone to the problem of priority inversion whereby a medium-priority thread runs while a high-priority thread (A) waits on a resource held by a low-priority thread (B). A scheduler that supports priority donation would allow B to run first, so that A, which has the highest priority, can be unblocked. Your implementation of priority donation must handle 1) donations from multiple sources, 2) undoing donations when a lock is released, and 3) nested/recursive donation.
A thread may set its own priority by calling thread set priority and get its own priority by calling thread get prioirty.
If a thread no longer has the highest “effective priority” (it called thread set priority with a low value or it released a lock), it must immediately yield the CPU to the highest-priority thread.
2.3 User Threads
Pintos is a multithreaded kernel (i.e. there can be more than one thread running in the kernel). While working on Project User Programs, you have no doubt worked with the threading interface in the kernel. In threads/thread.c, thread create allows us to create a new kernel thread that runs a specific kernel task. Analogously, the thread exit function allows a thread to kill itself. You should read and understand the kernel threading model.
On the other hand, as it were in Project User Programs, each user process only had one thread of control. In other words, it is impossible for a user program to create a new thread to run another user function. There was no analog of thread create and thread exit for user programs. In a real system, user programs can indeed create their own threads. We saw this via the POSIX pthread library.
CS 162 Spring 2022 Project 2 Threads
For this task, you will need to implement a simplified version of the pthread library in lib/user/pthread.h. User programs would be allowed to create their own threads using the functions pthread create and pthread exit. Threads can also wait on other threads with the pthread join function, which is simi- lar to the wait syscall for processes. Threads should be able to learn their thread IDs (TIDs) through a new get tid syscall. You must also account for how the syscalls in Project User Programs are affected by making user programs multithreaded.
In Project User Programs, whenever a user program (which consisted of just a single thread) trapped into the OS, it ran in its own dedicated kernel thread. In other words, user threads had a 1-1 mapping with kernel threads. For this task, you will need to maintain this 1-1 mapping. That is, a user process with n user threads should be paired 1-1 with n kernel threads, and each user thread should run in its dedicated kernel thread when it traps into the OS. You should not implement green threads2, which have a many-to-one mapping between user threads and kernel threads. Green threads are not ideal, because as soon as one user thread blocks, e.g. on IO, all of the user threads are also blocked.
In addition, you must also implement user-level synchronization. After all, threads are not all that useful if we can’t synchronize them properly with locks and semaphores. You will be required to implement lock init, lock acquire, lock release, sema init, sema down, and sema up for user programs.
2.4 Concept Check
The following are conceptual questions meant to be answered in your design document. You won’t need to write any code for these questions, but you may need to read and reference some.
1. When a kernel thread in Pintos calls thread exit, when and where is the page containing its stack and TCB (i.e. struct thread) freed? Why can’t we just free this memory by calling palloc free page inside the thread exit function?
2. When the thread tick function is called by the timer interrupt handler, in which stack does it execute?
3. Suppose there are two kernel threads in the system, thread A running functionA and thread B running
functionB. Give a scheduler ordering in which the following code can lead to deadlock.
struct lock lockA; // Global lock
struct lock lockB; // Global lock
void functionA() {
lock_acquire(&lockA);
lock_acquire(&lockB);
lock_release(&lockB);
lock_release(&lockA);
void functionB() {
lock_acquire(&lockB);
lock_acquire(&lockA);
lock_release(&lockA);
lock_release(&lockB);
4. Consider the following scenario: there are two kernel threads in the system, Thread A and Thread B. Thread A is running in the kernel, which means Thread B must be on the ready queue, waiting patiently in threads/switch.S. Currently in Pintos, threads cannot forcibly kill each other. However, suppose that Thread A decides to kill Thread B by taking it off the ready queue and freeing its thread stack. This will prevent Thread B from running, but what issues could arise later from this action?
2 https://en.wikipedia.org/wiki/Green_threads
CS 162 Spring 2022 Project 2 Threads
5. Consider a fully-functional and correct implementation of this project, except for a single bug, which exists in the kernel’s sema up function. According to the project requirements, semaphores (and other synchronization variables) must prefer higher-priority threads over lower-priority threads. However, the implementation chooses the highest-priority thread based on the base priority rather than the effective priority. Essentially, priority donations are not taken into account when the semaphore decides which thread to unblock. Please design a test case that can prove the existence of this bug. Pintos test cases contain regular kernel-level code (variables, function calls, if statements, etc) and can print out text. We can compare the expected output with the actual output. If they do not match, then it proves that the implementation contains a bug. You should provide a description of how the test works, as well as the expected output and the actual output.
2.5 Testing
Pintos already contains a test suite for Project User Programs, but not all of the parts of this project have complete test coverage. You must submit one new test case which exercise functionality that is not covered by existing tests. We will not tell you what features to write tests for, so you will be responsible for identifying which features of this project would benefit most from additional tests. Make sure your own project implementation passes the tests that you write. You can pick any appropriate name for your test, but beware that test names should be no longer than 14 characters.
CS 162 Spring 2022 Project 2 Threads
3 Deliverables 3.1 Design
Before you start writing any code for your project, you need to create an design plan for each feature and convince yourself that your design is correct. You must submit a design document and attend a design review with your TA. This will help you solidify your understanding of the project and have a solid attack plan before tackling a large codebase.
3.1.1 Document
Like any techinical writing, your design document needs to be clean and well formatted. We’ve provided you with a template linked on the website that you must use. The template can be found on the website. We use Dropbox Paper3 which supports real-time collaboration like Google Docs with the added benefit of techincal writing support (e.g. code blocks, LaTeX). Not using this template or failure to use code formatting will result in losing points. The main goal of this is not to punish you for this but rather make it easy for TAs to read.
To get started, navigate to the template and click the “Create doc” button on the top right hand corner. You can share this doc with other group members to collaborate on it. Make sure to click the blue “Share” button in your document, not the template.
For each task except for Concept Check, you must explain the following aspects of your proposed design. We suggest you create a section for each task which has subsections for each of the following aspects.
Data Structures and Functions
List any struct definitions, global or static variables, typedefs, or enumerations that you will be adding or modifying (if it already exists). These should be written with C not pseudocode. Include a brief explanation (i.e. a one line comment) of the purpose of each modification. A more in depth explanation should be left for the following sections.
Algorithms
Tell us how you plan on writing the necessary code. Your description should be at a level below the high level description of requirements given in the assignment. Do not repeat anything that is already stated on the spec.
On the other hand, your description should be at a level above the code itself. Don’t give a line-by-line run- down of what code you plan to write. You may use small snippets of pseudocode or C in places you deem appropriate. Instead, you need to convince us that your design satisfies all the requirements, especially any edge cases. We expect you to have read through the Pintos source code when preparing your design document, and your design document should refer to the appropriate parts of the Pintos source code when necessary to clarify your implementation.
Synchronization
List all resources that are shared across threads and processes. For each resource, explain how the it is accessed (e.g. from an interrupt context) and describe your strategy to ensure it is shared and modified safely (i.e. no race conditions, deadlocks).
In general, the best synchronization strategies are simple and easily verifiable. If your synchronization strategy is difficult to explain, this is a good indication that you should simplify your strategy. Discuss the time and memory costs of your synchronization approach, and whether your strategy will significantly limit the concurrency of the kernel and/or user processes/threads. When discussing the concurrency allowed by your approach, explain how frequently threads will contend on the shared resources, and any limits on the number of threads that can enter independent critical sections at a single time. You should aim to avoid locking strategies that are overly coarse.
3 http://paper.dropbox.com/
CS 162 Spring 2022 Project 2 Threads
Interrupt handlers cannot acquire locks. If you need to access a synchronized variable from an interrupt handler, consider disabling interrupts. Locks do not prevent a thread from being preempted. Threads can be interrupted during a critical section. Locks only guarantee that the critical section is only entered by one thread at a time.
Do not forget to consider memory deallocation as a synchronization issue. If you want to use pointers to struct thread, then you need to prove those threads can’t exit and be deallocated while you’re using them.
If you create new functions, you should consider whether the function could be called in 2 threads at the same time. If your function access any global or static variables, you need to show that there are no synchronization issues.
Rationale Tell us why your design is better than the alternatives that you considered, or point out any shortcomings it may have. You should think about whether your design is easy to conceptualize, how much coding it will require, the time/space complexity of your algorithms, and how easy/difficult it would be to extend your design to accommodate additional features.
3.1.2 Review
After you submit your design doc, you will schedule a design review with your TA. A calendar signup link will be posted sometime before the design doc due date. During the design review, your TA will ask you questions about your design for the project. You should be prepared to defend your design and answer any clarifying questions your TA may have about your design document. The design review is also a good opportunity to get to know your TA for participation points.
3.1.3 Grading
The design document and design review will be graded together. Your score will reflect how convincing your design is, based on your explanation in your design document and your answers during the design review. If you cannot make a design review, please contact your TA to work out an arrangement. An unexcused absence from a design review will result in a 0 for the design portion.
Code will be submitted to GitHub via your groupX repo. Pintos comes with a test suite that you can run locally on your VM. We will run the same tests on the autograder, meaning there are no hidden tests. As a result, we recommend you test locally as much as possible since the autograder’s bandwidth is limited.
3.2.1 Checkpoints
On the autograder, we will provide checkpoints for you to stay on pace with the project. Checkpoints will not be graded and have no effect on your grade. However, we still encourage students to keep up with the checkpoints See Plan for more details on the specific checkpoints for this project.
Each checkpoint will have a corresponding autograder. Checkp
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com