You don't go into a lot of detail as to how your game works, but here is what I can offer:

• If you can draw the data-dependent stuff onto a reasonably-sized surface, you can draw once, then keep the surface, and draw it onto the screen while processing. This way you can redraw cursor, HUD, etc onto the screen, but not ruin the game image, since you have it as a separate surface.
• You can save the new data in an alternate memory space. Once everything is calculated, just point to the new data and deallocate the old. You might want to / have to split game data into two parts: screen-changers and behind-the-scenes data. Or flag it, however you like.

Edit: Since some people got a bit confused as to what I meant, I'm going to elaborate a bit.

This is called a race condition. You don't go into a lot of detail as to how your game works, but here is what I can offer:

• If you can draw the data-dependent stuff onto a reasonably-sized surface, you can draw once, then keep the surface, and draw it onto the screen while processing. This way you can redraw cursor, HUD, etc onto the screen, but not ruin the game image, since you have it as a separate surface. Edit: So the procedure would now be: render onto work_in_progress_surface and blit last_stable_surface onto the screen, until you are done with AI and moving things. Now blit work_in_progress_surface onto last_stable surface and clear it for the next frame. Get user input and repeat. The main idea here is that you keep the last good frame separated.
• You can save the new data in an alternate memory space. Once everything is calculated, just point to the new data and deallocate the old. You might want to / have to split game data into two parts: screen-changers and behind-the-scenes data. Or flag it, however you like. Edit: One possible way to implement this is to make a list of all objects that could change in mid-render. Before applying AI and moving things make a deep copy of everything listed, render the old data but modify the new data. When your AI/moving is finished, just deep copy all new data into the normal objects.
• If the AI/moving is guaranteed to be very fast - less than ~200ms where it doesn't bother users, you could just suspend rendering and the UI through a semaphore. Set it to 0 when the renderer is running, then have the AI/moving set it to 1 and wait, when the renderer finishes, it should look at it before starting again. When it sees the 1 it will set it to 2 and stop rendering. The AI/moving will see the 2 and start working. When all render data has been modified, the AI/moving sets it back to 0 and backgrounds. The render thread sees the 0 and resumes rendering. This is how a pretty simple semaphore works, don't skip the extra transitional phase, think about why it's there.