Scheduling, keyboards and IPC

[zhiayang]

I'm not sure if this should belong in this sub forum or the other one... Either way.

Finally after what seems like an eternity, I've got a system that's runs stable for more than 48 hours. Right now I'm implementing a simple userspace shell program, and I have a couple of issues:

1. How is keyboard input generally handled? In UNIX the process opens a file handle to stdin and uses general Read() and Write() functions, but is there another way?

2. Currently I have the driver set up with IPC, where it sends messages to the process and the process will get key presses from that. This is more of a microkernel approach (isn't it?) but that wasn't what I was aiming for... Is this a good thing, or too much of a performance impediment?

3. Say I go with the method described in (2). (this question probably applies to other things as well). How would scheduling work? Right now I'm theorising that the large (noticeable) lag when typing is caused by a amalgamation of factors, including system calls (interrupt gates) to read the message, the fact that the shell process is not immediately scheduled when a message is received, etc.

The third question bugs me the most. Say, for example, that Process A receives a message and it just got preempted and is at the back of the queue (assuming a single-priority, equal timeslice scheduler). Should receiving a message interrupt the current process and run Process A; insert Process A right after the current running process, or something else?

I think this applies for waiting for I/O accesses as well, like reading a file synchronously. File I/O isn't as urgent as something like keyboard input though.

Suggestions?

[bwat]

Right now I'm theorising that the large (noticeable) lag when typing is caused by a amalgamation of factors, including system calls (interrupt gates) to read the message, the fact that the shell process is not immediately scheduled when a message is received, etc.

Eh? What is the processor load? My guess is that you've got big problems somewhere. Humans type very slowly relative to CPU instruction latency.

If you want to understand scheduling and keyboard/TTY processing in a general purpose OS then I would suggest reading lots of general purpose OS source code. The UNIX v6 and Lion's commentary on it wouldn't be such a bad place to start. The XINU book is another great reference (which I prefer actually).

[h0bby1]

in my os, everything is window based, even in text mode, it can use windows, so all event are windows based

but in general the idea is to have an event stack, either on a window or application/task basis, and to have a device manager below who pull state from devices, and dispatch the event to the event stack of application

if it's windows based, to the windows who has the focus, and the task poll the windows event task

or on a task basis, a system of event filter can be implemented on a task basis, to know what kind of event the application want to recieve, and the system forward the event to the concerned task's event stack

or various system can be thought to match device input to an event stack that will be initialized by the application

either a thread can poll the events in the background, the device manager push events in the stack, and then wake up an event processing task to process them, or an interupt driven call back system, or with a task gate maybe something could be made if the input device work with interupt

if you really want low delay response, the best is something interupt driven, because you'll have the input delivered as fast as hardware can do, but it can lead to some issues, or otherwise threads with event stacks can be the way to go, or if you have something windows based, then the windows manager can do most of the job and then doing event handling with the windowing api, either with a call back or event stack polling

[Brendan]

Hi,

I'm not sure if this should belong in this sub forum or the other one... Either way.

Finally after what seems like an eternity, I've got a system that's runs stable for more than 48 hours. Right now I'm implementing a simple userspace shell program, and I have a couple of issues:

1. How is keyboard input generally handled? In UNIX the process opens a file handle to stdin and uses general Read() and Write() functions, but is there another way?

In general, the keyboard driver sends something to a process. The "something" can be ASCII characters and nothing else, or a full "keypress packet" (containing unicode, various meta key states, if it was pressed/released, etc), or anything else. How it's sent could be messages or pipes or any other type of IPC; or could be (e.g.) a shared FIFO queue or some other shared data structures that mostly behaves as a type of IPC anyway.

2. Currently I have the driver set up with IPC, where it sends messages to the process and the process will get key presses from that. This is more of a microkernel approach (isn't it?) but that wasn't what I was aiming for... Is this a good thing, or too much of a performance impediment?

3. Say I go with the method described in (2). (this question probably applies to other things as well). How would scheduling work? Right now I'm theorising that the large (noticeable) lag when typing is caused by a amalgamation of factors, including system calls (interrupt gates) to read the message, the fact that the shell process is not immediately scheduled when a message is received, etc.

How it works depends on how you decide it should work. As an example; imagine you've got a relatively high priority task that called some sort of "getIPCdata()" kernel function, and there was no data to get so the kernel blocks that task. Then the keyboard driver sends some data to that task; causing the task to be unblocked ("ready to run"). When the task is being unblocked the scheduler notices that the task is higher priority than whatever is currently running and does a task switch immediately (the high priority task pre-empts the currently running task). The task starts running where it left off in the "getIPCdata()" kernel function; which can now return the received data to the task. In this case the time between a user pressing a key and that task receiving it can be extremely low. Also note that in this case (due to task priorities and pre-emption) the CPU could be extremely overloaded (e.g. trying to run hundreds of average priority tasks) and it won't make any difference to how quickly the higher priority task gets the data from the keyboard driver.

The third question bugs me the most. Say, for example, that Process A receives a message and it just got preempted and is at the back of the queue (assuming a single-priority, equal timeslice scheduler). Should receiving a message interrupt the current process and run Process A; insert Process A right after the current running process, or something else?

The problem here would be using a "single-priority equal timeslice scheduler" (round robin scheduler) - they are very bad for performance (latency) because you can't say "this task is interactive and is more important than those other 100 tasks compiling something in the background". If you put recently unblocked tasks at the back of the queue they have to wait for potentially hundreds of other tasks before they get CPU time; and if you put recently unblocked tasks at the front of the queue then people will abuse it (constantly blocking and unblocking to get bumped to the front of the queue and hog a massive amount of CPU time).

The solution is to have a scheduler that understands task priorities. For example, let's say you've only got 3 priorities - "high priority", "normal priority" and "low priority", with a queue for each priority, where high priority tasks pre-empt normal priority tasks and low priority tasks, and where normal priority tasks pre-empt low priority tasks. In this case, you might have 20 low priority tasks, 75 normal priority tasks and 5 high priority tasks; and if the task waiting for keyboard is unblocked it could be placed at the back of the high priority queue and would only have to wait for 5 other tasks to use the CPU before it gets a turn (and wouldn't have to wait for 100 tasks to use the CPU).

With more complex schedulers you can even better behaviour for various cases. For a random example, you could have several different scheduling policies (each with different task priorities and scheduling algorithms); where one is designed for real-time tasks (and might use "earliest deadline first"), one is designed for normal tasks (and might have 8 priority queues and use "round robin" for each queue), and one could be designed for background tasks (and might have 32 priorities where priority determines timeslice length).

I think this applies for waiting for I/O accesses as well, like reading a file synchronously. File I/O isn't as urgent as something like keyboard input though.

It applies to every situation where an important task is waiting for data from something (which can include waiting for data from another important task, or keyboard, mouse, network packets, file IO, etc). For a simple example, imagine a web server that waits to receive a "HTTP request", then does a little work (including asking to read data from a file), then waits to for data from a file to arrive, then sends a "HTTP reply". If each "waits for" means waiting for something and then also waiting for 100 tasks to have their 10 ms time slice, then the time between the "HTTP request" being received and the "HTTP reply" being sent is going to be at least 2 seconds.


Cheers,

Brendan

[zhiayang]

Hi,

I'm not sure if this should belong in this sub forum or the other one... Either way.

Finally after what seems like an eternity, I've got a system that's runs stable for more than 48 hours. Right now I'm implementing a simple userspace shell program, and I have a couple of issues:

1. How is keyboard input generally handled? In UNIX the process opens a file handle to stdin and uses general Read() and Write() functions, but is there another way?

In general, the keyboard driver sends something to a process. The "something" can be ASCII characters and nothing else, or a full "keypress packet" (containing unicode, various meta key states, if it was pressed/released, etc), or anything else. How it's sent could be messages or pipes or any other type of IPC; or could be (e.g.) a shared FIFO queue or some other shared data structures that mostly behaves as a type of IPC anyway.

2. Currently I have the driver set up with IPC, where it sends messages to the process and the process will get key presses from that. This is more of a microkernel approach (isn't it?) but that wasn't what I was aiming for... Is this a good thing, or too much of a performance impediment?

3. Say I go with the method described in (2). (this question probably applies to other things as well). How would scheduling work? Right now I'm theorising that the large (noticeable) lag when typing is caused by a amalgamation of factors, including system calls (interrupt gates) to read the message, the fact that the shell process is not immediately scheduled when a message is received, etc.

How it works depends on how you decide it should work. As an example; imagine you've got a relatively high priority task that called some sort of "getIPCdata()" kernel function, and there was no data to get so the kernel blocks that task. Then the keyboard driver sends some data to that task; causing the task to be unblocked ("ready to run"). When the task is being unblocked the scheduler notices that the task is higher priority than whatever is currently running and does a task switch immediately (the high priority task pre-empts the currently running task). The task starts running where it left off in the "getIPCdata()" kernel function; which can now return the received data to the task. In this case the time between a user pressing a key and that task receiving it can be extremely low. Also note that in this case (due to task priorities and pre-emption) the CPU could be extremely overloaded (e.g. trying to run hundreds of average priority tasks) and it won't make any difference to how quickly the higher priority task gets the data from the keyboard driver.

The third question bugs me the most. Say, for example, that Process A receives a message and it just got preempted and is at the back of the queue (assuming a single-priority, equal timeslice scheduler). Should receiving a message interrupt the current process and run Process A; insert Process A right after the current running process, or something else?

The problem here would be using a "single-priority equal timeslice scheduler" (round robin scheduler) - they are very bad for performance (latency) because you can't say "this task is interactive and is more important than those other 100 tasks compiling something in the background". If you put recently unblocked tasks at the back of the queue they have to wait for potentially hundreds of other tasks before they get CPU time; and if you put recently unblocked tasks at the front of the queue then people will abuse it (constantly blocking and unblocking to get bumped to the front of the queue and hog a massive amount of CPU time).

The solution is to have a scheduler that understands task priorities. For example, let's say you've only got 3 priorities - "high priority", "normal priority" and "low priority", with a queue for each priority, where high priority tasks pre-empt normal priority tasks and low priority tasks, and where normal priority tasks pre-empt low priority tasks. In this case, you might have 20 low priority tasks, 75 normal priority tasks and 5 high priority tasks; and if the task waiting for keyboard is unblocked it could be placed at the back of the high priority queue and would only have to wait for 5 other tasks to use the CPU before it gets a turn (and wouldn't have to wait for 100 tasks to use the CPU).

With more complex schedulers you can even better behaviour for various cases. For a random example, you could have several different scheduling policies (each with different task priorities and scheduling algorithms); where one is designed for real-time tasks (and might use "earliest deadline first"), one is designed for normal tasks (and might have 8 priority queues and use "round robin" for each queue), and one could be designed for background tasks (and might have 32 priorities where priority determines timeslice length).

I think this applies for waiting for I/O accesses as well, like reading a file synchronously. File I/O isn't as urgent as something like keyboard input though.

It applies to every situation where an important task is waiting for data from something (which can include waiting for data from another important task, or keyboard, mouse, network packets, file IO, etc). For a simple example, imagine a web server that waits to receive a "HTTP request", then does a little work (including asking to read data from a file), then waits to for data from a file to arrive, then sends a "HTTP reply". If each "waits for" means waiting for something and then also waiting for 100 tasks to have their 10 ms time slice, then the time between the "HTTP request" being received and the "HTTP reply" being sent is going to be at least 2 seconds.


Cheers,

Brendan

This makes sense now, thanks. Probably a good idea to go read more on scheduling algorithms...

[sortie]

Hi,

A few random thoughts:

It is likely important for your operating system to favour interactive processes in use: If the kernel knows which processes will receive keyboard input (or which processes the events were forwarded to), it would likely be a good heuristic to put them at maximum priority for a single timeslice whenever a keyboard event occurs. This way keyboard-to-screen latency improves considerably without much penalty to the rest of the system.

Do not confuse keyboard input with stdin. The kernel would likely deliver keyboard events to user-space, as it is a more universal format - it will then later get reduced to a text stream sent through the terminal system and thus becoming stdin for the target process.

[zhiayang]

Hi,

A few random thoughts:

It is likely important for your operating system to favour interactive processes in use: If the kernel knows which processes will receive keyboard input (or which processes the events were forwarded to), it would likely be a good heuristic to put them at maximum priority for a single timeslice whenever a keyboard event occurs. This way keyboard-to-screen latency improves considerably without much penalty to the rest of the system.

This makes sense... So for example if a keyboard event is sent to the IPC dispatcher, it would first put the target process/thread at max priority, then send the message to pre-empt the current thread?

Do not confuse keyboard input with stdin. The kernel would likely deliver keyboard events to user-space, as it is a more universal format - it will then later get reduced to a text stream sent through the terminal system and thus becoming stdin for the target process.

Right... I've got to read up on this, but how does the terminal control the standard streams?

Also, another thing: how are variable time slices implemented? By changing the one-shot counter of the PIC every interrupt or something?

[Brendan]

Hi,

It is likely important for your operating system to favour interactive processes in use: If the kernel knows which processes will receive keyboard input (or which processes the events were forwarded to), it would likely be a good heuristic to put them at maximum priority for a single timeslice whenever a keyboard event occurs. This way keyboard-to-screen latency improves considerably without much penalty to the rest of the system.

This makes sense... So for example if a keyboard event is sent to the IPC dispatcher, it would first put the target process/thread at max priority, then send the message to pre-empt the current thread?

There's lots of ways of determining task priorities; and you can split them into "base priority" and "boosts". There are 2 categories to determine base priority.

The first category is "attempting to guest because you don't know", where the scheduler uses (often broken and abusable) heuristics to determine what priority a task uses. An example of this is Linux, which tends to decide that a task is "interactive" if it blocks a lot and is CPU bound if it doesn't. This means that if you've got a compiler running in the background that happens to block a lot due to waiting for file IO, then the scheduler decides it's "interactive" and gives it a higher priority; and if you've got a 3D game that's struggling to maintain 60 frames per second and uses a lot of CPU time (due to graphics and polling for keyboard/mouse/network) then the scheduler decides it's not interactive and gives it a priority nerf. It also means that a process can track the time it uses and sleep for 1 us just before its time slice ends to trick the scheduler into thinking it blocks a lot and get a priority boost.

The second category is "knowing", where the scheduler is told what priority different tasks are (e.g. when they're created) and doesn't need to guess. This can also be broken and abusable (e.g. programmers saying their software should be extremely high priority for no reason); but there are ways to minimise that. For example, you could have a "max. priority" for each task and say that when a task is created its max. priority must be less than or equal to max priority of the task that created it. Of course you'd also have a "current priority" and let a task change its own priority to anything less than its max. priority whenever it wants. Typically, for a system like this, programmers think in terms of relative priority - e.g. an application developer might have one thread for handling user interaction that they want to use max. priority, plus other threads that they want running at a lower priority (so that the latency of their own "user interaction" doesn't get messed up by their other threads); or a GUI developer might give applications a slightly lower priority than their GUI (so that laggy applications don't mess up the GUI's responsiveness).

Once you've got a base priority to work with, you can add a system of "temporary boosts". A well known example is Windows, which gives an application a priority boost if its window has focus. For a well designed OS (e.g. where the GUI isn't built into the OS and is just another installable/changeable piece of software) this means having a set of rules to determine who is allowed to boost who. Another example (that tends to be used in micro-kernels) is to allow a message receiver to temporarily inherit the priority of the message sender; so that if a high priority task sends a "request message" to a lower priority task then the lower priority task gets boosted up to high priority. Of course this shouldn't happen for "reply messages"; which means the kernel has to know the difference between requests and replies or it won't work (e.g. it couldn't work for my kernel's asynchronous messaging).

Also don't forget that this is not just about user interaction - there can be many different things that need to respond quickly that don't involve the user at all (mostly servers - DNS, NTP, HTTP, SQL, etc).

Also, another thing: how are variable time slices implemented? By changing the one-shot counter of the PIC every interrupt or something?

Either you have a fixed frequency timer where a task is given a variable number of "ticks", or you have a one-shot timer.

There's also something I'd call "variable frequency scheduling" where each task is given a fixed length time slice, but higher priority tasks are given more fixed length time slices. For example, with 4 tasks (A, B, C and D) where A gets twice as much time as B, B gets twice as much time as C, and C gets twice as much time as D; a variable time slice scheduler might do "AAAAAAAABBBBCCD" while a variable frequency scheduler might do "ABACABADABACABA". The variable time slice scheduling has a lot less task switches but can be "lumpy" under load (e.g. look at task B), while the variable frequency scheduling has a lot more task switches but is also a lot smoother under load. For low priority tasks, "lumpy" isn't a problem so variable time slice scheduling is probably better; and for normal/medium priority tasks "lumpy" can be ugly and variable frequency scheduling can be more suitable.

Of course the idea that different tasks should share the CPU can be wrong. To understand this, imagine a painter that has to paint 10 different houses for 10 different people - it's better to have 5 finished houses and 5 houses waiting than it is to have 10 half-finished houses. This means giving as much CPU time as possible to a single task (possibly the task that was started first, or perhaps the task with the earliest deadline).

The important thing to realise is that it's possible for a kernel to have many different "scheduling policies" for different types of tasks. For example; for very high priority tasks you might use "highest priority task that can run does run", for medium-high priority tasks you might use variable frequency scheduling, for medium-low priority tasks you might use variable time slice scheduling and for low priority tasks you might use "task that was started first gets all CPU time" scheduling. You don't have to use the same scheduling for all tasks and end up with "one size fits all/some/none".


Cheers,

Brendan