home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / mach / doc / unpublished / cpuserver.doc.Z / cpuserver.doc
Encoding:
Text File  |  1992-08-18  |  14.4 KB  |  297 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.                              THE MACH CPU_SERVER:
  13.                    AN IMPLEMENTATION OF PROCESSOR ALLOCATION
  14.  
  15.  
  16.                                  David L.Black
  17.  
  18.                         Department of Computer Science
  19.                           Carnegie-Mellon University
  20.                              Pittsburgh, PA 15213
  21.                                   Version of:
  22.                                 14 August 1990
  23.  
  24.  
  25.  
  26.  
  27.  
  28.  
  29.  
  30.  
  31.  
  32.  
  33.  
  34.  
  35.  
  36.  
  37.  
  38.                                    ABSTRACT
  39.  
  40. The CPU-Server is a user-mode server that performs processor allocation for the
  41. Mach operating system.  This  document  describes  the  server  and  it's  user
  42. interfaces.
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52.   This  research was sponsored by the Defense Advanced Research Projects Agency
  53. (DOD), ARPA Order No. 4864, monitored by the Space and  Naval  Warfare  Systems
  54. Command under contract N00039-84-C-0467.
  55.  
  56.   The views and conclusions contained in this document are those of the authors
  57. and should  not  be  interpreted  as  representing  official  policies,  either
  58. expressed  or  implied,  of the Defense Advanced Research Projects Agency or of
  59. the U.S.  Government.
  60. 1. Introduction
  61.   This document describes the cpu_server,  a  user-mode  server  that  performs
  62. processor allocation for the Mach operating system, and its library interfaces.
  63. The server implements processor allocation policy; the  actual  mechanisms  are
  64. contained  in  the  Mach kernel (see related document).  The library interfaces
  65. hide the details of server interaction from applications with simple scheduling
  66. requirements.  This server is an example implementation of processor allocation
  67. policy; many other policies can be implemented using the mechanisms provided by
  68. the kernel.
  69.  
  70.   Not  all  releases  of  Mach support this server. It is mainly interesting on
  71. multi-processor machines, so no major effort has been made to support it on the
  72. standard  uni-processor  versions  of  Mach.  However, the new releases of Mach
  73. support it on all machines. On systems that  support  it,  this  software  (MiG
  74. interface  to  server  and  library interfaces) is available in the cpu library
  75. (/usr/mach/lib/libcpu.a, -lcpu command to ld).
  76.  
  77. 2. Concepts
  78.   The server performs processor allocation by assigning processors to processor
  79. sets  provided  by  its clients.  This allows the clients to use and manage the
  80. processors without giving clients complete control over them; only  the  server
  81. has  the port capabilities required to reassign processors.  Processor sets are
  82. entities exported by the Mach kernel; threads assigned to a processor  set  run
  83. exclusively  on  processors  assigned  to  that  set  and  vice versa (with the
  84.                       tm
  85. exception of some Unix   system calls).
  86.  
  87.   The server interface is designed around a class of objects  called  requests.
  88. A request consists of the following components:
  89.  
  90.    - A run duration,
  91.  
  92.    - A sequence of <processor set, number of processor> pairs.
  93.  
  94. A request is satisfied by assigning each processor set its corresponding number
  95. of processors for the run duration specified.   The  server  enforces  internal
  96. limits  on  the  number of processors and the maximum run time.  Current limits
  97. are 15 minutes and 75% or less of the processors on the system.
  98.  
  99. 3. Implementation
  100.   The server satisfies requests in a greedy fashion with  strict  adherence  to
  101. the  order  in  which  they  are  received.   For example, if the server has 10
  102. processors and receives requests for 4, 7, and 2 processors,  it  will  satisfy
  103. the  request  for  4  first,  and then the requests for 7 and 2 together.  This
  104. algorithm  was  chosen  for  its  simplicity  and  lack  of  starvation;   more
  105. sophisticated  algorithms  that make better use of the processors by satisfying
  106. requests out of order could be used.
  107.  
  108.   The server implementation was based on the  cthreads  library  and  the  Mach
  109. Interface  Generator(MiG).    Two  threads are used internally; one manages the
  110. assignment of processors to requests, the other manages all  interactions  with
  111. clients.     Clients  communicate  with  the  server  via  rpcs;  MiG-generated
  112. interfaces hide the details of the message formats.  In addition the server can
  113. optionally generate notification messages to indicate that processors have been
  114. allocated to a request and that processors are  about  to  be  removed  from  a
  115. request;   these   messages   can  be  used  for  internal  synchronization  of
  116. applications that require multiple processors for proper execution.
  117.  
  118. 4. Interface
  119.   The server's  interface  to  its  clients  uses  remote  procedure  calls  to
  120. implement the following primitives:
  121.  
  122.    - cpu_request_create(server,    total_processors,   run_time,   *delay,
  123.      *request) -- create a request  for  total_processors  processors  for
  124.      run_time  seconds.    The  request  object  and  a delay estimate are
  125.      returned.  The initial server port (server) is obtained by looking up
  126.      the name "cpu_server" with the local name service.
  127.  
  128.    - cpu_request_add(request, processor_set, processors, *processors_left)
  129.      --  Add  the  tuple  <processor_set,  processors>  to  the  specified
  130.      request.    Return  the  number of processor remaining in the request
  131.      (i.e. that can be used in future cpu_request_add calls).
  132.  
  133.    - cpu_request_set_notify(request, notify_port) - Ask the server to send
  134.      a  notification  message  to  notify_port  after  the  processors are
  135.      allocated and 1 second before removing the processors.   Applications
  136.      that  receive these messages can use them to make sure that execution
  137.      only takes place while all of the processors are allocated;  the  end
  138.      message  can  be  used  to initiate a barrier synchronization to stop
  139.      cleanly, and the start message can be used to exit the barrier.
  140.  
  141.    - cpu_request_activate(request,   options,   total_time,   *delay)   --
  142.      Activate  the  request  (i.e.  request  the server to satisfy it).  A
  143.      maximum delay until the requested processors  will  be  allocated  is
  144.      returned.    No  further  cpu_request_add  calls are permitted on the
  145.      request.  The following options are supported:
  146.  
  147.         * Destroy -  Destroy  the  processor  sets  when  the  request  is
  148.           completed.     This  is  intended  to  support  naive  users  by
  149.           preventing a program that overruns its request from  going  into
  150.           suspended  animation;  destroying  its processor sets forces the
  151.           program back into  the  default  processor  set  where  it  will
  152.           continue to run.
  153.  
  154.         * Repeat  -  Repeat the request for total_time.  The time for each
  155.           instance of the request is specified by the run_time argument of
  156.           the cpu_request_create operation that created the request.
  157.  
  158.    - cpu_request_activate_task(request, options, total_time, task, *delay)
  159.      -- Identical to cpu_request_activate, but informs the server that the
  160.      application  using  the  processor  sets  is  a task; this allows the
  161.      server to optimize assignment and  removal  of  processors  by  using
  162.      task_suspend  and  task_resume -- processor assignment is much faster
  163.      if the processor is idle.
  164.  
  165.    - cpu_request_destroy(request) - Destroy the specified request, freeing
  166.      any  processors  that were allocated to it.  If the Notify end option
  167.      applies, an end notification will be sent  and  the  freeing  of  the
  168.      processors will be delayed by 1 second.
  169.  
  170.    - cpu_request_status(request,                     *reserved_processors,
  171.      *assigned_processors,  *active,   *options,   *time)   -   Find   out
  172.      information  about  a  request  including  whether  it has processors
  173.      assigned to it, and how long until the assigned  processors  will  be
  174.      removed,  or  the  maximum delay until processors will be assigned to
  175.      it.
  176.  
  177.    - cpu_server_info(server, *max_time, *max_total_time,  *max_processors,
  178.      *delay)  --  Obtain  information  about  the server.  max_time is the
  179.      maximum  time   for   a   single   request   in   cpu_request_create.
  180.      max_total_time  is  the  maximum  total  time for a repeating request
  181.      created   by   the   Repeat   option   to   cpu_request_activate   or
  182.      cpu_request_activate_task.    max_processors is the maximum number of
  183.      processors for any request.  delay is the current maximum delay until
  184.      a  new  request can be satisfied.  The cpuinfo program uses this call
  185.      to determine if the cpu_server is  available  and  what  its  current
  186.      situation is.
  187.  
  188. 5. Library Interfaces
  189.   The  above  server  interface  along  with  the kernel interface will be used
  190. directly by programs that require  explicit  control  over  which  threads  are
  191. executing  on  which  processors  at  which  time.   For applications with less
  192. stringent processor allocation requirements, simple  library  interfaces  which
  193. hide  all of the internal details of interaction with the kernel and server may
  194. be appropriate.  Four interfaces have been developed, the allocate, task, hook,
  195. and task-hook interfaces.
  196.  
  197.   The  allocate interface supports a single allocation of a pool of processors.
  198. It exports the following two calls:
  199.  
  200.    - allocate_processors(num_processors,  time,  interactive)  -  Allocate
  201.      num_processors  processors  for  the  specified time.  If the time is
  202.      larger than the server's maximum slice time, then a repeating request
  203.      is  automatically submitted.  If interactive is TRUE, errors generate
  204.      printfs, and the user is asked whether the server's maximum delay  is
  205.      acceptable; no allocation is performed if the answer is no.
  206.  
  207.    - deallocate_processors()   -   Free   the   processors   allocated  by
  208.      allocate_processors.  This must be called by a  thread  in  the  same
  209.      task as the thread that did the allocation.
  210.  
  211. allocate_processors  does  not  return  until  the allocation of processors has
  212. started; it performs a task_assign internally so that the  initial  thread  and
  213. all  threads and tasks subsequently created share the allocated processors.  If
  214. a program overruns its time allocation, it will continue to  run,  but  without
  215. dedicated processors.
  216.  
  217.   The  task interface is identical to the allocate interface, but is restricted
  218. to applications consisting of a single task so  that  the  server  can  exploit
  219. efficiencies  available  in  this  case  (suspending  the  task before removing
  220. processors).  The server will perform  its  own  task_suspend  and  task_resume
  221. calls  on  the task in this case.  The task interface exports the following two
  222. calls:
  223.  
  224.    - task_allocate_processors(num_processors, num_seconds, interactive)  -
  225.      Identical  to  allocate_processors, but also promises the server that
  226.      all or the threads using the processors will be in the current task.
  227.  
  228.    - task_deallocate_processors() - Deallocate the processors allocated by
  229.      task_allocate_processors.
  230.  
  231.   The  hook  interface  supports  allocation of a pool of processors, with user
  232. scheduling hooks.  It exports the following two calls:
  233.  
  234.    - allocate_processors_with_hooks(num_processors,           num_seconds,
  235.      start_hook, end_hook, interactive) - Allocate the specified number of
  236.      processors for the specified number of seconds.   If  the  number  of
  237.      seconds  is greater than the server's maximum slice time, a repeating
  238.      request is automatically submitted.  start_hook is called  each  time
  239.      after  the  processors  are allocated.  Similarly, end_hook is called
  240.      approximately   1   second   before   any   processor   deallocation.
  241.      interactive functions identically to the previous interfaces.
  242.  
  243.    - deallocate_processors_with_hooks() - Free the processors allocated by
  244.      allocate_processors_with_hooks.  The end_hook will not be called, but
  245.      users  should  be  aware of the race between this deallocate call and
  246.      the server ending a time slice.
  247.  
  248. A thread must be dedicated to the allocate_processors_with_hooks call; i.e. the
  249. calling  thread  does  not  return  until the allocation request is finished or
  250. terminated.  This dedicated thread is  assigned  to  the  allocated  processors
  251. (this can be reversed by performing a thread_assign_default or thread_assign as
  252. part of the first invocation of start_hook.  All threads within  its  task  and
  253. subsequently  created  tasks  are  also  assigned  (c.f.  task_assign).    Both
  254. start_hook and end_hook must return.
  255.  
  256.   Finally, there is the task-hook interface, which combines  the  functionality
  257. of  the  hook interface with the server optimization of the task interface; the
  258. calls in this interface are the  hook  interface  calls  with  task_  prefixed.
  259. Users  should  note  that  the  interfaces  are independent; processors must be
  260. deallocated with the deallocate call from the same interface that was  used  to
  261. allocate them.
  262.  
  263. 6. Extensions
  264.   The cpu_server could be extended in a number of ways:
  265.  
  266.    - Time  Sensitivity  - Allow more of the machine to be allocated during
  267.      off peak periods.
  268.  
  269.    - Request Size Sensitivity - Use a declining priority system instead of
  270.      absolute  ordering to speed throughput.  This is a standard technique
  271.      from  schedulers  for  physical  memory   machines;   other   similar
  272.      techniques  are  also  applicable  (the  current processor allocation
  273.      problem for multiprocessors is  essentially  similar  to  the  memory
  274.      allocation problem for schedulers for physical memory machines).
  275.  
  276.    - User  Sensitivity  -  Reserve some portion of the machine for certain
  277.      users based on administrative decisions  (e.g.  they  paid  for  some
  278.      portion of the machine, so they should always be able to get at least
  279.      that portion).
  280.  
  281.    - Non-Uniform Topologies - For NUMA (Non Uniform  Memory  Access),  all
  282.      topology  knowledge  and policy is located in the server.  Techniques
  283.      such as first-fit and best-fit may be  applicable  to  the  processor
  284.      allocation  server  for  such  a  machine (e.g. the clustered Gigamax
  285.      machine being built by Encore).
  286.  
  287. In addition the server and the kernel interface (thread  assignment)  could  be
  288. used directly in a language runtime that is sophisticated enough to control and
  289. allocate processors to its threads.
  290.                                Table of Contents
  291. 1. Introduction                                                               1
  292. 2. Concepts                                                                   1
  293. 3. Implementation                                                             1
  294. 4. Interface                                                                  1
  295. 5. Library Interfaces                                                         1
  296. 6. Extensions                                                                 2
  297.