OSDev.org

The Place to Start for Operating System Developers
It is currently Mon Nov 23, 2020 7:23 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 13 posts ] 
Author Message
 Post subject: Partial time slices
PostPosted: Tue May 12, 2020 1:54 pm 
Offline
Member
Member
User avatar

Joined: Mon Jun 05, 2006 11:00 pm
Posts: 2077
Location: USA (and Australia)
Let's say you have two threads, and your timer fires every 10ms.

One thread runs for 8ms and yields itself. The other thread runs for 2ms, and the timer then preempts it, and switches back to the other thread.

The thread that is cooperatively yeilding, could actually be getting 80% of the processor time. I feel that it's unfair to penalize the busy thread that doesn't yield with a partial time slice.

How do others deal with partial time slices?

Do you ignore the problem, and don't care if you penalize threads with partial time slices? Do you tell your scheduler to skip preemping on the next run (so yielding is a thread voluntarily giving the rest of it's timeslice to another thread, giving the next thread an extra long time slice?) Run your timer at a higher rate that your scheduler, and make sure each thread gets a certain number of ticks before preempting?

_________________
My OS is Perception.


Top
 Profile  
 
 Post subject: Re: Partial time slices
PostPosted: Tue May 12, 2020 3:44 pm 
Offline
Member
Member
User avatar

Joined: Mon Jun 05, 2006 11:00 pm
Posts: 2077
Location: USA (and Australia)
I was wondering if instead of a fixed frequency, it would be better for my timer to run in one shot mode? Then every time I context switch, I can reset the timer to the maximum time slice?

_________________
My OS is Perception.


Top
 Profile  
 
 Post subject: Re: Partial time slices
PostPosted: Tue May 12, 2020 10:19 pm 
Offline
Member
Member

Joined: Wed Oct 26, 2011 12:00 pm
Posts: 192
I can only say for myself what i do, which is to run my timer in one-shot mode and then reset it to the given time-slice at every context switch. I use a multilevel feedback queue, which simply means i reward threads that give up their time-slice by keeping their priority and resetting their time-slice to full, and i penalize threads using the entire time-slice by reducing their priority, but however giving them a longer time-slice next time they are up for running.

_________________
Github
Website


Top
 Profile  
 
 Post subject: Re: Partial time slices
PostPosted: Wed May 13, 2020 1:15 am 
Offline
Member
Member
User avatar

Joined: Thu Aug 11, 2005 11:00 pm
Posts: 1101
Location: Tartu, Estonia
I agree with MollenOS (even though I have not yet implemented this in my scheduler, but I plan to do so). I think that a one-shot timer makes much more sense than a periodic timer to set the maximum time a thread may spend running at once, since most of the time threads should yield / block for other reasons than expiring a time slice (unless there is actual competition for CPU time, because there are several compute intensive threads). Threads could be waiting for I/O, user input or other events to happen, and would thus issue a blocking wait. Possibly all threads would do that, and so in the end the CPU would be idle (unless there is 100% CPU usage). And for the "idle state", there is not much reason to be woken up by a periodic or one-shot timer at all, so that mechanism could even be applied only to non-idle threads.

_________________
Programmers' Hardware Database // GitHub user: xenos1984; OS project: NOS


Top
 Profile  
 
 Post subject: Re: Partial time slices
PostPosted: Wed May 13, 2020 4:19 am 
Offline
Member
Member
User avatar

Joined: Sat Mar 31, 2012 3:07 am
Posts: 3988
Location: Chichester, UK
If you use a one-shot timer, how do you keep track of elapsed time in your kernel?

There's a very good discussion of various scheduling approaches here: http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf and here: http://pages.cs.wisc.edu/~remzi/OSTEP/c ... d-mlfq.pdf


Top
 Profile  
 
 Post subject: Re: Partial time slices
PostPosted: Wed May 13, 2020 9:16 am 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 765
Timekeeping and timers are orthogonal to scheduling.

Managarm uses a tickless design, i.e., the length of a time slice is computed dynamically whenever a thread is scheduled. The calculation to do this is similar (but not equivalent) to Linux' CFS. Basically, the idea is that each thread should run for a fraction of exactly 1/(# threads) of the time.

The local APIC timer is used to enforce the time slice but it is in no way special compared to other IRQs - each IRQ or syscall can trigger rescheduling if higher priority threads wake up. Priority does not affect the length of a time slice, it determines whether a thread is scheduled or not. Managarm always schedules the thread with highest priority. In the common situation that many processes have the same priority, Managarm schedules the thread with highest "unfairness", i.e., the thread whose fraction of running time deviates most extremely from 1/(# threads).

To keep track of real time (and monotonic time), Managarm uses the TSC (with HPET as fallback if no invariant TSC exists). The HPET is used for global timers (even when TSC is used for timekeeping). The TSC has the advantage that it can be read from userspace. To let userspace compute the offset to real-time (i.e., UTC), a read-only page is mapped into each process and updated by a "clocktracker" server.

_________________
managarm: Microkernel-based OS capable of running a Wayland desktop (Discord: https://discord.gg/7WB6Ur3). My OS-dev projects: [mlibc: Portable C library for managarm, qword, Linux, Sigma, ...] [LAI: AML interpreter] [xbstrap: Build system for OS distributions].


Top
 Profile  
 
 Post subject: Re: Partial time slices
PostPosted: Fri May 15, 2020 5:11 pm 
Offline
Member
Member

Joined: Wed Mar 09, 2011 3:55 am
Posts: 397
Korona wrote:
The TSC has the advantage that it can be read from userspace. To let userspace compute the offset to real-time (i.e., UTC), a read-only page is mapped into each process and updated by a "clocktracker" server.


It's probably best not to enable the TSD flag or provide a wall time offset for all processes, as even relative timing information (let alone access to actual wall time) can have security implications.


Top
 Profile  
 
 Post subject: Re: Partial time slices
PostPosted: Sat May 16, 2020 1:39 am 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 706
linguofreak wrote:
It's probably best not to enable the TSD flag or provide a wall time offset for all processes, as even relative timing information (let alone access to actual wall time) can have security implications.
Did you mean to say, that the TSD flag should be set (to disallow userspace from reading the TSC)? Besides, yes, side channels are a thing. Denying service to your law-abiding programs to prevent side channels is, however, stupid. If need be, anyone can fashion a timer just from having a second thread increase a global variable. Sure it won't be as accurate, but for a side-channel attack, it might just be enough. Moreover, many programs want to know relative timing information for many reasons, not the least of whic being profiling, and preventing them from doing that because one day, and insecure application on your system may be exploited is as sensible as removing all knifes from your house because someone might hurt others with them.

Besides timing side channels, I see no security implications for timing information.

_________________
Thou hast outraged, not insulted me, sir; but for that I ask thee not to beware of Starbuck; thou wouldst but laugh; but let Ahab beware of Ahab; beware of thyself, old man.


Top
 Profile  
 
 Post subject: Re: Partial time slices
PostPosted: Sat May 16, 2020 1:50 am 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 765
IMHO, disabling TSC to prevent side channel attacks is a fool's errand, at least if you do not severely restrict your system also in other ways. A similarly accurate clock can be constructed by concurrently incrementing a 64-bit counter from another userspace thread. It was shown over and over again that timing attacks are also possible (even though a bit harder) with less accurate clocks by averaging and exploiting the law of large numbers.

_________________
managarm: Microkernel-based OS capable of running a Wayland desktop (Discord: https://discord.gg/7WB6Ur3). My OS-dev projects: [mlibc: Portable C library for managarm, qword, Linux, Sigma, ...] [LAI: AML interpreter] [xbstrap: Build system for OS distributions].


Top
 Profile  
 
 Post subject: Re: Partial time slices
PostPosted: Tue May 19, 2020 8:35 am 
Offline
Member
Member
User avatar

Joined: Mon May 22, 2017 5:56 am
Posts: 383
Korona wrote:
IMHO, disabling TSC to prevent side channel attacks is a fool's errand, at least if you do not severely restrict your system also in other ways. A similarly accurate clock can be constructed by concurrently incrementing a 64-bit counter from another userspace thread. It was shown over and over again that timing attacks are also possible (even though a bit harder) with less accurate clocks by averaging and exploiting the law of large numbers.

Would it help to introduce a bit of randomness into the scheduler timing, or does it just result in a "less accurate clock"?

I'm also almost sure there was a Linux kernel option to randomize the TSC, last time I configured it, (2.6.??) but now I'm not sure that makes any sense, let alone whether it would help.

_________________
Kaph link pending. code pending. design pending. plans in a state of flux! everything pending! choice of language still up in the air! why is nothing coming together?!?


Top
 Profile  
 
 Post subject: Re: Partial time slices
PostPosted: Tue May 19, 2020 10:25 pm 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 706
eekee wrote:
Would it help to introduce a bit of randomness into the scheduler timing, or does it just result in a "less accurate clock"?
Help with what? Also, yes, a more random clock is just a little less accurate. And modern CPUs are so fast that a thread incrementing a global variable can get many, many cycles in before being preempted. Again, it's not perfect, but it is good enough. Overall, the timer thread is always runnable and will therefore consume most of one CPU core. If not much else is going on, there may not even be a need to ever preempt this thread.

eekee wrote:
I'm also almost sure there was a Linux kernel option to randomize the TSC, last time I configured it, (2.6.??) but now I'm not sure that makes any sense, let alone whether it would help.
Well, it no longer exists as far as I could find. To my knowledge there is no way to change the TSC. Even if there was, there would be no point, since most of the code using the TSC is only interested in its differences over time. And if the Linux team somehow found a way to make the TSC completely useless, there are other methods of timing things.

_________________
Thou hast outraged, not insulted me, sir; but for that I ask thee not to beware of Starbuck; thou wouldst but laugh; but let Ahab beware of Ahab; beware of thyself, old man.


Top
 Profile  
 
 Post subject: Re: Partial time slices
PostPosted: Wed May 20, 2020 5:27 am 
Offline
Member
Member
User avatar

Joined: Mon May 22, 2017 5:56 am
Posts: 383
That all makes sense, thanks.

_________________
Kaph link pending. code pending. design pending. plans in a state of flux! everything pending! choice of language still up in the air! why is nothing coming together?!?


Top
 Profile  
 
 Post subject: Re: Partial time slices
PostPosted: Tue Jul 07, 2020 3:45 am 
Offline
Member
Member

Joined: Fri May 20, 2016 2:29 pm
Posts: 42
Location: Paris, France
I implemented things such that when a process is scheduled, it tracks both when it was scheduled and how long its timeslice is, based on priority (MLFQ). The timer handler checks whether the current task has exceeded this lifetime, and if not, doesn't schedule.

_________________
www.github.com/codyd51/axle.git


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 13 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group