Daniel Carrera wrote:
> Hello,

> What is the default quantum size used by the Minix scheduler? I'm
> talking about user processes. The source code seems to say that it is
> "8 clock ticks" but I don't know how long a clock tick is. The Minix
> book (OS Design & Implementation) says 2050 msec, and I assume ms
> means millisecond, but that can't be right. That's two whole seconds!
> On the other hand, if msec means micro-second (which I would have
> written as usec) then the quantum looks too small.

> One possibility is that this is a typo in the book, and in reality AST
> meant to say 250ms. That sounds more like in the right ball-park (if I
> were to guess I would have guessed between 250ms and 25ms). But I
> would like to check.

I thought the clock frequency was in the range of 50/60 hz, which would
make a tick last 17/20 msec and a quantum last 133/160 msec. This seems
reasonable, especially because OS D&I 2 suggests a quantum size of around
100 msec (page 85). Which version of "the book" are you using and where do
you find the 2050 msec tick length?

Regards,

Jens

--
Jens de Smit
Student Computer Science | Vrije Universiteit Amsterdam
jfdsmit@few.vu.nl | http://www.few.vu.nl/~jfdsmit
"[In the end, people] get furious at IT that the goddamn magic isn't working"
-- Stewart Dean

On Sep 4, 8:02*pm, "J.F. de Smit" wrote:
> I thought the clock frequency was in the range of 50/60 hz, which would
> make a tick last 17/20 msec and a quantum last 133/160 msec. This seems
> reasonable, especially because OS D&I 2 suggests a quantum size of around
> 100 msec (page 85). Which version of "the book" are you using and where do
> you find the 2050 msec tick length?

I have a copy of version 3 and it says 2050 msec on page 104. The
numbers that you say sound reasonable. In addition, in a preceeding
paragraph AST gives an example of how if the quantum is 100ms and 10
users start a command at the same time, the last user will have to
wait 1 second, and that feels slow. So it seems strange that just
after saying this he would say "2050 msec is often a reasonable
compromise". It must be a misprint.

So I'll assume that 100ms is the right number.

Thanks for the help.
Daniel.

Daniel Carrera wrote:
> I have a copy of version 3 and it says 2050 msec on page 104. The
> numbers that you say sound reasonable. In addition, in a preceeding
> paragraph AST gives an example of how if the quantum is 100ms and 10
> users start a command at the same time, the last user will have to
> wait 1 second, and that feels slow. So it seems strange that just
> after saying this he would say "2050 msec is often a reasonable
> compromise". It must be a misprint.

> So I'll assume that 100ms is the right number.

I think 100 msec is still an approximation. I know the quantum length is
deducable from the source code (naturally), but I couldn't find it
yesterday and don't have time for extensive archeological activities.

The 1 second waiting time is actually pretty reasonable for such a
worst-case scenario is _ten_ people hitting at _exactly_ the same
time. This won't happen very often (how many times will ten people log in
to a Minix machine running interactive applications?). On the other hand,
2050 msec would incur a 2 second delay on _any_ concurrent operation,
which would definitely be too much. Still baffles me what it should have
been then: 250 msec still sounds like a lot while 205 msec doesn't make
sense as an approximate number. Two 0's where they don't belong sounds
unlogical and besides, 25 msecs sounds like really short. If a context
switch takes several ticks of itself, this would amount to 10-20%
performance loss on context switches themselves. Because microkernels
peform more context switches than monoloithic kernels, the performance hit
would be unbearable.

It would be fun to know how many ticks a context switch takes. The
clocktick handler in the clock task always counts 1 "lost tick", which
kind of suggests that there is only 1 tick happening while interrupts are
disabled, suggesting the switch takes less than 2 ticks. This could be
possible on modern CPU's because the frequency of ticks hasn't changed
while the frequency of cycles has, yielding more cycles per tick. Anyone
with detailed information on this?

Regards,

Jens


--
Jens de Smit
Student Computer Science | Vrije Universiteit Amsterdam
jfdsmit@few.vu.nl | http://www.few.vu.nl/~jfdsmit
"[In the end, people] get furious at IT that the goddamn magic isn't working"
-- Stewart Dean

>> I have a copy of version 3 and it says 2050 msec on page 104.

It correctly says "20 - 50 msec" in the three copies of the book we have
here.

By default, a clock tick is 1/60th of a second on MINIX3, i.e. about
17ms. See the definition of HZ in /usr/include/minix/const.h .

Any reasonably recent system can do thousands of context switches in
such a time period.

Regards,
David

On Sep 5, 9:44*am, "J.F. de Smit" wrote:
> Daniel Carrera wrote:
> I think 100 msec is still an approximation. I know the quantum length is
> deducable from the source code (naturally), but I couldn't find it
> yesterday and don't have time for extensive archeological activities.

I know that the quantum size is different for user applications and
for system applications (drivers and servers) but I don't think that
the quantum size varies between different user processes. I certainly
could not find anything to that effect in the source code, and I
really looked.

This is actually what I want to test with the scheduler. I wonder if
the scheduler would work better if the quantum size varied
dynamtically. This also goes back to why I was looking for a benchmark
the other day. In the end, I didn't find any suitable benchmark, so
I'm writing my own I'm not publishing it yet because I need to see
if it is actually capable of detecting differences between schedulers.

Daniel.

On Sep 5, 10:55*am, "D.C. van Moolenbroek" wrote:
> >> I have a copy of version 3 and it says 2050 msec on page 104.
>
> It correctly says "20 - 50 msec" in the three copies of the book we have
> here.

Oh, I should have thought of that. What I actually have is a digital
copy and a computer error appears to have removed all the -
characters. Usually this isn't a problem and I have no trouble reading
it, but in this example it totally changed the sentence.

Thanks for the help.

> By default, a clock tick is 1/60th of a second on MINIX3, i.e. about
> 17ms. See the definition of HZ in /usr/include/minix/const.h .

Hmm... I'm looking at include/minix/const.h and I can't find anything
about the clock. I see the constant CLICK_SIZE but that is talking
about memory, not the clock.

What's the name of the constant I should be looking for?

Thanks
Daniel.

D.C. van Moolenbroek wrote:
>>> I have a copy of version 3 and it says 2050 msec on page 104.

> It correctly says "20 - 50 msec" in the three copies of the book we have
> here.

> By default, a clock tick is 1/60th of a second on MINIX3, i.e. about
> 17ms. See the definition of HZ in /usr/include/minix/const.h .

Yeah, I thought that, just looked in the wrong place yesterday
(/usr/src/kernel/const.h).

> Any reasonably recent system can do thousands of context switches in
> such a time period.

Yeah, makes sense when you actually _think_ about it. Recent systems
execute at least 2 million cycles in 1 msec, which should by all means be
complete overkill for moving around a couple 100 bytes worth of registers,
doing some accounting and switching back to the user process. I guess I
was sleepy last night...

Regards,

Jens

--
Jens de Smit
Student Computer Science | Vrije Universiteit Amsterdam
jfdsmit@few.vu.nl | http://www.few.vu.nl/~jfdsmit
"[In the end, people] get furious at IT that the goddamn magic isn't working"
-- Stewart Dean

Daniel Carrera wrote:
> On Sep 5, 10:55?am, "D.C. van Moolenbroek" wrote:
> Oh, I should have thought of that. What I actually have is a digital
> copy [...]

Naughty naughty :P

>> By default, a clock tick is 1/60th of a second on MINIX3, i.e. about
>> 17ms. See the definition of HZ in /usr/include/minix/const.h .

> Hmm... I'm looking at include/minix/const.h and I can't find anything
> about the clock. I see the constant CLICK_SIZE but that is talking
> about memory, not the clock.

> What's the name of the constant I should be looking for?

Dave already said, you probably skimmed over it. It's "HZ" (short for
Hertz).

Regards,

Jens

--
Jens de Smit
Student Computer Science | Vrije Universiteit Amsterdam
jfdsmit@few.vu.nl | http://www.few.vu.nl/~jfdsmit
"[In the end, people] get furious at IT that the goddamn magic isn't working"
-- Stewart Dean

On Sep 5, 12:58*pm, "J.F. de Smit" wrote:
> Dave already said, you probably skimmed over it. It's "HZ" (short for
> Hertz).

Oh, yes I missed that. Ok, so we have:

#define HZ 60

So let's see... that means that a clock tick is 1/60s which translates
to ~17ms. Next I need to know how many clock ticks represent one
quantum. I couldn't find that exactly, but kernel/table.c gives the
init process 8 ticks (see boot_image). So I can use 8 ticks as my
first guess. That means that a user quantum is 8/60s =~ 133ms.

Does this sound right to you?

Some processes in the boot_image table are 4 ticks. If user processes
are also 4 ticks, then we get 67ms quanta.

Do you know how many ticks a user process is?

Thanks.
Daniel.