CST334 Week 6 Report

 Concurrency: Part II

This week, we learned a ton more about concurrency in operating systems. Notably, the main topic was semaphores, which are essentially an upgraded version of our previous basic locks and condition variables which we can use to improve system performance, especially in multi-threading applications. Our book specifically defines a semaphore as an object with an integer value that we can manipulate with two routines, which in the posix standard are sem_wait() and sem_post(). It is important to remember that the initival value of a semaphore defines its behavior, so it must first be initialized to some value. The first type of semaphore we studied is the binary semaphore, used as a lock. Next, we learned how to implement semaphores for ordering events in a concurrent program. These semaphores can be very useful to use when a thread which is waiting for a list to become non-empty, so it can delete an element from it. Specifically, the semaphore would signal when another thread has completed, in order for the waiting thread to awaken into action, much like how condition variables work. We also learned about the producer/consumer problems and dining philosopher problems as means to understand semaphores on a deeper level. Avoiding concurrency bugs, including deadlock, was very helpful especially since we may implement semaphores ourselves in the future.

CST334 Week 5 Report

 CST334 Week 5 Journal

This week, we learned a ton about the basics of operating system concurrency. One of the most fundamental things we learned is the thread. A thread is basically a computational unit within a process. Although a single thread is semi independent, it shares a central logical address space with other threads, allowing them to access the same data. At the same time, one process can have many threads. We use threads in order to support parallelism and also to avoid blocking program progress due to slow IO. Another very important concept we learned is the lock, which is designed to help us execute a series of instructions atomically. By placing locks around critical sections in code, programmers can ensure that the section is executed as if it is a single atomic instruction. We implement locks by declaring lock variables, which hold the state of the lock (available or acquired). We evaluate the efficacy of a particular lock type by looking at several goals: mutual exclusion, fairness, and performance are the main objectives. The ticket lock has a key advantage over the spin lock in that it prevents a thread from starving, since it ensures that at some point in the future it will acquire the lock. Several data structures can be utilized in the implementation of concurrency, and we can achieve this by adding locks with performance in mind. There are concurrent counters, linked lists, queues, and hash tables, which all have pros and cons, particularly apparent when factoring scalability in. It is important to keep several things in mind though: more concurrency does not necessarily increase performance and performance problems should only be remedied once they exist. Threads can utilize a condition variable in order to bypass our problem of a thread traditionally spinning in an inefficient manner until some condition is true. In a nutshell, the thread that is waiting in the condition variable queue is signaled to by another thread to awaken and continue.

CST Week 4 Post

 CST Week 4 Summary

This week we learned a ton about how the operating system manages virtual memory, especially paging. Paging is basically an alternative to the segmentation approach when it comes to managing memory. Instead of splitting up a process' address space into some number of variable sized segments, we divide it into fixed-size units, each of which is called a page. There are numerous advantages of paging, from avoiding external fragmentation to being very flexible and enabling the spare use of virtual address spaces. 

To be blunt, we cannot simply implement paging into our system willy nilly - we have to take numerous factors into account when doing so in order to ensure good memory management. One is ensuring that we have a tranlsation-lookaside buffer, or TLB in order to cache frequently used virtual-to-physical address mappings. The main purpose of the TLB is to keep our system running quickly - we wont have to perform a full page table search for an address mapping if it is in the TLB. Another important technique for ensuring good paging function is to implement a hybrid of small and large table sizes: instead of having a single page table for the entire address space of the process, we can have one per logical segment. We may thus have three page tables, one for the code, heap and stack parts of the address space. In addition, the OS actually packs away infrequently used portions of address spaces into hard disk drives, in order to maintain a single and large address space overall. When memory is near full, the OS will also page out one or more pages to make room for the new page about to be used. The process of picking a page to kick out or replace is known as the page replacement policy, and there are several. Notably, the optimal policy, developed by Belady, decrees that it is most optimal to replace the page which will be accessed furthest in the future. The optimal is an ideal template which developers can approach through implementing their own policies, which include FIFO, random, and LRU among others.

CST334 Week 3 Report

 CST334: Weekly Learning Summary Pt. III

This week, we learned a ton in Operating Systems. We learned mostly about how the OS virtualizes memory. In essence, we are looking at how the OS utilizes hardware based address translation. The OS creates an easy to use abstraction of memory by way of the address space: this space contains all the memory state of the running program: the code, the stack, the heap, etc. Each process has not a real memory address, but rather a virtual memory address that must be translated into a real, physical memory address by the OS whenever we are creating or modifying a process.With dynamic relocation, we use a base register to transform virtual addresses into physical addresses; furthermore, a bounds register ensures that addresses are within the confines of the address space.These base and bounds registers are typically managed by a part of the CPU known as the memory management unit, or MMU. On an important note, both internal and external fragmentation are necessary evils in this address translation model, and our job as computer scientists is to try to minimize these while managing memory.