What about when there is no shoulder? Is that a rare or a common problem?
I assume that you have just changed the topic and are no longer talking about highways with exits. Because in my experience, all interstate highways have shoulders.
Most high-traffic roads have shoulders. Most low-traffic roads do not. So on a low-traffic road without shoulders, it's usually not a problem to ride in the traffic lane. So where should you position yourself in the traffic lane? My preference is to ride where the right tires of the vehicle would normally be. The very edge of the road is where all the debris is, and thus where you will get all your flat tires. Also, the edge is typically not very safe because you will likely crash if your tires slips off the edge. If you have a mirror (and ears), you can tell when traffic is coming up from behind. If they move over, you can just stay where you are. If you're not sure that they are going to move over, you can move closer to the edge until they go by.
Sometimes you'll find a high-traffic road without shoulders. Get the hell off of it as soon as possible.