We present the first exploration of gas dynamics in a relativistic binary black hole (BH) system in which an accretion disk (a "mini-disk") orbits each BH. We focus on 2D hydrodynamical studies of comparable-mass, non-spinning systems. Relativistic effects alter the dynamics of gas in this environment in several ways. Because the gravitational potential between the two BHs becomes shallower than in the Newtonian regime, the mini-disks stretch toward the L1 point and the amount of gas passing back and forth between the mini disks increases sharply with decreasing binary separation. This "sloshing" is quasi-periodically modulated at 2 and 2.75 times the binary orbital frequency, corresponding to timescales of hours to days for supermassive binary black holes (SMBBHs). In addition, relativistic effects add an m = 1 component to the tidally driven spiral waves in the disks that are purely m = 2 in Newtonian gravity; this component becomes dominant when the separation is 100 gravitational radii. Both the sloshing and the spiral waves have the potential to create distinctive radiation features that may uniquely mark SMBBHs in the relativistic regime.