Operating System代写：CS162 Threads

代写多线程程序，作业一共分为三个Task，需要对现有的程序进行性能优化。

Your task

In this project, you will add features to the threading system of the educational operating system Pintos. We will introduce these features briefly and provide more details in the reference material at the end of this document.

Task 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). */
 * 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. Your task is to re-implement timer_sleep() so that it executes efficiently without any “busy waiting”.

Task 2: 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.

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. The purpose of priority donation is to solve the priority inversion problem. For example, a scheduler that did not donate priorities would choose medium-priority threads instead of B. However, we want B to run first, so we can unblock A. 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(int new_priority) and get its own priority by calling thread_get_priority().

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.

Task 3: Multi-level Feedback Queue Scheduler (MLFQS)

In addition to the priority scheduler algorithm, you must implement a multi-level feedback queue scheduler algorithm, which is explained in detail in the reference material. The scheduler will either use the priority scheduling algorithm or the MLFQS algorithm, depending on the value of the variable “bool thread_mlfqs” (found in thread.c). This variable is toggled with –mlfqs command-line option to Pintos.

Design Document Guidelines

For each of the 3 tasks of this project, you must explain the following 4 aspects of your proposed design. We suggest you create a section for each of the 3 project parts. Then, create subsections for each of these 4 aspects.

1. Data structures and functions - Write down any struct definitions, global (or static) variables, typedefs, or enumerations that you will be adding or modifying (if it already exists). These definitions should be written with the C programming language, not with pseudocode. Include a brief explanation the purpose of each modification. Your explanations should be as concise as possible. Leave the full explanation to the following sections.

2. Algorithms - This is where you tell us how your code will work. Your description should be at a level below the high level description of requirements given in the assignment. We have read the project spec too, so it is unnecessary to repeat or rephrase what is stated here. 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. Instead, you should try to convince us that your design satisfies all the requirements, including any uncommon edge cases.
   The length of this section depends on the complexity of the task and the complexity of your design. Simple explanations are preferred, but if your explanation is vague or does not provide enough details, you will be penalized. Here are some tips:

   • For complex tasks, like the priority scheduler, we recommend that you split the task into parts. Describe your algorithm for each part in a separate section. Start with the simplest component and build up your design, one piece at a time. For example, your algorithms section for the Priority Scheduler could have sections for:
     • Choosing the next thread to run
     • Acquiring a Lock
     • Releasing a Lock
     • Computing the effective priority
     • Priority scheduling for semaphores and locks
     • Priority scheduling for condition variables
     • Changing thread’s priority
   • Use backticks around variable names and function names. Use bold, italics, and other Markdown styles to improve the readability of your design document.
   • Lists can make your explanation more readable. If your paragraphs seem to lack coherency, consider using a list.
   • A good length for this section could be 1 paragraph for a simple task (Alarm Clock) or 2 screen pages for a complex task (Priority Scheduler). Make sure your explanation covers all of the required features.
   • We fully expect you to read a lot of Pintos code to prepare for the design document. You won’t be able to write a good description of your algorithms if you don’t know any specifics about Pintos.
3. Synchronization - Describe your strategy for preventing race conditions and convince us that it works in all cases. Here are some tips for writing this section:
   • This section should be structured as a list of all potential concurrent accesses to shared resources. For each case, you should prove that your synchronization design ensures correct behavior.
   • An operating system kernel is a complex, multithreaded program, in which synchronizing multiple threads can be difficult. The best synchronization strategies are simple and easily verifiable, which leaves little room for mistakes. If your synchronization strategy is difficult to explain, consider how you could simplify it.
   • You should also aim to make your synchronization as efficient as possible, in terms of time and memory.
   • Synchronization issues revolve around shared data. A good strategy for reasoning about synchronization is to identify which pieces of data are accessed by multiple independent actors (whether they are threads or interrupt handlers). Then, prove that the shared data always remains consistent.
   • Lists are a common cause of synchronization issues. Lists in Pintos are not thread-safe.
   • 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.
   • 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.
4. 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.