Interesting Stuff

Will be back

2011-12-31T18:22:00.003+05:30

I know I have been silent for more than a year now! Will be back with more in 2012.

kernel/proc.c - sys_call() internals

2010-11-12T09:55:00.007+05:30

I gave some idea about sys_call() in the preceding diagrams. sys_call() does a number of checks before it allows a message or notification to be passed from one process to another. These are all part of the security mechanisms in the kernel that keep processes from doing things they are not allowed to do and from corrupting each other's memory maps. Assuming that a process has just made a system call, here is the list of checks that happen:

Does the process have the privileges to make this particular system call? (the priv structure for this process in the process table is looked up to determine this)
In the case of a 'send' or 'notify', is the destination a valid process? In the case of a 'receive' is the source a valid process? Note that a caller can specify 'ANY' as its source in which case it is looking for a message or notification from any process, so this check is unnecessary for that case. 'ECHO' is also a special case where this check doesn't make sense.
Does the message pointer point to a valid region in memory i.e. is it really within the memory map limits of the calling process? Again, the memory map limits are available in the memmap struct for this process in the process table.
If the request is to 'send' to some process, is the caller allowed to send to the destination process?
Is the destination process running?
Has system shutdown started?

If all the checks above have passed then call one of the following functions: mini_notify(), mini_receive() or mini_send() depending upon the nature of the request.

Refer to the 'Message Primitives and Process States' diagrams (preceding posts) for details on what happens within the above functions.

Comments welcome.

Message Primitives and Process States - Case 3

2010-11-08T17:58:00.002+05:30

Message Primitives and Process States - Case 2

2010-11-03T21:47:00.000+05:30

Message Primitives and Process States - Case 1

2010-11-03T19:27:00.002+05:30

Process scheduling in Minix

2010-11-01T12:44:00.011+05:30

The diagram above shows the state transitions for any process in Minix. A running process can become blocked when it makes a system call (which translates into the INT assembly instruction, also known as a software interrupt). Once blocked, it has to become ready before it can be run again. The scheduling algorithm only picks ready processes for execution.

The kernel maintains 16 queues of runnable processes. These queues are numbered 0 (highest priority queue) to 15 (lowest priority queue). Different processes have different priorities and the priority of a process may change during its execution. The changed priority is reflected in the fact that the process is moved to a different scheduling queue.

The clock and system tasks in Layer 1 of Minix have the highest priority. The device drivers in Layer 2 get lower priority but they are all not equal. Server processes (process manager, file system etc.) get lower priority than device drivers. User processes get lower priority than the server processes. Refer to this post for more on these layers.

Scheduling is round robin in each queue. If a running process uses up its quantum, it is moved to the tail of its queue and given a new quantum (Transition 4 in the diagram above). When a blocked process is awakened it is put at the head of its queue if it had any part of its quantum left when it blocked (Transition 2 in the diagram above). But it does not get a new quantum. It gets only as much quantum as it was left with when it blocked.

Whenever a running process becomes blocked or a runnable or running process is killed by a signal, it is removed from the scheduling queues. What this means is that the scheduling queues contain only ready or runnable processes.

Given this structure, the rule is very simple: Find the highest priority queue that is not empty and pick and continue running the process that is at the head of that queue.

So here is the chain of events at a high level: Process A is running -> Hardware and software interrupts occur -> interrupt handling code runs -> messages or notifications are sent or received -> the message processing results in process state transitions which causes changes to the scheduling queues in the kernel -> so Process B gets selected for execution.

We have discussed in detail how context switching happens and how the scheduling logic works. It is clear that the state transitions in the above diagram really drive the context switching. But what really causes these state transitions? The answer lies in the messaging layer of Minix. That is the final missing piece of the puzzle and I will discuss it with another diagram in an upcoming post.

Comments welcome.

Minix Context Switching Detail

2010-10-23T21:21:00.015+05:30

Download and view this PDF file.

I have shown both hardware and software interrupt workflows here. Since the diagram is large and complex, it may have some errors due to oversight. Comments/corrections welcome.

Context Switching

2010-10-20T22:39:00.001+05:30

I think I now understand exactly how context switching happens in Minix. I am working on a detailed diagram which I will upload once I am done.

Minix Interrupt Handling

2010-10-17T21:30:00.003+05:30

Context Switching - The illusion of multiple processes executing simultaneously

2010-10-17T21:14:00.005+05:30

In a single processor system, at any instant, only one process is executing - be it a system process (part of the OS) or a user process. The illusion of multiple processes running simultaneously is achieved by constantly switching from process to process. Now, when does a context switch happen in minix? What causes the CPU to suspend execution of one process and resume another? There are three ways in which this can happen:

1. Hardware interrupt (one of the devices in the computer sends a signal to the interrupt controller which in turn sends an interrupt signal to the INT pin of the CPU)

2. Software interrupt (i. e. system call made by the executing process)

3. The 'quantum' of time assigned to the executing process has been used up, so this process is pre-emptively suspended and another one is picked for execution. (This is really a special case of hardware interrupt where the interrupting device is the clock.)

In upcoming posts, I will first explain interrupt processing and context switching and then give more details on scheduling of processes.

The Global Descriptor Table

2010-10-15T07:58:00.015+05:30

The GDT (Global Descriptor Table), LDTs (Local Descriptor Tables) and the IDT (Interrupt Descriptor Table) , all located in memory provide protected access to system resources. The GDT and IDT are pointed to by special registers within the CPU (so the processor can access them), and the GDT entries point both to the operating system segments and to the LDTs. The IDT contains pointers to code that needs to be executed when interrupts occur.

Each running program has its own LDT but there is a single GDT for the entire system.

The LDT describes segments local to each program including its text (code), data, stack and so on. The GDT describes system segments including the operating system itself. (Segments are independent address spaces. Segmentation is one of the techniques use to manage memory on computers. More on segments when we discuss memory management but for now just understand that with segmented memory, we need a two part address to reach any memory location - the first part is the address of the segment and the second part is the location (offset) within the segment.)

So the GDT basically points to (i.e. contains the physical addresses of) segments that contain the operating system code and data but also provides a way to get to all the LDTs in the system.

Intel 386 Processor Registers (32 bit)

2010-10-03T14:00:00.006+05:30

The Minix Startup Sequence Call Flow

2010-10-02T17:02:00.002+05:30

Privilege Levels

2010-09-29T06:54:00.006+05:30

The architecture of 32-bit Intel processors provides four privilege levels of which Minix takes advantage of three. These are defined as C macros in kernel/protect.h

#define INTR_PRIVILEGE 0 /* kernel and interrupt handlers */
#define TASK_PRIVILEGE 1 /* kernel tasks */
#define USER_PRIVILEGE 3 /* servers and user processes */

The kernel contains code that runs during interrupts and during context switches, so it always runs with INTR_PRIVILEGE. Every address in memory and every register in the CPU can be accessed by a process with this privilege level.

The System and Clock tasks run with the TASK_PRIVILEGE level which allows them to access I/O but not to use instructions that modify special registers (like those that point to descriptor tables).

Servers and user processes run at USER_PRIVILEGE level. Such processes are unable to execute certain instructions such as those that access I/O ports, change memory assignments or change privilege levels themselves.

Note that of the four layers of processes in the Minix OS, all the layers except Layer 1 run with USER_PRIVILEGE level (i.e. user mode).

Fork

2010-09-28T09:26:00.002+05:30

Just for the heck of it, I added some print statements to the code in forkexit.c in the Minix source. After recompiling, linking, creating a boot image and installing in the boot directory when I restarted the machine, all I could see was thousands and thousands of those messages I had introduced. After startup, no matter what I did the screen was littered with those messages. Which is natural since fork happens (one or more times) whenever you execute a command.

The Minix Startup Sequence Part 2

2010-09-27T13:40:00.001+05:30

The Minix Startup Sequence Part 1

2010-09-27T11:51:00.004+05:30

The Banker's Algorithm for avoiding deadlocks

2010-07-06T09:19:00.002+05:30

The Banker's Algorithm for avoiding deadlocks is about as effective as banker's hours are in the software development industry. Read it for academic interest.

Deadlocks

2010-07-01T06:48:00.004+05:30

I am back after quite a while. Time-slicing works well for processors but not for the human brain. It is better to do a few things well by spending enough time on each of them than to do a hundred things without making much progress in any.

Anyway, I am studying deadlocks right now. The formal definition (unlike most formal definitions!) is quite easy to comprehend: A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause.

But all of the conditions below should hold for a deadlock to occur:

Mutual exclusion: Each resource is either currently assigned to exactly one process or is available.
Hold and wait: Processes currently holding resources that were granted earlier can request new resources
No preemption: Resources already granted cannot be forcibly taken away from a process. (The process has to explicitly release them.)
Circular wait: There must be a circular chain of two or more processes, each of which is waiting for a resource held by the next member of the chain.

The 'directed graph' technique is used to model these conditions. All approaches that attempt to prevent deadlocks try and eliminate one or more of the above conditions.

The microkernel design of Minix

2010-01-08T07:18:00.004+05:30

In a monolithic OS, the entire OS is in a single process. But Minix has a microkernel design in which the operating system is composed of a set of processes (the kernel being just one of them) that work together by passing messages to each other. In this case it becomes necessary to distinguish between 'system calls' and 'kernel calls'. Unlike in a monolithic OS, user processes in Minix do not request services directly from the kernel. System calls from user processes result in 'messages' to the server processes (File System, Process Manager etc.). In turn, the server processes communicate with each other, the device drivers and with the kernel again using 'messages'. These messages to the kernel are really the 'kernel calls'. User processes do not have the privileges to make kernel calls.

In summary, the conventional 'system call' in Minix results in one or more 'kernel calls' which will be initiated by either the server processes or device drivers. The ipc primitives: send, receive and notify are the 'infrastructure' on top of which kernel and system calls are built. The technical term for these ipc primitives is 'traps'.

Tanenbaum gives a nice analogy to drive home the meaning of traps in Minix. The ipc primitive is like a carrier wave in a radio communications system. A send message contains some data which conveys useful information to the receiving process. It is like a modulated radio wave. The notify message conveys no information other than its origin. This is like an unmodulated radio wave (like a radio beacon that guides airplanes to an airport).

The Minix Process Table

2009-12-11T23:55:00.003+05:30

The complete state of a process is defined by the process' data in memory, plus the information in its process table slot. See picture for details.

Minix Kernel Data Structures

2009-12-10T10:43:00.004+05:30

While studing the kernel data structures, it is a pain to go back and keep referring to the source in order to visualize the inter-relationships and references among the various pieces of data. I am currently working on some diagrams that will make it easier to visualize the layout of data in the kernel. I hope to upload these diagrams this weekend.

Have been busy

2009-11-08T17:54:00.002+05:30

I have been busy for a few weeks. Work from my day job has picked up and I am short staffed. Too many night phone calls. Too many meetings. No time to do anything worthwhile. I hope to fix the staffing situation at my work place and then get back to Minix after that. It is a real bummer. I was on a roll.

The heart of Minix

2009-10-08T11:33:00.004+05:30

The 'save' assembly function in /src/kernel/mpx386.s is really the heart of the Minix OS. Discovering and understanding this function is like finding the holy grail. 'save' does some magical things. It doesn't follow any rules. It lives in its own world :-)

Coding on bare metal

2009-10-06T22:28:00.003+05:30

Went through the startup process in the Minix book again. It makes more sense now. The next section explains interrupt processing excellently. This is where we really begin to understand how the illusion of multiple processes is created.

vish is a little closer to looking normal

2009-10-01T17:20:00.004+05:30

One of the good engineers I know found out why my shell is not able to deal with commands without absolute path names. The problem was that I was using the wrong flavor of exec. Now that I am using execvp, this issue is resolved. execvp searches for the executable in the directories that are listed in the PATH env variable. Thanks Linu.

Minix Startup

2009-09-28T19:55:00.002+05:30

Just slogged through the OS startup process in The Minix Book. Could not understand some things in the first pass. I will have to re-read. In order to understand this section, I had to go back and revise assembler syntax and also how programs are laid out in memory. These topics led me to other related topics and I spent quite some time today reading all kinds of stuff. Ultimately I 'unwound the stack' and came back to The Minix Book but I am still not satisfied. I find the kernel initialization process quite tough to grasp. I have to keep reminding myself that since the system is not yet fully initialized, concepts like files and processes don't even exist. All we have is a processor with registers, memory and kernel data structures. It is getting really steep here. But this is probably the most important part of this book. I have to keep my focus and keep working through it.

Made some improvements to vish

2009-09-16T17:13:00.002+05:30

I had forgotten to handle the possibility of no user input i.e. the user just pressing enter at the vish prompt. I took care of that today. I also found an issue that was being caused by not setting a pointer to NULL after freeing it. (The pointer variable was being reused in a loop.)

Finally, I had to make a minor change in order to account for some of the quirks in the behaviour of strtok().

I think vish is a lot more robust now. But it still does not handle cd, pwd, input and output redirection etc. Will get around to it later as I need to spend time studying the Minix kernel source.

vish is alive and kicking butt!

2009-08-30T05:27:00.004+05:30

vish works great! Feels good. The data corruption had nothing to do with fork(). It was happening because I was trying to hold on to some data on the stack! I must be getting old. Need to work the pipe facility and possibly wildcards into this new shell.

Also, even though I am passing the environment string array into execve(), it does not seem to use it and is forcing me to supply full path names of commands I want to execute. Will figure out what is going on later. For now, this is a good point to break and move on to later topics in the book (process management etc.)

Writing a new shell

2009-08-23T16:02:00.002+05:30

So I started writing my own shell called 'vish'. Lots of issues. The 'execve' system call does not seem to work consistently. I tried to track down the problem and what I found is this: I have a pointer to an array of strings which represent the command arguments that the user types in. I am using strtok to parse user input and build this structure. But as soon as I call fork(), this data structure is getting corrupted in both the parent and child processes. This just does not make any sense. Will get back and take a closer look.

Process Scheduling

2009-08-16T17:16:00.003+05:30

Just went through various algorithms for process scheduling. The one that really interests me is Lottery Scheduling. Can't wait to get into how exactly scheduling is implemented in Minix.

On an unrelated note, I am about to start writing my own shell. Think I will call it vish! I guess this shell could produce error messages that start with "You vish".

Programming with semaphores

2009-08-10T06:04:00.002+05:30

Just studied the different examples on using semaphores in the Tanenbaum book. Consider a non-trivial one like the solution given for the Dining Philosopher's problem. Sitting and staring at the algorithm for hours helps you understand it but not in such a way that you can recall it at a later time. Nor is it easy to find flaws in these algorithms just by inspection. I think that the only way to get good at using semaphores intelligently is to spend lots of time programming and debugging with them. If you don't use it you lose it.

Race conditions are painful because of their unpredictability.

Semaphores

2009-08-04T09:55:00.003+05:30

But then, race conditions can happen in Petersen's approach too and even in the sleep/wake-up approach suggested in the producer-consumer (which share a read-write buffer) problem. That is where Djikstra's semaphores come in. Semaphores basically keep track of pending wake-up calls and account for each of them. Semaphore 'ups/downs' are analogous to 'wake-ups/sleeps' in the producer-consumer problem.

Cooperating processes

2009-08-03T12:15:00.002+05:30

I am currently reading about different approaches to ensure protection of shared resources in a system that supports multiples processes: the concept of mutual exclusion. Petersen's approach is very simple and elegant. A variant of this relies on the hardware by using the TSL hardware instruction. Fun stuff.

I also wrote and tested a C program that tests most of the system calls on Ubuntu Linux 9.0.4. It was a great experience. The actual exercise is to test this on Minix but I don't yet have a machine on which I can install and play with Minix.

Hardware Interrupts

2009-07-27T09:57:00.003+05:30

Back to the basics! I want to plug holes in my knowledge so I am currently studying Tanenbaum's 'Operating Systems: Design and Implementation' also known as The Minix Book.

The topic is 'hardware interrupts'. This concept is a little difficult to understand for an application programmer who takes many things about the hardware and software for granted. Tanenbaum explains it well but I had to read it multiple times to grasp it. One reason is that the author does not provide a diagram to illustrate what happens when a hardware interrupt occurs. Maybe I will create one and post it here!

Comments welcome.