CST 334 - Week 5

Concurrency

This week we entered the realm of multithreaded programs. Each process can be split up into threads, which execute inside the same address space as the process. Every thread gets its own stack so that its execution state can be independent of the other threads, and it also gets its own thread control block and thread id. The parent process runs on its own thread, called the main thread. The purpose of multithreading is to take advantage of parallelism, which allows a process to split a task up into different pieces and run them all at the same time (ideally simultaneously on multiple CPUs). 

One of the biggest issues with threads is concurrent access to shared code. For instance, if multiple threads are all accessing the same data structure, their operations may clash and the results can be indeterminate. In the case of a counter, multiple threads updating/reading the counter variable will certainly not end well. To solve this issue, the concept of locking is used. Before entering a critical section (shared code), a thread must obtain a lock. If another thread has the lock, the thread must wait. One way for a thread to wait is to enter a spin (spin-wait), but that can be wasteful. A better method is for the thread to sleep while waiting for a signal from another thread to wake up (at which point the lock would be obtained). 

CST 334 - Week 4

Memory Virtualization (Part 2)

This week we covered part 2 of memory virtualization. The primary takeaway dealt with a process called paging. Unlike segmentation, where chunks of memory can be various sizes, paging splits the memory up into equal-sized chunks called pages. Pages typically are small, usually 4kB (2^12 bytes) in size. Having memory sliced up into same-sized chunks eliminates external fragmentation, but internal fragmentation can still exist. The techniques of segmentation and paging can be combined.

The memory management unit contains a cache called the TLB, or translation lookaside buffer. This unit is essentially a map which translates virtual pages to physical pages. Since it is a physical cache near the CPU, it is not very large. It only contains mappings for the most recently accessed pages. If the CPU cannot find a page mapping in the TLB, a TLB miss occurs. When that happens, the TLB accesses the page table (via a pointer stored in a register), which is essentially a master map of all virtual to physical pages. The TLB loads itself with the mapping info and retries the original instruction, resulting in a TLB hit (and successful mapping). 

Of course, it is possible that a requested physical page is not located in memory, but rather in the disk's swap space, and a page fault (or miss) will occur. In that case, the TLB will raise an exception so that the operating system can address the page fault. There is often a background page daemon that automatically writes old pages to the disk (according to the system's page replacement policy) so that there are always physical pages available during page swapping.

CST 334 - Week 3

Memory Virtualization

This week we went a bit further into memory virtualization. Each running process has a private copy of memory that only it can access. However, the memory addresses available for each process are exactly the same. How is that possible? Through the memory management unit (MMU), a piece of hardware that helps the operating system translate virtual addresses into physical addresses. Each process is granted a slice* of physical memory, which is calculated by adding its virtual address to a base value that is unique to the process. For example, if a process is trying to write to virtual address 100, and it has been assigned base address 13000, then the operating system would actually write to address 13000+100 (base+offset) = 13100. 

An additional value, called the limit, marks the boundary of each process's address space. This ensures no process enters another process's physical address space. Operating systems keep track of free spaces in physical memory using a free list, but external fragmentation is bound to happen due to holes in between processes that are too small to be reallocated. For example, a process may require 20KB of memory, and the system may actually have enough, but if it's split up into small parts then the process can't fit into it. One potential solution is compaction, which repositions processes so that they are in succession. External fragmentation can be minimized by using an algorithm called worst-fit allocation, which places new processes in the largest available memory gap.

* Each process can actually be granted many slices of memory. This is called segmentation and is a commonly implemented memory management technique. Since the memory granted to each process is implicitly split into discrete segments (i.e. stack, heap, data, code), segmentation explicitly separates these structures in the memory. The reason for this is to prevent waste from sparse address spaces. Without segmentation, the heap and stack are connected by a contiguous block of memory and grow towards each other. If too much memory is allocated for the process, there can be a lot of unused memory between the stack and heap. This is known as internal fragmentation. Since it is not reachable by other processes, it goes to waste. Segmentation allows processes to be allocated varying amounts of memory (just the amount needed). As a side note, whether a system has segmentation or not, illegal memory access exceptions are usually called segmentation faults.

CST 334 - Week 2

Processes

This week was all about processes (running programs). Programs are just files on a disk and don't actually do anything until they are executed. When that occurs, the operating system allocates memory for the program and loads up its source code and static data (if any exists). The allocated memory must be enough to include not only the program and its data, but also the program's stack and heap. The combination of all these discrete memory locations is called a process. 

A process encapsulates a program and allows it to run securely by isolating its address space from other processes. The process does not know that it is trapped in a bubble and believes that it has full access to system resources. In reality, its reach is limited (which it will discover if it attempts to access a memory location outside of its designated range). Since the operating system has virtualized everything, the process doesn't even know the true size of the memory or that other processes are using the CPU. 

Zombies!

In Unix-like environments, processes can spawn new processes with fork(), which requires a subsequent call to exec() to do anything useful. The way that the fork/exec system works is strange but allows for the running of code in between the forking of a process and the execution of a new program. I also learned that the parent process must call wait() at some point to check if the child process has finished, otherwise a zombie process can exist and waste system resources. 

When a child process terminates, an entry is maintained in its parent's process list until the parent realizes it has finished (through the wait system call). Until that time, the operating system will keep allocating resources for it, hence the term zombie: the process appears to be running but nothing is actually processing. I am not sure why child processes do not notify their parents automatically. It's worth noting here that if a parent process terminates before its children, the child processes will become orphaned and adopted by the init system process.

Scheduling

Finally I want to talk a bit about scheduling. This topic has fascinated me since my data structures and algorithms class. When we were discussing circularly linked lists, my professor briefly described round-robin scheduling. This type of scheduling ensures that all processes in the ready queue are run on the CPU by giving them each an equal amount of execution time before rotating to the next. This week my knowledge of schedulers was expanded, and now I have better insight into some of the challenges faced by different scheduling algorithms (such as turnaround vs response times).

Multilevel queue algorithms use multiple ready queues, each with a different priority level. The individual queues use standard round-robin scheduling, but processes are able to move up or down in priority. These scheduling algorithms offer good turnaround and response times while avoiding starvation of CPU-bound processes, which may occur when a process is unable to move up from a low priority queue and receives little-to-no execution time. Note that processes may be granted a different time quantum (slice of time on the CPU) depending on their priority level.