In my embedding, I use the following (adapting the example above):

// initialize the Python interpreter
Py_Initialize();

PyEval_InitThreads();

/* Swap out and return current thread state and release the GIL */
PyThreadState tstate = PyEval_SaveThread();

PyGILState_STATE gstate;
gstate = PyGILState_Ensure();

PyRun_SimpleString("import random\n");

PyGILState_Release(gstate); 


You don't have to free the tstate returned by PyEval_SaveThread because
it is the thread state of the main thread (as established during
Py_Initialize), and so it will be freed during Python's shut-down.

I think in general you should rarely need to call PyEval_ReleaseLock
directly; instead use PyEval_SaveThread, the Py_BEGIN_ALLOW_THREADS
macro, or PyGILState_Release (as appropriate).  The documentation should
probably say as much.