Right now I'm trying to implement some sort of depth buffer in software and I have a huge problem when I'm writing to it. Having one mutex is absolute overkill. So I created a number of mutexes equal to the number of threads. I'm locking a mutex based on current pixel (pixel_index % mutexes_number) and this works better, but still very very slow. And I wonder how it's done in a real GPU? Is there a clever algorithm or hardware handles it?
Highly specialized hardware handles it. A typical strategy is for a GPU to tile rasterization and store depth information in compressed formats (e.g. the z-equation when a polygon completely covers a tile). This allows testing across an entire tile at once; other cool HW tricks include depth testing before the pixel shader is run (assuming conditions permit - the shader cannot write a depth value). You might consider something similar in software, such as having each thread "own" a subset of tiles and walk each primitive independently, or mimic multi-gpu strategies such as alternate frames or alternate raster lines.
In a real GPU, instead of having multiple cores trying to read/write the same region of the depth buffer and attempting to synchronize between them, the depth buffer is divided into tiles (such as 16×16 or 32×32), and each tile is assigned to a single core. That core is then responsible for all rasterization in that tile: any triangles that touch that tile will be rasterized (within that tile) by the owning core. Then there is no interference between cores, and no need for them to synchronize when accessing their part of the framebuffer.
This implies that triangles that touch multiple tiles will need to be rasterized by multiple cores. So, there is a work redistribution step between geometry processing (operations on vertices and triangles) and pixel processing.
In the geometry stage, each core might process a chunk of input primitives; then for each primitive, it can quickly determine which tiles the primitive touches (this is called "coarse rasterization"), and add the primitive to a queue for each core that owns one of the affected tiles.
Then, in the pixel stage, each core can read out the list of primitives in its queue, calculate pixel coverage for the tiles the core owns, and proceed to depth testing, pixel shading and updating the framebuffer, with no need of any further coordination with other cores.