3

What is the best algorithm to use for scheduling an application that will support 10K concurrent threads with heavy I/O but low CPU usage? Links to papers are appreciated.

McGovernTheory
  • 6,556
  • 4
  • 41
  • 75
  • What is your definition of 'best'? – stephendl Mar 31 '09 at 16:05
  • Also, this seems a bit more of a Computer Science question than a programming question. I wouldn't close it on that basis, but thought it worth a mention. It even sounds a bit like homework. – John Saunders Mar 31 '09 at 16:08

5 Answers5

4

Why wouldn't you use SCHED_RR? You said it yourself: low CPU usage. You could even nice the process when you expect to do some heavy I/O so you're scheduled less often than other processes.

In general, though, why not let the OS do what it's best at, and just worry about writing efficient code? The OS will know you're doing a blocking I/O call and will put your thread/task in a waitqueue and select another task to run. You don't need to worry about those details.

FreeMemory
  • 8,444
  • 7
  • 37
  • 49
  • So, if I were game to write my own scheduler code, what papers should I read? – McGovernTheory Apr 03 '09 at 20:47
  • Papers? I guess you could check out the chapter on "Scheduling" in "Modern Operating Systems" by Tanenbaum. Or you can read up on scheduling in "Understanding the Linux Kernel." Or you can look at schedule() in kernel/sched.c - which is probably the best for real, practical knowledge. – FreeMemory Apr 08 '09 at 18:28
1

Actually I believe no scheduling mechanism will handle this number of threads flawlesly as the management tables in the kernel will become quite large.

If possible, I'd suggest rewriting the app to use asynchronous I/O, select() or something similar on the OS of your choice.

grover
  • 2,265
  • 1
  • 16
  • 15
1

You will likely want SCHED_RR for this. You might be interested in reading this question regarding the difference between SCHED_FIFO and SCHED_RR.

Community
  • 1
  • 1
Tim Post
  • 33,371
  • 15
  • 110
  • 174
1

Your problem is more related to I/O scheduling than Thread scheduling. The linux kernel offers various I/O scheduler mplementations. You can find a good article on this subject in this edition of LWN.

shodanex
  • 14,975
  • 11
  • 57
  • 91
0

As grover suggested, you could also use some Thread pooling mechanisms, which are less resource intensive and will solve your purpose at least to some reasonable extent, if not fully

Prabhu R
  • 13,836
  • 21
  • 78
  • 112