home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / os / linux / 22452 < prev    next >
Encoding:
Text File  |  1993-01-02  |  4.0 KB  |  81 lines
  1. Newsgroups: comp.os.linux
  2. Path: sparky!uunet!uchinews!msuinfo!oak!perlis!wissner
  3. From: wissner@perlis.mcs.gvsu.edu (Jim Wissner)
  4. Subject: Linux Scheduling (Was Re: Die Die Die) (long)
  5. Message-ID: <1992Dec21.155544.20713@mcs.gvsu.edu>
  6. Sender: news@mcs.gvsu.edu
  7. Nntp-Posting-Host: perlis
  8. Organization: Grand Valley State University, Allendale MI
  9. References: <BzM129.Lp@brunel.ac.uk>
  10. Date: Mon, 21 Dec 1992 15:55:44 GMT
  11. Lines: 68
  12.  
  13. In article <BzM129.Lp@brunel.ac.uk> cs89rdb@brunel.ac.uk (Roger D Binns) writes:
  14. >Is it possible to improve the console driver to accept a few more
  15. >keystrokes?  Try the following line, and see if you can get control
  16. >of your machine back.  I can't do anything except press the reset
  17. >button on the box.
  18. >
  19. >while true ; do (ping 127.0.0.1 &) ; done
  20. >
  21. >It doesn't run out of processes, but does run out of swap.  It would
  22. >be nice if there was a magical keystroke that could deal with this,
  23. >and kill the process with the highest pid for instance.  I suggest 
  24. >ctrl+alt+ins.
  25. >
  26. >I have had similar 'lockups' while using X, for instance while running
  27. >xv, and a C compiler.  It swaps so much, there is nothing I can do.
  28. >Init doesn't even get scheduled so that it can handle the soft
  29. >ctrl+alt+delete.
  30.  
  31. The Linux scheduler follows (in general) a round-robin scheduling model,
  32. in that each process initially gets a fixed time quantum.  Of course, if
  33. a process uses up its quantum it is preempted, and if it needs to sleep
  34. while doing some sort of IO, it releases the CPU voluntarily.
  35.  
  36. It does not, however, pick the next process to schedule in the traditional
  37. manner.  Normally, new processes are put in at the tail of the queue,
  38. and the scheduler picks processes from the head of the queue.
  39. When it's time, the current process is thrown to the tail of the queue
  40. and the scheduler picks the next process.  There is a sense of ordering.
  41.  
  42. Linux does not follow this order so strictly.  Specifically, new 
  43. processes will get picked right away (the opposite of the above) and
  44. any processes that are woken up and found to have a higher 'priority'
  45. than the current process will preempt the current process (as opposed
  46. to the above, where they wait until their turn comes around again,
  47. regardless of their priority.).  Usually this works quite well:
  48. interactive jobs get a good response time as you would want.
  49.  
  50. And theoretically, the scheme Linux uses shouldn't allow for starvation
  51. (what you are experiencing) - processes that use their quantum will
  52. 'wait' until all other processes have had their chance.  There is,
  53. however, no mechanism to /prevent/ starvation.  This is what I suspect
  54. is happening: you are flooding the system with new processes, and even
  55. if you aren't running out of them, you are still preventing anything
  56. else from getting scheduled.  (Remember, incoming jobs will get an
  57. advantage over existing ones?)  So in effect, you are in an unbreakable
  58. loop.  I suspect also that the same thing is happening (to a lesser
  59. extent) with the xv & gcc.  Particularly if you are 'making' something -
  60. which is continually spawning off new processes.  While this isn't as
  61. bad as your first problem, you can still really hurt some processes.
  62.  
  63. As part of an independant study, I have re-written the Linux scheduler.
  64. I performed a lot of testing on the current one, and found that for
  65. most things it works extremely well.  However, once you have X going
  66. and start a couple gcc's and some other things (ie, a multi-user
  67. environment) - things can get pretty nasty.  What I have implemented
  68. is a multi-level feedback queue, which currently using only two queues:
  69. a high and a low priority.  (I'm experimenting with three levels).
  70. I've been running it for quite a while now and it [seems to be] quite
  71. stable.  For the most part you don't notice a difference, but when a
  72. bunch of CPU intensive jobs are submitted, there is a noticable
  73. improvement in the response time to incoming interactive jobs.  There
  74. is still quite a bit of tweaking to be done before it is optimal,
  75. I'm sure.  But if you wish to take a look at it and try it out I'd
  76. be happy to give it to you.
  77.  
  78. >Roger
  79.  
  80. Jim.
  81.