diff --git a/Misc/NEWS b/Misc/NEWS
index 659d7ca..f8c704f 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -50,6 +50,9 @@
 Library
 -------
 
+- Issue #24303: Fix random EEXIST upon multiprocessing semaphores creation with
+  Linux PID namespaces enabled.
+
 - Issue #25698: Importing module if the stack is too deep no longer replaces
   imported module with the empty one.
 
diff --git a/Modules/_multiprocessing/semaphore.c b/Modules/_multiprocessing/semaphore.c
index b9e8f34..fc42754 100644
--- a/Modules/_multiprocessing/semaphore.c
+++ b/Modules/_multiprocessing/semaphore.c
@@ -429,7 +429,7 @@
     int kind, maxvalue, value;
     PyObject *result;
     static char *kwlist[] = {"kind", "value", "maxvalue", NULL};
-    static int counter = 0;
+    int try = 0;
 
     if (!PyArg_ParseTupleAndKeywords(args, kwds, "iii", kwlist,
                                      &kind, &value, &maxvalue))
@@ -440,10 +440,18 @@
         return NULL;
     }
 
-    PyOS_snprintf(buffer, sizeof(buffer), "/mp%ld-%d", (long)getpid(), counter++);
+    /* Create a semaphore with a unique name. The bytes returned by
+     * _PyOS_URandom() are treated as unsigned long to ensure that the filename
+     * is valid (no special characters). */
+    do {
+        unsigned long suffix;
+        _PyOS_URandom((char *)&suffix, sizeof(suffix));
+        PyOS_snprintf(buffer, sizeof(buffer), "/mp%ld-%lu", (long)getpid(),
+                      suffix);
+        SEM_CLEAR_ERROR();
+        handle = SEM_CREATE(buffer, value, maxvalue);
+    } while ((handle == SEM_FAILED) && (errno == EEXIST) && (++try < 100));
 
-    SEM_CLEAR_ERROR();
-    handle = SEM_CREATE(buffer, value, maxvalue);
     /* On Windows we should fail if GetLastError()==ERROR_ALREADY_EXISTS */
     if (handle == SEM_FAILED || SEM_GET_LAST_ERROR() != 0)
         goto failure;