The almost-smallest devices are powered by LoopOS(tm):

  while(1){ }

So slow and bloated! Get with 2.0:

    for(;;){ }

On the really low end, hardware is often single-purpose and you don't really need an operating system. When there is an operating system (maybe you have to listen to messages from something while performing a previously requested activity), a small hard real-time scheduling library gets used as an "operating system".

Just random RT OS's? It's been awhile since I've worked on tiny 8 bit mcus, but all the stuff was really small and seemingly hand rolled, nothing as monolithic as Linux.

I would not be surprised to learn that it varies from company to company and chip to chip, with various bits being shared for common logic.

I remember VxWorks. Bigger than a while loop, but used in space missions back in the 90s: http://www.windriver.com/inspace/

Edit: looks like VxWorks wants a 32-bit CPU, 128KB of ROM, and 1-2MB of RAM. But you get threads, networking, filesystem, etc.

Tron/Etron and variants most likely if any operating system at all. What powers non-smart refrigerators, dishwashers, washing machines, microwave ovents, etc? Tron for many of them.

https://en.wikipedia.org/wiki/TRON_project

As foofoo said, they often don't use OS's so much as libraries and loops. There are OS's that have been out there for a while for tiniest devices. Contiki is probably a nice intro to different tradeoffs they make in design and features:

http://www.contiki-os.org/

On more serious MCU's, you might see things like VxWorks or QNX:

https://en.wikipedia.org/wiki/VxWorks

https://en.wikipedia.org/wiki/QNX

As hardware improved, we also saw trimmed down Linux like ucLinux, MontaVista Linux, and so on. It just went from there with increasing complexity (and reboots :).

Most of the really small stuff is written bare-metal in C or assembler. E.g. http://www.microchip.com/wwwproducts/en/PIC10F200 : 384 bytes of code space, 16 bytes of RAM. More constrained than the Atari 2600.

$0.31 each, available in 2mm x 3mm packages.

There are all kinds of micro-everything circulating out there, from timing and IO drivers to entire network stacks.