CST370: Week 4 (Week 55)

 This week we covered merge sort and though we didn't have a programming assignment I took some time to explore it. I watched some videos suggested by my classmates and did my own search to find out about some of its real world applications. I'm a fan of low level code and embedded systems so I looked at the Linux kernel. As it turns out, the list_sort algorithm in the kernel which is used to sort linked lists, is based on merge sort. One difference from other applications is that they use an iterative approach and avoid recursion. The iterative approach makes for more predictable memory usage, better constrained stack usage, and cuts down on function call overhead.

Linux 6.17 list_sort

We also had our midterm this week. The process of preparing, and in my case probably over preparing, helped make the concepts we covered more concrete in my mind. Specifically, preparing my four page note sheet. With the pace of the classes, sometimes I worry that too much of what is taught might wind up in short term memory and might not serve us when we need it. I think the process of exam prep definitely helps avoid that possibility.

CST370: Week 3 (Week 54)

 This week we covered breadth first search, depth first search, brute force and exhaustive algorithms, and divide and conquer. I was curious about real world applications of BFS and DFS and learned that BFS is useful for GPS/mapping algorithms for finding the nearest instance of some destination. For example, finding the nearest gas station or restaurant. Since it walks outward from the start location, it guarantees an optimal solution. I learned that some forms of DFS are useful for dependency mapping for software trees like the Linux kernel. They also have clever ways of parallelizing operations. Bitbake builds the Linux kernel but it does it in multiple threads without stumbling and minimizing the time that any module has to wait for another module to build. I.e. it uses the build machine's resources efficiently.

I feel like brute force algorithms may be the way most of us initially approach a problem since it's so direct. That said, I think that divide and conquer algorithms are really interesting. I'm thinking that complex problems where d&c can be applied, they can really benefit from modern computer systems where multi-threading and multiprocessing are commonplace. I look forward to exploring merge sort next week.

CST370: Week 2 (Week 53)

 This week we covered O(n) and Θ(n) notation for analyzing and comparing algorithms. We looked at recursive, non-recursive, and brute force algorithms. It is interesting to look at the speed (time complexity) of some algorithms like recursive tree traversal versus their iterative counterparts. Some time ago I auto generated a numeric file to use as an experiment. I watched the stack grow in the debugger over the course of the traversal/print program execution and it was a good way of seeing why recursion is avoided in memory constrained applications. This section was excellent in that it's a good way of helping us establish useful metrics for algorithms especially in cases where the comparison isn't intuitive or obvious.

CST370: Week 1 (Week 52)

 This  week we eased into the material by reviewing fundamental data structures like (queues, stacks, linked lists). We also reviewed trees, graphs, and weighted/unweighted maps which I think will be a foundation for what's to come in this class. We had puzzles to solve as exercises which I feel is a good way of sharpening the skills that help us break down problems algorithmically. HW0 and HW1 were relatively straight forward and remind me of programming problems that I used to use as practice when preparing for interviews. I think that in the future a lot of these types of problems will be solved by AI but I think it's incredibly valuable for us, especially as computer scientists to have a strong foundation in solving these problems by hand.

CST334: Week 8 (Week 32)

 I learned a lot this semester but I had four major take aways.

1) I got a better understanding of what's happening between the userspace applications that we usually interact with and the underlying hardware (CPU, memory, storage, etc.). We don't always think about whether we are using a character device, a block device, or a network device. We don't think about whether it's interrupt driven or if it uses polling. We don't always think about how the browser window stays active while it simultaneously streams audio or what happens when we open a file on our local disk. This class gives perspective on the aspects of computers that we don't interact with directly.

2) I saw another aspect of computing where efficient algorithms are the centerpiece. Operating systems, like AI, like networking, and different search and pattern recognition technologies are very centered on well-developed algorithms. Especially when it comes to scheduling and caching systems.  I looked up some of the problems that people have solved and some that are in active research. There is a lot of interesting work being done and this class helps form a good foundation to at least have a fundamental understanding of it.

3) I saw how important it is for multiple things to be happening in a system at once and for specialized components to be used to drive performance. Concurrency and multithreading are critical in modern computing and this class did a good job covering it. For example, PA5 could lead you to imagine what it would be like if applications blocked while waiting for I/O or network operations to complete. On the hardware side performance boosts we get from purpose-specific hardware like MMUs and DMA controllers is something else that I think about. Multiple tasks, multiple threads, multiple processing components, all working in concert.

4) I see how important it is to recognize and consider trade-offs. For example, is there a sweet spot for the size of different layers of cache? Does it depend on the targeted application? A Xeon processor in a server or Core i9 in a laptop. Is it worth the cost for additional fast cache? Additional cache, cores, memory, etc come at the price of power consumption, heat, space, and an increase in price. This class helped expand  my understanding of those trade-offs.

CST334: Week 7 (Week 31)

This week we learned about topics relating to device I/O, disks and persistent storage, file system structure and operations.

With regard to I/O devices, we covered different ways of handling data transfers between the CPU and peripherals devices. Polling(programmable) I/O involves the CPU constantly checking a device's status, i.e. polling the device. It’s simple but inefficient due to wasted CPU cycles. Interrupt-driven I/O is more efficient since devices interrupt the CPU only when they need attention. That way the CPU can work on other tasks while waiting. DMA-based I/O (Direct Memory Access) is better in most cases. It allows I/O devices to transfer data directly to and from memory without involving the CPU, minimizing CPU overhead. It requires dedicated hardware called a DMA controller.

We also covered hard drives, their basic structure, and performance implications. Hard drives are made up of spinning platters, usually in a stacked configuration. The platters have magnetic coatings for storing data. Tracks are rings on the plater that expand outward from the center. One ring inside of the other. The tracks are divided into sectors. A head moves across the platters to read or write data at commanded locations. Access time is the time it takes to retrieve data. It’s impacted by seek time, the time it takes for the head to move to the correct track. It’s also impacted by rotational delay, the time it takes for the targeted sector to rotate under the head.

Lastly, we covered the basics of files and directories. At a basic level, files and folders are just sequences of bits/bytes. Directories organize the files (and other directories) hierarchically. A superblock holds important file system information, like its size and the number of available blocks. Inodes contain metadata about files and directories (ownership, permissions, etc.) and pointers to their data blocks. Blocks are the basic unit of storage for file contents. The metadata describes files and directories, and are used for file system management and access.

CST334: Week 6 (Week 30)

This week we continued learning about concurrency. We learned about atomicity, semaphores, signaling, condition variables, and some of the pitfalls of multithreaded implementations like deadlocks, starvation, livelocks, etc.

We learned that semaphores are better suited for signaling between threads vs resource locking like mutexes. A semaphore represents an integer value but that is incremented or decremented via atomic operations. It is initialized to some integer value specified by the programmer. For example, a software interface for a device with N transmit queues may use a semaphore initialized to N. Each time a process thread successfully requests a queue, the semaphore is decremented, until it reaches 0. At that point, future requesters must wait. When a thread is done transmitting, it increments the semaphore, thus signaling waiting threads that a queue is available. The behavior seems similar to mutexes but mutexes are better suited to protecting a shared resource in a critical section than they are for signaling.

It's interesting that for semaphores and mutexes to work, the instruction set has to implement an atomic read-modify-write operation. Otherwise, the lock/unlock or increment/decrement operations may be interrupted before they complete. It just shows how specific some of the instruction set needs to be to provide the higher level features we take for granted.

We also learned how to use condition variables that allow waiting threads to be notified when a condition is met. For example, a condition variable may be used to notify thread that a buffer is empty so that it can step out of it end its wait loop and lock the buffer, before before queueing new buffer entries.

We also learned about the risks that come with multithreaded programing like deadlocks, starvation, livelock, etc. When we are dealing with a lot of shared resources and many actors contending for access it's easy to imagine how things can go wrong. Circular dependencies, ill-conceived priority + preemption algorithms, and other failings can wreak havoc. That's why we were also shown design patterns that use locks, semaphores, and condition variables in ways that help avoid some of the pitfalls.

I have a lot of respect for the researchers and engineers who devise these techniques.