How the util of iostat is computed?

iostat -x (I used an old version of the source code to write this up before realizing it) displays information from /proc/diskstats (documented here) and /proc/stat (for CPU times; see man proc(5)) (and a few others, but that's not important for understanding).

You can see the relevant snippets of code in osgx's answer, but I couldn't make sense of them in isolation, so here's an extended explanation:

• %util = blkio.ticks / deltams * 100%
• deltams is the time elapsed since last snapshot in ms. It uses CPU stats from /proc/stat presumably because it gives better results than to rely on system time, but I don't know for sure. (Side note: for some reason the times are divided by HZ, while the documentation states it's in USER_HZ, I don't understand that.)

• blkio.ticks is "# of milliseconds spent doing I/Os", from /proc/diskstats docs:

  Field  9 -- # of I/Os currently in progress
    The only field that should go to zero. Incremented as requests are
    given to appropriate struct request_queue and decremented as they finish.
  Field 10 -- # of milliseconds spent doing I/Os
    This field increases so long as field 9 is nonzero.
  

  i.e. my understanding is that ticks is the number of ticks when any I/O request (for this device) was in progress multiplied by the duration between ticks.

So %util = 100% means that each time the kernel looked (I guess it's 1000 times per second on modern kernels, see "HZ"), an I/O request was in progress.

Here's an excerpt from another post on iostat:

[%util is] how much time did the storage device have outstanding work (was busy).

In proper RAID environments it is more like “how much time did at least one disk in RAID array have something to do”. I’m deliberately excluding any kind of cache here – if request can be served from cache, the chance is quite negligible it will show up in %util, unlike in other values.

What this also means – the RAID subsystem can be loaded from 6.25% (one disk doing the work) to 100% (all of them busy). Thats quite a lot of insight in single value of ’100%’, isn’t it?

%util is named busy in the source code of iostat: https://code.google.com/p/tester-higkoo/source/browse/trunk/Tools/iostat/iostat.c#380

Busy is counted as percent ratio of Ticks to deltams, limited to 100%

busy = 100.0 * blkio.ticks / deltams; /* percentage! */
if (busy > 100.0) busy = 100.0;

DeltaMS is sum of system load for the period of time (user time + system time + idle time + iowait)/ ncpu.

double deltams = 1000.0 *
        ((new_cpu.user + new_cpu.system +
          new_cpu.idle + new_cpu.iowait) -
         (old_cpu.user + old_cpu.system +
          old_cpu.idle + old_cpu.iowait)) / ncpu / HZ;

Ticks - is the Time of requests in queue for the period

blkio.ticks = new_blkio[p].ticks
                - old_blkio[p].ticks;

In more current version of sysstat the code is bit different: http://sources.debian.net/src/sysstat/10.2.0-1/iostat.c#L959

/*       rrq/s wrq/s   r/s   w/s  rsec  wsec  rqsz  qusz await r_await w_await svctm %util */
printf(" %8.2f %8.2f %7.2f %7.2f %8.2f %8.2f %8.2f %8.2f %7.2f %7.2f %7.2f %6.2f %6.2f\n",
...
       /*
        * Again: Ticks in milliseconds.
        * In the case of a device group (option -g), shi->used is the number of
        * devices in the group. Else shi->used equals 1.
        */
       shi->used ? xds.util / 10.0 / (double) shi->used
                 : xds.util / 10.0);    /* shi->used should never be null here */

xds is filled in the compute_ext_disk_stats(&sdc, &sdp, itv, &xds); http://sources.debian.net/src/sysstat/10.2.0-1/common.c?hl=679#L679

/*
 * Macros used to display statistics values.
 *
 * HZ is 1024 on IA64 and % should be normalized to 100.
 */
#define S_VALUE(m,n,p)  (((double) ((n) - (m))) / (p) * HZ)

xds->util  = S_VALUE(sdp->tot_ticks, sdc->tot_ticks, itv);

And there is the filling of tot_ticks from iostat.c

  * @ioi        Current sample statistics.
  * @ioj        Previous sample statistics.
  * @itv        Interval of time.
  ...

sdc.tot_ticks = ioi->tot_ticks;
sdp.tot_ticks = ioj->tot_ticks;

tot_ticks are read from "sysfs stat for current block device or partition" in read_sysfs_file_stat (iostat.c:487), and ioi and ioj are current and previous stat.