TL,DR; They improved the way they farmed what was left, kept the Thematic freeholder penetes a societal pillar, and outlived their most dangerous rivals.
For need of context, keep in mind that the population numbers of Constantinople began to suffer under Heraclius after the Persians took control of Egypt in 618. At this point, the grain supplies to Constantinople effectively stopped, and the grain dole was cancelled for the first time in five centuries. Heraclius retook control of Egypt ten years later, and the grain began to flow again, but there is no mention of the dole being restored. In either case, the discussion is essentially irrelevant, as the Byzantines lost Egypt just twelve years after they got it back. With the failure of Byzantine armies to retake Alexandria from the Arabs in 646, much less the Nile river valley where all the grain was grown, the Byzantines, for the first time since Egypt was secured under Augustus, had to look elsewhere to feed their capital.
At first, the Byzantines relied on North Africa, which had supplied Italy with grain in the fourth and early fifth centuries. The Arabs, while they did raid the Exarchate of Africa, were not able to initially take Carthage like they did Egypt and the Levant. The Rashidun Caliphate faced surprisingly stiff resistance in Egypt and reversals in Anatolia, so the Umayyad Caliphate, still very much intent on obtaining the quick expansion the initial Caliphs enjoyed, instead focused its energy on seizing the Byzantine capital to break the Empire apart rather than continuing west along the African coast. This effort, which included the building of an Arab navy and a prolonged siege (674-678), was ultimately abortive, and resulted in the first real full stop against Arab expansion. The Byzantines got a peace treaty, and some time to recover. With the fertile land in Africa and Sicily still under Byzantine control, grain could still continue to come to the capital, and the military situation prompted Constans II and Constantine IV to create the land-for-service Thematic system, which would significantly assist in keeping the armies competitive and turning Anatolia into, if not a cash cow, an arms dealer. Numerous laws were passed protecting the status of Thematic freeholders, or the Penetes who were able to farm the last Byzantine province at a level never done before.
Of course, Carthage was eventually lost. The fifty years of Byzantine control after the disasters at the end of Heraclius's reign helped keep the Empire alive, but when a civil crisis hit after Justinian II's deposition at the turn of the eighth century, the status quo again changed. Invading the Caliphate in 692, Justinian II seriously misjudged the Caliphate's strength, and in response to a Byzantine invasion of Syria, they invaded North Africa, this time cutting off Carthage, and neither Leontios nor Tiberius III could take the city back. Arab movements during the eighth and ninth centuries into Sicily cut that off from Constantinople as well, so now the Byzantines really had no easy grain provinces left.
Ostrogorsky would have us believe the Crimean coast supplied the Constantinopolitan grain after this, but Teall writes instead that after this point, Constantinople was instead supplied by grain from the Theme of Thrace, and other excesses from Anatolia. It wasn't so much that the Byzantines had an area that they could rely on, but rather that "if Byzantine agriculture met the demand for grain that Constantinople, the armies, and the lesser cities imposed, it did so because the total acreage of arable land was fully exploited," (Teall 130) which is a really excellent way of describing the situation. The Byzantines simply played every card at their disposal to survive. If the Romans could be lax about acreages because of Egypt, the Byzantines couldn't be; with the soldiers farming their Themes, they made sure every last inch of land they had was being used, and it worked, creating one of the most effective armies and tax structures in Europe during the medieval period.
Of course, to keep this efficiency, the Byzantines had a special interest in maintaining the status of the penetes. Among the many land laws regarding them was the allelengyon, or tax by village rather than person. If a freeholder could not pay his taxes because of famine or other extenuating circumstances, the entire village was held accountable for the lost income. This particular format of the law was instituted by Nicephorus I in the early ninth century. While harsh, there was flexibility, and later versions of the tax (under Basil II in 1002) allowed for the protection of the penetes class, making the more powerful members of the Byzantine aristocracy, or dynatoi, cover for the poorer freeholders in those circumstances, keeping the penetes, who farmed so well for the armies, firmly entrenched, which kept crop growth efficient and prevented the aristocracy from seizing too much power. I am not an expert on Byzantine land laws, as they are, for lack of a better word, very byzantine, but nevertheless, numerous laws like these kept the grain supply running throughout the ninth and tenth centuries.
Finally, as hinted at earlier, the Byzantines got the upper hand over their enemies. The Umayyad failure to take Constantinople the second time in the eighth century following the Byzantine crises triggered their own in the form of the Abbasid Revolution, and the Abbasid Caliphate was not interested in outright conquest. Their power too calcified in time, ending the raids. The Fatimid Caliphate came to power as the Empire was exploiting its recovery, and sought peace with their more powerful neighbor more often than not. On the European side, the Bulgarian Empire was hurt by the very thing that helped bring it to power; the Danube frontier was exposed, and first the Magyars and then the Rus destabilized the Bulgarians enough for the Byzantines to gain the upper hand. The Carolingian and Holy Roman Empires, though powerful, never came into serious conflict with Byzantium over its key territories before the Crusades. All this helped even further, as by the end of the tenth century, the raids had ceased, the farming territories were secure from conquest, and the Byzantine armies everywhere were ascendant. The Byzantine land laws worked, allowing Nicephoros Phocas to retake Cilicia and Crete, John Tzimiskes to campaign as far as Palestine, not done since Heraclius, and Basil II toend the First Bulgarian Empire and secure much of Syria under Byzantine suzerainty. The result was that the Byzantine Empire the foremost state in Europe and the Near East in 1025, and by some estimations, Constantinople, once reduced to 50,000, the largest city in the world.
Sources:
Kazhdan, Alexander. n.d. “Allelengyon.” In The Oxford Dictionary of Byzantium, 69. Oxford ; New York: Oxford University Press. McGeer, Eric. 2000. The Land Legislation of the Macedonian Emperors. Pontifical Institute of Mediaeval Studies. Ostrogorsky, George. 1940. History of the Byzantine State. Rutgers University Press. ———. 1966. “Agrarian Conditions in the Byzantine Empire in the Middle Ages.” In Cambridge Economic History of Europe, 2nd ed., 1:205–34. Cambridge University Press. Teall, John L. 1959. “The Grain Supply of the Byzantine Empire, 330-1025.” Dumbarton Oaks Papers 13: 87–139. https://doi.org/10.2307/1291130.
(I'm glad all the things I had saved on Zotero are still coming in handy after uni haha)
For the most part, locally.
Until Africa was lost to the Byzantines in the late seventh century, and Sicily over the course of the ninth and tenth, these fertile areas may have sent some grain to Constantinople, as they had to Rome centuries before. There is, however, no evidence that they did so regularly or in large quantities. Likewise, though merchants from the steppes north and west of the Black Sea probably brought small quantities of grain into the city, they do not seem to have been a major source of supply.
Most of Constantinople's grain came, instead, from the city's European (Thracian) and Asian (Bithynian) hinterlands. Thrace was probably the more important of these; as early as the reign of Constans II (r. 641-68), we hear about ships filled with grain regularly sailing from Thracian ports to Constantinople. The area along the Strymon River seems to have been especially productive. At least in some periods, Bithynia was also vital: the chronicler Theophanes, for example, records that ships from Constantinople crossed to the Asian suburb of Chalcedon to resupply the capital with grain immediately after the great Arab siege of 717-18.
It seems, in short, that many relatively small-scale producers (and a few larger ones - by the ninth century, rich families from Constantinople often had estates in Bithynia) regularly sent grain to the Constantinoplitan market. Although the city's rapid growth in the ninth and tenth centuries may have strained this system, it never outstripped its capacity.
John Teall, "The Grain Supply of the Byzantine Empire, 330-1025" Dumbarton Oaks Papers 13 (1959), 87-139
Who did these population estimates, and using what evidence?
It's hard to extrapolate from the populations of smaller cities, so some scholars favor much lower estimates, and others much higher estimates, for the great cities of the ancient and medieval worlds. If you're combining sources, a mismatch can be an issue.
Josiah Russell estimates that in the early 5th Century, Constantinople had about 147,880 people. He uses a somewhat speculative interpretation of the Notitia of the city. (Josiah Russell, Late Ancient and Medieval Population, page 66, also page 77.) He also states "if 300 a hectare (a very high index) is permitted, the city would have had ablout 192,000 persons at its height under Justinian." and seems to favor an estimate of about 160,000. (ibid, page 93.)