I haven’t written a blog post for MINIX3 in some time (sorry Professor), and I figured that it would probably be wise to wrap up what I managed to complete this semester after I managed to get past all the stress I was feeling.

About halfway through the semester I started meeting weekly with my professor in order to discuss ways to approach my project. He knew I was pretty darn stressed about it, but was also pleased with how much I had learned about MINIX3 and Operating Systems in general. When we started meeting, I hadn’t done any actual programming in the scheduler, and I was still fuzzy on how the whole scheduler worked as one unit. I had also not realized this at the time, but the scheduling algorithm in the official MINIX3 Book was an older version. It doesn’t reflect the design found in this report, which describes the current scheduling algorithm (found in versions 3.3.0 and newer, I believe). This was adding to the confusion in how to approach the system, because I was getting my information on the implementation of the scheduler from both sources.

I’ve talked about this a bit in my previous blogs, but I figured I’d recap in this one now that I have a better understanding of the system. In the official MINIX3 book, the scheduler is still built into the Kernel. This meant that any scheduling changes that were to be implemented involved editing kernel code, which could end up being pretty complex in the event of errors, etc. What the scheduling report outlines is the move of the scheduler into the user mode level of MINIX’s layered design system. There still is a small default scheduler that had to be implemented, but the main scheduling policy is implemented within the user mode scheduler.

Let’s talk scheduling policies. Both the kernel-level and the user-level schedulers implement a Round Robin scheduling algorithm by default. As outlined in the report, the easiest policies to implement with the user mode scheduler are round robin, priority, staircase, and some other queue-based policies. Whilst I was googling information about implementing priority-based algorithms, I found this wonderful project done by a GitHub user named Akshita Mittel. It includes a few test files and the changes necessary to make to some of MINIX3’s files in order to implement different algorithms. It is very similar to the project I had intended on doing, so whilst I did not copy it directly (licensing and copyright issues and whatnot), I did use it as a resource for implementing my own project.

Since I wanted to deviate my project slightly from the resources I found online, instead of just implementing more than one scheduling policy, I elected to compare the default scheduling policy with a priority scheduling algorithm, and vary the number of queues by +- 25%. This left me with 3 variations of the default Round Robin policy — one with 12 queues, one with the standard 16 queues, and one with 20 queues. It also left me with 3 variants of a scheduler using a priority algorithm, again with 12, 16, and 20 queues. My goal was to run the same test across each of these 6 variations and see if there was some notable runtime difference.

Before I go into the test, I figured I’d explain the difference between Round Robin and Priority style scheduling. Round Robin policies assign each process within the priority queues a time slice, called quantum. As processes run out of quantum, they’re moved to a higher (the higher the number, the lower the priority) priority queue. In MINIX3, after a certain number of ticks, the queues are rebalanced. This means that all processes who have had their priority changed get that priority reset. The difference between round robin and priority scheduling algorithms is fairly simple — round robin policies aim to be fair, which is why they implement queue feedback. Priority policies are designed without fairness in mind. You might want some processes to always have the highest priority. Therefore, it simply disables process feedback from happening. Processes don’t move around between queues. A diagram of the structure of the priority queues are shown below.

The test I used was based on Akshita’s that I found on GitHub. The test program would log system time, do some work with a process, then log the system time again, and find the difference between the start and end times. I found the average running time for 100 tests for each of the variations. The results are displayed below.

As you can see, there wasn’t much consistency across the tests. I’m sure that, before I even ran the tests, I could have reasonably come to the conclusion that there wouldn’t have been much of a difference in run times given my particular approach. The test I ran was mostly CPU bound as opposed to I/O bound, which very well could have made a difference. I think CPU bound tests could have made a bigger impact if I had implemented a different policy than priority. On top of designing a better test for what I was doing in particular, I think that theoretically the number of queues within a round robin scheduler wouldn’t make much of a difference unless the processes existed within them for a very long period of time. Also, I think that the number of queues within a priority scheduler wouldn’t make a significant difference either, since processes tend to live where are they spawned. Aside from the crowding of the queues, I don’t see it having a large impact on the overall runtime. Therefore, I think that the results I got make sense.

I’m not upset that my small “research project” didn’t yield great results. The point of this independent study was for me to better understand operating systems, as I felt as though I was seriously lacking in that area. While I know there’s still a tremendous amount of knowledge to be gained in OS’s, I’m happy with the work I did this semester and feel far more confident when discussing OS concepts in general. It was a very stressful project at first, but now that I’ve wrapped it up, I think it was absolutely worth it. Hands-on operating system practice is a great way to go about learning the subject. In fact, this independent study has sparked quite a bit of interest in systems programming for me, and I’m looking forward to continue learning about it in the future!

(Side-note, this is my last school-related blogpost. At first, I felt extremely uncomfortable writing these things. Now, I think it’s something I’d like to do once a week, or at least regularly. I appreciate my professor requiring us to start these blogs — writing is something I never really saw myself doing enjoying, and after doing it for a couple of semesters now, I get it. Who would’ve guessed that recording what you learn is both both enjoyable and rewarding. Thanks, Professor Wurst!)

From the blog CS@Worcester – James Blash by jwblash and used with permission of the author. All other rights reserved by the author.

I’ve had to change my approach the past week or so with this independent study. When confronted with the source code, I think I began to feel overwhelmed by the amount of concepts I had to dive into. As a result, I attempted to take it from square one and relearn many systems concepts while also working on understanding the scheduler. As it turned out, this was a bit stressful for me. So I have decided to instead look at the relevant source code and, line by line, take notes learn things as they come. Perhaps this is the traditional way to handle diving into a large system of work, but since I don’t have a large amount of experience in large-scale work this is a learning process for me. It seems that this new direction is working a bit better for me.

Let’s start with /minix/servers/sched/main.c. The main() function is the primary function of the scheduler. When a message is passed into the scheduler, the main() function defines variables for the message, system call number, the caller’s number, and the result of the system call. Then, it enters an infinite loop. This loop saves the message’s info in the variables that were defined for it, and then checks for special situations such as system notifications, etc. (I’m not totally positive on the function of that, but it says that the balance_queues() function is called in this event.) Then, based on the call_nr (the system call number), a switch statement determines what call from /sched/schedule.c should be executed next, with functions like do_noquantum() (which executes when a process is out of quantum) and do_start_scheduling() (which seems to start the scheduling of the process). So long as the process is executed correctly, a reply is sent back that communicates success, and the loop continues on to the next kernel message.

So hopefully soon, I’m actually going to start tinkering with the scheduling policy and see what I can come up with. In the scheduling report I discussed in my previous post, it was suggested that with the current interface a Round Robin, Priority Scheduling, Staircase Scheduler, or Rotating Staircase Deadline algorithm can be easily implemented, so I’ll learn one of those and aim for that. I’m sure it’s going to take me longer than just a week to fully implement, but we’ll see what kind of magic I can work. I’m also sure I’m going to have to write a couple more of these research-related blog posts before I fully understand the workings and can proceed forward, but having changed my plan of attack, I’d like to finish those this week. Ready to move forward once again!

From the blog CS@Worcester – James Blash by jwblash and used with permission of the author. All other rights reserved by the author.

Before I can edit the scheduling algorithm for my independent study, I need to understand the intricacies of how it works. That’s what I tasked myself with this past week, and as it turns out, there’s a lot to know.

MINIX is structured in 4 layers. Top to bottom, they are the User Processes layer, the System Server Process layer, the Device Drivers layer, and finally the Kernel. Originally, the scheduler was built into the Kernel (like you would find on a traditional operating system, I would assume), however an independent project by Björn Patrick Swift moved the vast majority of the scheduling handling into the user space — specifically the System Server Process layer. This change allowed for a much more flexible scheduler that can be easily modified without worrying about large impactful (and potentially damaging) changes to the rest of the Kernel. On top of this, it allows for multiple user mode scheduling policies to be in place at the same time. The current user mode implementation of the scheduler is an event-driven scheduler, which largely sits idle and waits for a request from the Kernel. In order for this the happen, though, the kernel needs a scheduling implementation as well.

The Kernel scheduling implementation runs in a round-robin style, and chooses the highest priority process from a series of n priority queues. When a process in a priority queue runs out of quantum (or time left for it to be executed, which is predefined), it triggers the process’ RTS_NO_QUANTUM flag. This is what dequeues the process and marks it so it may no longer be run. The two system library routines exposed to user mode from the Kernel are sys_schedctl and sys_schedule. sys_schedctl is called by a user mode scheduler in order to take over the scheduling for a process. sys_schedule is then used by a scheduler to move the process to different priority queues or give it different quantum, based on its policy. It can also be used on currently running processes for the same functionality.

Having a minimal Kernel scheduler is important because without it some processes would run out of quantum during system startup, before the user mode scheduler has even started. Not only this, but in the event that the user mode scheduler crashes, it could be possible for the Kernel to take over scheduling until the user mode scheduler is restarted (I’m unsure if this is currently implemented or not, though). There are plenty of benefits to having a simple, inefficient Kernel implementation whilst placing the majority of the workload on user mode schedulers most of the time.

The report I linked previously that details all of the workings of the scheduler is fairly long (20 pages), so I’m going to continue reading it and taking notes on it. I don’t want each one of these blog posts to get too long and wordy, so I’ll make a few posts (all of them this coming week) on this topic, each a continuation of the last.

From the blog CS@Worcester – James Blash by jwblash and used with permission of the author. All other rights reserved by the author.

Over the past week, I found myself running head-first into a wall with MINIX. I ended up having to do lots of reading before I could even begin with development/tinkering. Having never done a project like this, I found rather quickly that the hardest part is getting started. Persistence is key, though!

In my research, I found that many resources were giving me mixed results. I saw a lot of people cross-compiling from their host machine into their VM, and I also found a lot of resources compiling from within MINIX itself. I really wanted to get a bit more experience with the feeling of low-level programming and using things like vi as an editor, even if it ends up making my life harder than necessary. So as a result, I was pretty set on the idea of compiling and rebuilding from within MINIX itself.

As it turns out, MINIX was originally designed with this type of native development in mind. From 1.0 to 3.2.1, they included the source files along with the install. In following versions, like the stable release of 3.3.0 shown on their download page, the /src directory isn’t even included within /usr. In order to obtain the source code, you need to use the git repository (also found here on Github) to clone the files. I found a section of the MINIX developer’s guide called “Tracking Current“, which explained how to go about using git within MINIX in order to track the most recent stable increments of MINIX’s development. On this page, it explains that the current stable release of 3.3.0 is not compatible with tracking current, as there have been key changes to the system since — the most recent snapshots are on version 3.4.0.

So, after a reinstall using a 3.4.0 snapshot, I finally have the source files included in my VM! I’ll start refactoring and show off what I do in following posts. I already played around a little bit by changing the startup text and rebuilding the system so it displays my name before I log in, just to make sure I actually understand how the “make build” command works. I’ll go more in depth on that subject next time. My task this coming week is to do a lot of reading through source code to understand what functions do what, and thinking about what changes I want to make exactly.

Until next time!

From the blog CS@Worcester – James Blash by jwblash and used with permission of the author. All other rights reserved by the author.