When GPS can't see satellites, how can I continue to tick off a smooth-ish time? I'm getting 10 updates/sec from my GPS unit (The MTK3339 used in the Adafruit breakout board), and using it to update a clock display. This works well enough, though there's one minor problem that I'd like to solve and one major one that I have to solve.

The minor issue first; I don't get an update every 100ms. I get one roughly every 100ms... plus or minus about 20-30ms. If a late and an early update arrive back-to-back right when the display goes from n to n+1 seconds, it's noticeable that it's not ticking at a regular cadence. It's not fatal, but the arythmic stutter of it is deeply painful to watch.

The major issue is - what do I do when the GPS can't find a signal? Maybe the device is driving through a tunnel for a minute or there's some other sky obstruction. I still want the clock to update in a best-guess sort of way.

You can't just update the seconds display and then, 1000 (arduino-measured) milliseconds later, update the clock if a new message hasn't arrived. 1000 real-world milliseconds can be anywhere from 700 - 1400ms measured by an arduino, depending on the board and the quality of the crystal. Worse yet, the discrepancy is far from consistent within a single crystal. Seeing the processor speed up and slow down by several percent over the course of a few minutes isn't uncommon.

So what I'd like is a mechanism that will constantly smooth the received (GPS) time to give a best-estimate of current actual time. I'm okay with it being a second or two off (at most) from real time, as long as the cadence feels like actual seconds, and a loss of GPS for a few minutes can be quickly corrected when the signal is re-acquired.

I'm somewhat aware of (strikethrough)DIP(/strikethrough) PID methods, but I'm not sure how to apply them here. It seems that someone must have solved the problem for the sake of syncing internet time, so I shouldn't be reinventing a solution.
What you want, namely something to “smooth the received (GPS) time”,
is called a GPS disciplined oscillator. Obviously, you are not
after the high accuracy of commercial GPSDOs, but the working principle
of what you are describing is essentially the same.


  what do I do when the GPS can't find a signal?


In GPSDO lingo, this is called the “holdover” state. At this point you
rely solely on your local oscillator (here, millis() or micros()),
and steer it to correct for is natural drift, as determined while the
GPS reception was good. Or you can go fancy, measure the chip
temperature, and apply a temperature compensation.


  I'm somewhat aware of DIP methods, but I'm not sure how to apply them
  here


I guess you mean “PID”.

You apply this to the phase of the oscillator. If the local oscillator
is ahead of the GPS (positive phase error), you lower its frequency. For
example, you could increment the seconds count every 1,000,100
microseconds (as measured by micros()), instead of every 1,000,000.
This will make your clock a little bit slow, and resynchronize it with
the GPS. Conversely, if your clock is behind the GPS, you slightly
increase its frequency to make it run faster.

In other words, the error value of your PID is the phase error of your
clock, and the control variable is the frequency adjustment. By
applying the PID technique this way, you are building what is known as a
phase-locked loop, or PLL. This is the standard way of
implementing a GPSDO.


  It seems that someone must have solved the problem for the sake of
  syncing internet time


Sure, but NTP implementations can be quite complex, as they have to deal
with multiple servers having different round-trip delays and different
levels of trust. I am not aware of any Arduino library that does
anything similar. You may search for “time synchronization” or “PLL”. If
you don't find any, you can pick a PID library and apply it to your
oscillator.

A couple of final remarks:


You wrote “speed up and slow down by several percent over the course
of a few minutes isn't uncommon”. This shows there is something
awfully wrong with either your Arduino or your code. Over a few
minutes, you expect frequency variations of the order of one part
per million on an Arduino clocked off a ceramic resonator, and a few
parts per billion if yours is clocked off a crystal. See this
experimental study on the stability of an Arduino clock.
This stability problem is the very first thing you should investigate
and fix.
Many GPS modules have the option to give you a 1PPS (one pulse per
second) signal. If you can use this signal, you may get a quite
accurate measurement of your phase error. Relying on the NMEA
sentences will give you lots of jitter, which you would then have to
compensate for by setting the time constant of the PLL to a very long
value.