From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jaco Kroon Date: Thu, 18 Jan 2007 20:07:15 +0000 Subject: Re: [KJ] question about race condition Message-Id: <45AFD373.9000604@kroon.co.za> MIME-Version: 1 Content-Type: multipart/mixed; boundary="===============1789253914==" List-Id: References: <200701181927.l0IJR6TA004900@bingnet2.cc.binghamton.edu> In-Reply-To: <200701181927.l0IJR6TA004900@bingnet2.cc.binghamton.edu> To: kernel-janitors@vger.kernel.org This is a cryptographically signed message in MIME format. --===============1789253914== Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=sha1; boundary="------------ms060607000601070705020203" This is a cryptographically signed message in MIME format. --------------ms060607000601070705020203 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Shaobo Liu wrote: > I have a question about concurrence confusing me a lot. > > As we know, when a resource is shared by multiple processes, we need some mechanism to protect > shared resource. > > For example, process A and process B both share a data structure DS. > Both A and B want write new data into DS. > > > > Usually we use a mutex to protect DS, > here the mutex is defined as: > > DECLARE_MUTEX(mut); > > for process A > { > ..... > down_interruptible(&mut); > A operates on DS; > up(&mut); > ....... > > } > > for process B > { > ..... > down_interruptible(&mut); > B operates on DS; > up(&mut); > ....... > > } > > If the above pseudo code is run on a multi-core system, and if one core tries "down_interruptible(&mut) " > in process A, with another core trying "down_interruptible(&mut);" in process B exactly at the same time, both A and B > will get the semaphore simultaneously, and then operate on DS. > > It seems we have no way to protect the shared resource at all. > > The similar logics also fit in with other locking mechanism such as mutex, spinlock, and atomic variables. > > Can you tell me my misunderstaning about above scenario. You're missing the fact that the attempt to take the lock happens atomically. I'm not 100 % sure about the kernel implementation, but basically one way to do this would be to store the value 0 in the memory location representing the lock, or "available". Now x86 (and x86_64) has the ability to lock the memory bus (only one of the processors/cores can access that particular memory location) for the duration of an instruction. So in terms of assembler an attempt to take the lock would then look something like (assuming edi has been pre-loaded with the memory address representing the lock): mov ax, 1 retry: lock xchg ax, [esi] test ax, ax jz success jmp retry success: ; lock is taken Whether the above is interruptable or not depends on the status of the i bit in the cpu status flags (cli/sti). Of course, we can also make a call just before the jmp to retry to attempt scheduling another process on this core to give whatever process is holding the lock an opportunity to finish it's job. Anybody please feel free to correct me. You can also take a look at at atomic.h (can't remember it's exact location in the sources) to get a better idea of what I'm talking about (atomic.h abuses the lock command to achieve some pretty cool stuff - I've used it once to speedup calculations in userspace that would otherwise have had to be protected with a mutex). PS: You're race condition applies equally to a unicore processor if interrupts are still enabled. Jaco --------------ms060607000601070705020203 Content-Type: application/x-pkcs7-signature; name="smime.p7s" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="smime.p7s" Content-Description: S/MIME Cryptographic Signature MIAGCSqGSIb3DQEHAqCAMIACAQExCzAJBgUrDgMCGgUAMIAGCSqGSIb3DQEHAQAAoIII/zCC AtowggJDoAMCAQICEGCOKyIwPh/O8sXnHglxoYcwDQYJKoZIhvcNAQEEBQAwYjELMAkGA1UE BhMCWkExJTAjBgNVBAoTHFRoYXd0ZSBDb25zdWx0aW5nIChQdHkpIEx0ZC4xLDAqBgNVBAMT I1RoYXd0ZSBQZXJzb25hbCBGcmVlbWFpbCBJc3N1aW5nIENBMB4XDTA2MDEzMTIwMzYzMloX DTA3MDEzMTIwMzYzMlowQjEfMB0GA1UEAxMWVGhhd3RlIEZyZWVtYWlsIE1lbWJlcjEfMB0G CSqGSIb3DQEJARYQamFjb0Brcm9vbi5jby56YTCCASIwDQYJKoZIhvcNAQEBBQADggEPADCC AQoCggEBAM+crsvygldZBbroFVKXOL/kr9Uvdqu1Dy/mOLws6U8LJ3+I4X9DtNnod0u+kzkS DrEBkLqkD+JtZBwcKp50hFreguFdHQf8Q008Dzb0fxWAPcgxm8TyNRZX8gApa4HtSkBXq739 NM2PqwDfB7TvaS3UQkqzWEQp0a8lggdMtQ4Y/2TlyHt2LDrxwvKiqDDn7frRnI498UoM8hRv OdSNcIop1MkkYTs1Ln0a05nKsrJZduz5DE0i+gljx7hDxXxdMoDjiORXnyjJSEl/YVvueq7B yM/XFpT1WAzAiGKrbqxPsxLulpoiar7px39CTU2Dwkee5wqSnRdyEQYLsdcEfzkCAwEAAaMt MCswGwYDVR0RBBQwEoEQamFjb0Brcm9vbi5jby56YTAMBgNVHRMBAf8EAjAAMA0GCSqGSIb3 DQEBBAUAA4GBACMDnVVMrJkMcbDapRLLi4iPjSoU7uTsM2EpBcgMJZeAAHPziTo3ig0UfpFH d0j0thg2u+7/mYJhwk1Zyy26oQmWIW9PSwzEBDuQ/ORc7z5Gtn0QSqRmVJuuIFtrolU1p7Eg 8Yw8sXzMIWAN4ibEfdokWX51q8IY71oXvECC+SeiMIIC2jCCAkOgAwIBAgIQYI4rIjA+H87y xeceCXGhhzANBgkqhkiG9w0BAQQFADBiMQswCQYDVQQGEwJaQTElMCMGA1UEChMcVGhhd3Rl IENvbnN1bHRpbmcgKFB0eSkgTHRkLjEsMCoGA1UEAxMjVGhhd3RlIFBlcnNvbmFsIEZyZWVt YWlsIElzc3VpbmcgQ0EwHhcNMDYwMTMxMjAzNjMyWhcNMDcwMTMxMjAzNjMyWjBCMR8wHQYD VQQDExZUaGF3dGUgRnJlZW1haWwgTWVtYmVyMR8wHQYJKoZIhvcNAQkBFhBqYWNvQGtyb29u LmNvLnphMIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAz5yuy/KCV1kFuugVUpc4 v+Sv1S92q7UPL+Y4vCzpTwsnf4jhf0O02eh3S76TORIOsQGQuqQP4m1kHBwqnnSEWt6C4V0d B/xDTTwPNvR/FYA9yDGbxPI1FlfyAClrge1KQFervf00zY+rAN8HtO9pLdRCSrNYRCnRryWC B0y1Dhj/ZOXIe3YsOvHC8qKoMOft+tGcjj3xSgzyFG851I1wiinUySRhOzUufRrTmcqysll2 7PkMTSL6CWPHuEPFfF0ygOOI5FefKMlISX9hW+56rsHIz9cWlPVYDMCIYqturE+zEu6WmiJq vunHf0JNTYPCR57nCpKdF3IRBgux1wR/OQIDAQABoy0wKzAbBgNVHREEFDASgRBqYWNvQGty b29uLmNvLnphMAwGA1UdEwEB/wQCMAAwDQYJKoZIhvcNAQEEBQADgYEAIwOdVUysmQxxsNql EsuLiI+NKhTu5OwzYSkFyAwll4AAc/OJOjeKDRR+kUd3SPS2GDa77v+ZgmHCTVnLLbqhCZYh b09LDMQEO5D85FzvPka2fRBKpGZUm64gW2uiVTWnsSDxjDyxfMwhYA3iJsR92iRZfnWrwhjv Whe8QIL5J6IwggM/MIICqKADAgECAgENMA0GCSqGSIb3DQEBBQUAMIHRMQswCQYDVQQGEwJa QTEVMBMGA1UECBMMV2VzdGVybiBDYXBlMRIwEAYDVQQHEwlDYXBlIFRvd24xGjAYBgNVBAoT EVRoYXd0ZSBDb25zdWx0aW5nMSgwJgYDVQQLEx9DZXJ0aWZpY2F0aW9uIFNlcnZpY2VzIERp dmlzaW9uMSQwIgYDVQQDExtUaGF3dGUgUGVyc29uYWwgRnJlZW1haWwgQ0ExKzApBgkqhkiG 9w0BCQEWHHBlcnNvbmFsLWZyZWVtYWlsQHRoYXd0ZS5jb20wHhcNMDMwNzE3MDAwMDAwWhcN MTMwNzE2MjM1OTU5WjBiMQswCQYDVQQGEwJaQTElMCMGA1UEChMcVGhhd3RlIENvbnN1bHRp bmcgKFB0eSkgTHRkLjEsMCoGA1UEAxMjVGhhd3RlIFBlcnNvbmFsIEZyZWVtYWlsIElzc3Vp bmcgQ0EwgZ8wDQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBAMSmPFVzVftOucqZWh5owHUEcJ3f 6f+jHuy9zfVb8hp2vX8MOmHyv1HOAdTlUAow1wJjWiyJFXCO3cnwK4Vaqj9xVsuvPAsH5/Ef kTYkKhPPK9Xzgnc9A74r/rsYPge/QIACZNenprufZdHFKlSFD0gEf6e20TxhBEAeZBlyYLf7 AgMBAAGjgZQwgZEwEgYDVR0TAQH/BAgwBgEB/wIBADBDBgNVHR8EPDA6MDigNqA0hjJodHRw Oi8vY3JsLnRoYXd0ZS5jb20vVGhhd3RlUGVyc29uYWxGcmVlbWFpbENBLmNybDALBgNVHQ8E BAMCAQYwKQYDVR0RBCIwIKQeMBwxGjAYBgNVBAMTEVByaXZhdGVMYWJlbDItMTM4MA0GCSqG SIb3DQEBBQUAA4GBAEiM0VCD6gsuzA2jZqxnD3+vrL7CF6FDlpSdf0whuPg2H6otnzYvwPQc UCCTcDz9reFhYsPZOhl+hLGZGwDFGguCdJ4lUJRix9sncVcljd2pnDmOjCBPZV+V2vf3h9bG CE6u9uo05RAaWzVNd+NWIXiC3CEZNd4ksdMdRv9dX2VPMYIDZDCCA2ACAQEwdjBiMQswCQYD VQQGEwJaQTElMCMGA1UEChMcVGhhd3RlIENvbnN1bHRpbmcgKFB0eSkgTHRkLjEsMCoGA1UE AxMjVGhhd3RlIFBlcnNvbmFsIEZyZWVtYWlsIElzc3VpbmcgQ0ECEGCOKyIwPh/O8sXnHglx oYcwCQYFKw4DAhoFAKCCAcMwGAYJKoZIhvcNAQkDMQsGCSqGSIb3DQEHATAcBgkqhkiG9w0B CQUxDxcNMDcwMTE4MjAwNzE1WjAjBgkqhkiG9w0BCQQxFgQU8JhDuy5RxM6cZeGzGNV2SdiZ sakwUgYJKoZIhvcNAQkPMUUwQzAKBggqhkiG9w0DBzAOBggqhkiG9w0DAgICAIAwDQYIKoZI hvcNAwICAUAwBwYFKw4DAgcwDQYIKoZIhvcNAwICASgwgYUGCSsGAQQBgjcQBDF4MHYwYjEL MAkGA1UEBhMCWkExJTAjBgNVBAoTHFRoYXd0ZSBDb25zdWx0aW5nIChQdHkpIEx0ZC4xLDAq BgNVBAMTI1RoYXd0ZSBQZXJzb25hbCBGcmVlbWFpbCBJc3N1aW5nIENBAhBgjisiMD4fzvLF 5x4JcaGHMIGHBgsqhkiG9w0BCRACCzF4oHYwYjELMAkGA1UEBhMCWkExJTAjBgNVBAoTHFRo YXd0ZSBDb25zdWx0aW5nIChQdHkpIEx0ZC4xLDAqBgNVBAMTI1RoYXd0ZSBQZXJzb25hbCBG cmVlbWFpbCBJc3N1aW5nIENBAhBgjisiMD4fzvLF5x4JcaGHMA0GCSqGSIb3DQEBAQUABIIB ALj/Fu3Bf/8fC8wg8tJoLCa+RfogHwOTmyjc5Goqk7WmDsn/suGYwL8sGT8YDmjDN5VPK7oE 4QAHss3z+CltRLbYlNfxW9wtVQRZPAkAkA/6pa6yOxGchmTYQ/qxhBXQc8B3cmKp2bj8gIwS bujsQuTX06+6uCTWszJbfRT8qJS50ZqRTiG2OECYHHzti+2F0sv5TRrdQrgLh770WTbHJD2Y OjL9SprMti23fXKndZxcPgijpb23SjdGplifmQ3A2IUQLmiKi6wKRIVWJjTIqLrv/ziJ18Pt meGjX6uY/AvOx0O7nEXCe81m1EexNDlJ1uEC6yHZI60OikD30n0/E10AAAAAAAA= --------------ms060607000601070705020203-- --===============1789253914== Content-Type: text/plain; charset="iso-8859-1" MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline _______________________________________________ Kernel-janitors mailing list Kernel-janitors@lists.osdl.org https://lists.osdl.org/mailman/listinfo/kernel-janitors --===============1789253914==--